Menu
I wrote this snippet of code and I assume len is tail-recursive, but a stack overflow still occurs. What is wrong?
myLength :: [a] -> Integer myLength xs = len xs 0 where len [] l = l len (x:xs) l = len xs (l+1) main = print $ myLength [1..10000000] 
807
Note that foldl is tail recursive. The important concept to know in Haskell is guarded recursion (see tail recursion modulo cons), where any recursive calls occur within a data constructor (such as foldr , where the recursive call to foldr occurs as an argument to (:) ).
The base case for numeric recursion usually consists of one or more specific numbers (often 0 or 1) for which the answer can be immediately given. The recursive case computes the result by calling the function recursively with a smaller argument and using the result in some manner to produce the final answer.
In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of (return (recursive-function params)) .
The tail recursion is basically using the recursive function as the last statement of the function. So when nothing is left to do after coming back from the recursive call, that is called tail recursion.
Remember that Haskell is lazy. Your computation (l+1) will not occur until it's absolutely necessary.
The 'easy' fix is to use '$!' to force evaluation:
myLength :: [a] -> Integer myLength xs = len xs 0 where len [] l = l len (x:xs) l = len xs $! (l+1) main = print $ myLength [1..10000000] Seems like laziness causes len to build thunk:
len [1..100000] 0 -> len [2..100000] (0+1) -> len [3..100000] (0+1+1) and so on. You must force len to reduce l every time:
len (x:xs) l = l `seq` len xs (l+1) For more information, look http://haskell.org/haskellwiki/Stack_overflow.
34
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
