CODEWITHSUNDEEP
haskellmemoryrecursionghctail-recursion
dspyz
dspyz

Reputation: 5510

Tail-recursive function consuming memory

I have a clearly tail-recursive function for finding (choose n k) mod 10007 (with k nonnegative)

Why is this function consuming lots of memory for large inputs? (ie 100000000 choose 50000000) I can understand if it might be slow, but it shouldn't use more than constant memory, should it? (assuming GHC knows about tail-call optimization)

GHC version 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

Upvotes: 0

Views: 196

Answers (2)

Yuriosity
Yuriosity

Reputation: 1918

By the way, to simplify your expressions, you can write a helper function:

force x = x `seq` x

or use force (no pun intended) from the Deepseq package. Then

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

Upvotes: -1

dspyz
dspyz

Reputation: 5510

I was putting the seq in the wrong place.

It needs to be:

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

Otherwise the call to seq isn't evaluated until reaching the base-case and a chain of thunks is still built up.

This isn't strictly tail-recursive, but rather it's "mutually" tail-recursive since seq ultimately returns its second argument without modifying it.

Upvotes: 5

Related Questions