[Haskell-beginners] Tail recursion problem
Daniel Fischer
daniel.is.fischer at googlemail.com
Sun Feb 20 17:20:33 CET 2011
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
More information about the Beginners
mailing list