使用Haskell类型系列或GADT的模块化算法？

Question

我经常有机会在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 in the heap
         107,496 bytes copied during GC
       1,197,320 bytes maximum residency (1454 sample(s))
         734,960 bytes maximum slop
              10 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      6905 colls,     0 par    0.109s   0.101s     0.0000s    0.0006s
  Gen  1      1454 colls,     0 par    0.812s   0.914s     0.0006s    0.0019s

  TASKS: 13 (1 bound, 12 peak workers (12 total), using -N11)

  SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)

  INIT    time    0.000s  (  0.001s elapsed)
  MUT     time    2.672s  (  2.597s elapsed)
  GC      time    0.922s  (  1.015s elapsed)
  EXIT    time    0.000s  (  0.001s elapsed)
  Total   time    3.594s  (  3.614s elapsed)

  Alloc rate    1,800,454,557 bytes per MUT second

  Productivity  74.3% of total user, 73.9% of total elapsed

对于第二次运行,我对未装箱的Vector 10,000(Mod Int 1000000007)执行了相同的操作.这使得我的代码变得更简单,但是花了大约3倍的时间(同时具有几乎相同的内存配置文件):

   4,810,911,824 bytes allocated in the heap
         107,128 bytes copied during GC
       1,199,408 bytes maximum residency (1453 sample(s))
         736,928 bytes maximum slop
              10 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      6906 colls,     0 par    0.094s   0.107s     0.0000s    0.0007s
  Gen  1      1453 colls,     0 par    1.516s   1.750s     0.0012s    0.0035s

  TASKS: 13 (1 bound, 12 peak workers (12 total), using -N11)

  SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)

  INIT    time    0.000s  (  0.001s elapsed)
  MUT     time    8.562s  (  8.323s elapsed)
  GC      time    1.609s  (  1.857s elapsed)
  EXIT    time    0.000s  (  0.001s elapsed)
  Total   time   10.172s  ( 10.183s elapsed)

  Alloc rate    561,858,315 bytes per MUT second

  Productivity  84.2% of total user, 84.1% of total elapsed

我想知道为什么会这样,如果它可以修复.不过,我真的很喜欢模块化算术包,并且会在性能不是绝对关键的情况下使用它.

Answer 1

较新版本的 GHC 内置了类型级数字，这应该比您自己使用 Peano 算术滚动的数字更有效。您可以通过启用来使用它们DataKinds。作为奖励，您还会获得一些不错的语法：

factorials :: [Mod Int 20]

这是否有效取决于您如何实现该Mod类型。在最一般的情况下，您可能希望mod在每次算术运算之后进行。除非您处于热循环中，保存少量指令很重要，否则这应该没问题。（在热循环中，无论如何，最好明确说明何时进行修改。）

我实际上在 Hackage 上的一个库中实现了这种类型：modular-arithmetic。它有一个测试套件，但没有基准测试，所以我不能保证绝对性能，但它没有做任何应该很慢的事情，而且对于我的目的来说已经足够快了。（诚​​然，这涉及小模量。）如果您尝试它并遇到性能问题，我很想听听它们，以便我可以尝试修复它们。