[Haskell-beginners] Tail recursion problem

20 Feb 2011

      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)
                                 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. 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