Memoria consumidora de la función recursiva de la cola: haskell, memoria, recursión, ghc, recursividad de la cola

Tengo una función claramente recursiva de cola para encontrar (elija n k) mod 10007 (con k no negativo)

¿Por qué esta función consume mucha memoria paragrandes entradas? (es decir, 100000000, elija 50000000) Puedo entender si puede ser lento, pero no debería usar más que la memoria constante, ¿no es así? (suponiendo que GHC sepa sobre la optimización de la llamada de cola)

GHC versión 7.8.3

modulus :: Int
modulus = 10007

choose :: Int -> Int -> Int
choose n1 k1
| s1 > 0 = 0
| otherwise = q1
where
(q1, s1) = doChoose n1 k1 (1, 0)
doChoose :: Int -> Int -> (Int, Int) -> (Int, Int)
doChoose _ 0 (qr, sr) = (qr, sr)
doChoose n k (qr, sr) =
doChoose (n `seq` (n-1)) (k-1) (qr `seq` (qn * qr `rem` modulus * inv qk `rem` modulus), sr `seq` (sn + sr - sk))
where
(qn, sn) = removePs n
(qk, sk) = removePs k

removePs :: Int -> (Int, Int)
removePs n =
case r of
0 -> (q0, s0 + 1)
_ -> (n, 0)
where
(q, r) = n `quotRem` modulus
(q0, s0) = removePs q

inv :: Int -> Int
inv = doInv 0 1 modulus . (`mod` modulus)
where
doInv x _ 1 0
| x < 0 = x + modulus
| otherwise = x
doInv _ _ _ 0 = error "Not relatively prime"
doInv x y a b = doInv y (x - q * y) b r
where
(q, r) = a `quotRem` b

Respuestas

Yo estaba poniendo el seq en el lugar equivocado

Necesita ser:

n `seq` qr `seq` sr `seq` doChoose (n-1) (k-1) (qn * qr `rem` modulus * inv qk `rem` modulus, sn + sr - sk)

De lo contrario, la llamada a seq no se evalúa hasta que llega a la base y se construye una cadena de thunk.

Esto no es estrictamente recursivo en la cola, sino que es "recíproco" recíprocamente en la cola, ya que en última instancia devuelve su segundo argumento sin modificarlo.

Por cierto, para simplificar tus expresiones, puedes escribir una función auxiliar:

force x = x `seq` x

o usar force (sin juego de palabras) de la Deepseq paquete. Entonces

doChoose (force n - 1) (k - 1) (qn * force qr * etc.)