[Haskell-beginners] Tail recursion problem

[Daniel Fischer]

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