Obliczanie wyrażeń modulo n

Question

Wykonując obliczenia modulo n z dużymi liczbami, napotkasz ogromne kary za wykonanie, gdy robisz na przykład mod (123456789^987654321) n. Zamiast tego musisz użyć własnego ^, który wewnętrznie oblicza mod n również dla obliczeń pośrednich.

Oczywiście, mogę łatwo realizować własne funkcje, ale muszę wyraźnie powiedzieć "mod n" dla każdej operacji. Zamiast tego można zbudować drzewo wyrażenia liczbowego i odroczyć faktyczne obliczenia, aw trybie stanu końcowego tylko jeden raz. (zobacz mój kod poniżej)

Zacząłem od tego, aby jasno pokazać, co mam na myśli, ale zastanawiam się, czy istnieją już implementacje tego, wydaje się całkiem przydatne, więc ktoś powinien to wdrożyć.

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 zrobił coś tego rodzaju, gdzie można zrobić instancję dla arytmetyki modulo, ale dla dowolnego modułu. Implicit configurations.