消耗内存的尾递归函数

Question

我有一个明确的尾递归函数用于查找(选择nk)mod10007(k非负)

为什么这个函数会为大输入消耗大量内存？(即100000000选择50000000)我可以理解它是否可能很慢,但它不应该使用超过常量内存,应该吗？(假设GHC知道尾调优化)

GHC版本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

Answer 1

我把它seq放在了错误的地方.

它需要是:

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

否则,在达到基本情况之前不会评估对seq的调用,并且仍会建立一系列thunk.

这不是严格的尾递归,而是它"相互"尾递归,因为seq最终返回它的第二个参数而不修改它.