haskell - 计算表达式模n

Question

在对大数进行模数计算时，在执行例如 mod (123456789^987654321) n 时会遇到巨大的性能损失。相反，您必须使用自己的 ^ 内部计算 mod n 也用于中间计算。

当然，我可以轻松实现自己的功能，但是我必须为每个操作明确地说“mod n”。取而代之的是，可以构建一棵数值表达式树并推迟实际计算，并且最终状态只取模一次。 (见下面我的代码)

我从这个开始清楚地表明我的意思，但我想知道是否已经存在这个实现，它似乎非常有用，所以应该有人实现它。

module Modulo where

data Expr =
    V Integer 
  | Plus Expr Expr
  | Mult Expr Expr
  deriving (Eq, Show)

instance Num Expr where
  (+) = Plus
  (*) = Mult
  fromInteger = V

eval :: Integer -> Expr -> Integer
eval m (V i) = i `mod` m
eval m (Plus e1 e2) = (eval m e1 + eval m e2) `mod` m
eval m (Mult e1 e2) = (eval m e1 * eval m e2) `mod` m

fifteen :: Expr
fifteen = 10 + 5

test = eval 13 fifteen

Answer 1

Oleg 做了这样的事情，你为模算术创建了一个实例，但是为任意模数。 Implicit configurations.