How does Haskell tail recursion work?

haskell tail-recursion
Hynek -Pichi- Vychodil picture Hynek -Pichi- Vychodil · Jan 5, 2009 · Viewed 9.4k times · Source

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]

Answer

eelco picture eelco · Jan 5, 2009

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]

Related questions

Does Haskell have tail-recursive optimization?

I discovered the "time" command in unix today and thought I'd use it to check the difference in runtimes between tail-recursive and normal recursive functions in Haskell. I wrote the following functions: --tail recursive fac :: (Integral a) => a -&…

Read More
foldl is tail recursive, so how come foldr runs faster than foldl?

I wanted to test foldl vs foldr. From what I've seen you should use foldl over foldr when ever you can due to tail reccursion optimization. This makes sense. However, after running this test I am confused: foldr (takes 0.057s …

Read More
Tail Recursion in Haskell

I am trying to understand tail-recursion in Haskell. I think I understand what it is and how it works but I'd like to make sure I am not messing things up. Here is the "standard" factorial definition: factorial 1 = 1 factorial k = …

Read More