[Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?

Chaddaï Fouché chaddai.fouche at gmail.com
Sat Aug 18 16:03:23 EDT 2007

> foo n = if n<0 then [] else n : foo (n-1)
> bar n = aux 0 [] where
>   aux i xs = if i>n then xs else aux (i+1) (i:xs)
> that foo is more efficient than bar because lazy evaluation of foo just puts
> the delayed computation in the "cdr" of the list, while lazy evaluation of
> bar has to keep track of all aux calls (the "closures") which gives much
> more overhead, maybe even stack overflow? Something like that?

There is absolutely no problem with bar, it will not stack overflow
since it _is_ tail-recursive _and_ the comparison i > n force the
evaluation of i avoiding the risk of constructing a too big thunk for
the first parameter of aux which could bring a stack overflow like in
this example :
nonStrictLength n [] = n
nonStrictLength n (_:xs) = nonStrictLength (n+1) xs

(try nonStrictLength 0 [1..10000000] in GHCi to see the stack
overflow, GHC strictness analysis would avoid the problem with -O)

Though foo is still more interesting than bar since it will work on
infinite list, bar is too strict.


More information about the Haskell-Cafe mailing list