我经常有机会在Haskell中执行模运算,其中模数通常较大且通常为素数(如2000000011).目前,我只使用像(modAdd mab),(modMul mab),(modDiv mab)等函数.但这样做相当不方便,需要一个额外的参数来始终指定和携带并在常规积分中创建我的各种函数形式和单独的模型.
因此,创建一个类似这样的新类可能是个好主意:
class Integral a => Mod a
m = 2000000011
instance Integral a => Num (Mod a) where
... defining (+), etc. as modulo m
然后可以使用常规函数执行常规算术,并定义有用的结构,如
factorials :: [Mod Int]
factorials = 1:zipWith (*) factorials [1..]
但这有一个问题:Mod Int类型的所有值必须具有相同的模数.但是,我经常需要在一个程序中使用多个模数(当然总是只组合相同模数的值).
我想,但是不能完全理解,这可以通过以下方式克服:
class Integral a => Mod Nat a
其中Nat是一种以Peano方式编码模数的类型.这将是有利的:我可以具有不同模量的值,并且类型检查器将使我免于意外地组合该值.
这样的事情是否可行和有效？它是否会导致编译器或RTS尝试实际构建巨大的(Succ(Succ(重复...重复2000000011次)如果我尝试使用该模数,使解决方案无效？RTS是否会尝试检查在每个操作上都匹配类型吗？每个值的RTS表示是否会从一个只有一个未装箱的int中被炸毁？
有没有更好的办法？
感谢来自cirdec,dfeuer,user5402和tikhon-jelvis的有用评论,我了解到(不出所料)我不是第一个有这个想法的人.特别是,Kiselyov和Shan 最近的一篇论文给出了一个实现,并且tikhon-jelvis向Hackage发布了一个名为(surprise!)模块算术的解决方案,它使用花哨的ghc pragma提供更好的语义.
幕后会发生什么？特别是,[Mod Int 2000000011]的百万元素清单是否会带来额外的200万份20000000左右？或者它是否编译为与一百万个Int的列表相同的代码,其中模数参数单独携带？后者会很好.
我对当前正在处理的问题进行了一些基准测试.第一次运行使用了未装箱的10,000元素Int向量,并对其执行了10,000次操作:
4,810,589,520 bytes allocated …我用C型和Lisp型语言编程了几十年,而Haskell用了几年.现在为了进一步理解类型和Haskell的其他漂亮的高级功能,例如并行性,我一直在尝试创建一个带有矩阵语义的新数据类型,现在可以在库的Array类型之上进行背负.
我正在使用最新的Haskell Platform 2013.2.0.0和附带的ghc.
newtype Matrix a = Matrix (Array (Int,Int) a)
(我知道数据将起作用而不是newtype,但在这种情况下,你会得到相同的语义,而使用newtype则会获得更好的性能).
例如,创建单位矩阵的一些简单函数可以正常工作:
unityMatrix:: (Num a) => Int -> Matrix a
unityMatrix d = Matrix $ let b = ((0,0),(d-1,d-1)) in array b
[((i,j),if i==j then 1 else 0)|(i,j)<-range b]
创建基本的show函数也是如此:
instance Show a => Show (Matrix a) where
show (Matrix x) =
let
b = bounds x
rb = ((fst.fst) b, (fst.snd) b)
cb = ((snd.fst) b, (snd.snd) b)
in
intercalate "\n" [unwords ([show (x!(r,c))|c<-range cb])|r<-range rb]
然后,为了使常规算术运算符起作用,我添加: …