[Haskell-beginners] Tail recursion problem

Sebastian Arndt sebarndt at web.de
Sun Feb 20 16:42:28 CET 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)
                                     countOdd' xs $! (fst last + 1, snd 
     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
                                     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 

Thank you.

Sebastian Arndt

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20110220/50c74ac3/attachment.htm>

More information about the Beginners mailing list