On Sunday 20 February 2011 16:42:28, Sebastian Arndt wrote:
Hi everyone,
i'm trying to understand tail recursion, but im stuck when it comes to tail recursion with tuples. Look at the following source code:
module Main(main) where
main = do putStrLn "tail recursion" print $ countOdd2 [0..10000000]
{- Tail recursion doesnt work -}
countOdd :: [Int] -> (Int, Int) countOdd lst = countOdd' lst (0,0)
countOdd' :: [Int] -> (Int, Int) -> (Int, Int) countOdd' (x:xs) last = if odd x then countOdd' xs $! (fst last, snd last + 1)
The ($!) doesn't evaluate anything here that isn't evaluated anyway. x `seq' y evaluates x to 'weak head normal form' when y must be evaluated. Evaluating to WHNF means evaluating to the outermost constructor (or lambda), in this case it means the pair (fst last, snd last +1) is evaluated only so far to determine that the outermost constructor is (,) - which means the components remain completely unevaluated and your function constructs a result of the form (((...(0 + 1)...+ 1) + 1), ((...(0 + 1)...+ 1) + 1)) which obviously is't what you really want. What you want is the evaluation of the pair's components, a simple and portable way would be countOdd' (x:xs) (evenCount, oddCount) = evenCount `seq` oddCount `seq` if odd x then ... or, to avoid unnecessary seq'ing, countOdd' (x:xs) (evenCount, oddCount) | odd x = let oc = oddCount + 1 in oc `seq` countOdd' xs (evenCount,oc) | otherwise = let ec = evenCount + 1 in ec `seq` countOdd' xs (ec,oddCount) When using GHC, it's more convenient to write it using bang-patterns: countOdd' (x:xs) (!ec, !oc) | odd x = countOdd' xs (ec, oc+1) | otherwise = countOdd' xs (ec+1,oc)
else countOdd' xs $! (fst last + 1, snd last) countOdd' [] last = last
{- Working tail recursion -}
countOdd2 :: [Int] -> Int countOdd2 lst = countOdd2' lst 0
countOdd2' :: [Int] -> Int -> Int countOdd2' (x:xs) last = if odd x then countOdd2' xs $! last + 1 else countOdd2' xs last countOdd2' [] last = last
The tail recursion in the function *countOdd2 *works fine.
You're evaluating an Int here to WHNF. For Ints, evaluation to WHNF is complete evaluation.
But it seems not to work in *countOdd *because i get a*Stack space overflow *error. Can anyone rewrite *countOdd *so that it works without a Stack space overflow?
Thank you.
Cheers Sebastian Arndt