How does Haskell tail recursion work?
Solution 1:
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]
Solution 2:
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.
Solution 3:
The foldl carries the same problem; it builds a thunk. You can use foldl' from Data.List to avoid that problem:
import Data.List
myLength = foldl' (const.succ) 0
The only difference between foldl and foldl' is the strict accumulation, so foldl' solves the problem in the same way as the seq and $! examples above. (const.succ) here works the same as (\a b -> a+1), though succ has a less restrictive type.
Solution 4:
The simplest solution to your problem is turning on optimization.
I have your source in a file called tail.hs.
jmg$ ghc --make tail.hs -fforce-recomp [1 of 1] Compiling Main ( tail.hs, tail.o ) Linking tail ... jmg$ ./tail Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it. girard:haskell jmg$ ghc -O --make tail.hs -fforce-recomp [1 of 1] Compiling Main ( tail.hs, tail.o ) Linking tail ... jmg$ ./tail 10000000 jmg$
@Hynek -Pichi- Vychodil The tests above were done on Mac OS X Snow Leopard 64bit with a GHC 7 and GHC 6.12.1, each in a 32 bit version. After you're downvote, I repeated this experiment on Ubuntu Linux with the following result:
jmg@girard:/tmp$ cat length.hs 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] jmg@girard:/tmp$ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.12.1 jmg@girard:/tmp$ uname -a Linux girard 2.6.35-24-generic #42-Ubuntu SMP Thu Dec 2 02:41:37 UTC 2010 x86_64 GNU/Linux jmg@girard:/tmp$ ghc --make length.hs -fforce-recomp [1 of 1] Compiling Main ( length.hs, length.o ) Linking length ... jmg@girard:/tmp$ time ./length Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it. real 0m1.359s user 0m1.140s sys 0m0.210s jmg@girard:/tmp$ ghc -O --make length.hs -fforce-recomp [1 of 1] Compiling Main ( length.hs, length.o ) Linking length ... jmg@girard:/tmp$ time ./length 10000000 real 0m0.268s user 0m0.260s sys 0m0.000s jmg@girard:/tmp$
So, if you're interested we can continue to find out what is the reason, that this fails for you. I guess, GHC HQ, would accept it as a bug, if such a straight forward recursion over lists is not optimized into an efficient loop in this case.
Solution 5:
Just so you know, there's a much easier way to write this function:
myLength xs = foldl step 0 xs where step acc x = acc + 1
Alex