Calcolo espressioni modulo n

Question

Quando si eseguono calcoli modulo n con numeri grandi, si verificheranno enormi penalità per le prestazioni quando si fa, ad esempio, mod (123456789^987654321) n. Invece devi usare il tuo ^ che calcola internamente mod n anche per i calcoli di intermediazione.

Certo, posso facilmente implementare le mie funzioni, ma poi devo dire esplicitamente "mod n" per ogni operazione. Invece si potrebbe costruire un albero di espressioni numeriche e rimandare i calcoli reali, e nello stato di fine modulo n solo una volta. (vedi il mio codice qui sotto)

Ho iniziato su questo per mostrare chiaramente cosa intendo, ma mi chiedo se esista già implementazioni di questo, sembra abbastanza utile quindi qualcuno dovrebbe averlo implementato.

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 fatto qualcosa di questo genere, in cui si effettua un'istanza per l'aritmetica modulo, ma per un modulo arbitrario. Implicit configurations.