Função recursiva da cauda consumindo memória - haskell, memória, recursão, ghc, cauda recursiva

Eu tenho uma função claramente recursiva de cauda para encontrar (escolha n k) mod 10007 (com k não negativo)

Por que esta função está consumindo muita memória paragrandes entradas? (ou seja, 100000000 escolher 50000000) Eu posso entender se ele pode ser lento, mas não deve usar mais do que a memória constante, deveria? (supondo que o GHC sabe sobre a otimização de cauda)

GHC versão 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

Respostas:

Eu estava colocando o seq no lugar errado.

Precisa ser:

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

Caso contrário, a chamada para seq não é avaliada até atingir o caso base e uma cadeia de thunks ainda é construída.

Isto não é estritamente recursivo à cauda, ​​mas sim "mutuamente" recursivo à cauda, ​​já que seq finalmente retorna seu segundo argumento sem modificá-lo.

By the way, para simplificar suas expressões, você pode escrever uma função auxiliar:

force x = x `seq` x

ou usar force (sem trocadilhos) do Deepseq pacote. Então

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