Is the following function tail call optmized?

Question

I am new to haskell (first time trying fn programming) and just trying out various exercises from "real world haskell" book. Can someone please correct me and tell if the below function is tail call optimized or not? If yes, then could you correct me how is it done? I am adding 1 to the recursive function so i believe this should throw a stackoverflow exception?

I tried calling myLength [1..2000000] but it didn't throw any stackoverflow exception

myLength (x:xs) = 1 + myLength(xs) 
myLength [] = 0

Answer 1

GHC can likely optimize this to be tail-call recursive, but the way you've written it is not. In order to be tail-call recursive, the "top" function in the tree has to be the recursive call. When I run your code in GHCi with [1..20000000000000], it runs out of memory with a segmentation fault, so it will not work for very large inputs.

If we re-arrange your definition a bit, I think it'll make it a bit more clear as to why it isn't TCR:

myLength (x:xs) =
    (+)
        1
        (myLength xs)
myLength [] = 0

Here I've broken it down into what is essentially a tree, and could be represented like

        (+)
       /   \
      /     \
     1     myLength
              \
               xs

So as you can see, the last function to be called in this tree is (+), not myLength. To fix this, you can use the fold pattern:

myLength = go 0
    where
        go acc (x:xs) = go (1 + acc) xs
        go acc []     = acc

And now the tree looks like

             go
           /    \
         (+)     xs
        /   \
       1    acc

So the top function in the tree is go, which is the recursive call. Alternatively, you can use a built-in fold to implement this. To keep from building up a lot of thunks, my recommendation would be to use foldl' from Data.List:

myLength = foldl' (\acc x -> acc + 1) 0

And while this may take a very long time to execute, it will not blow up the stack nor will it build up thunks that eat up RAM.

---

But as @DonStewart says, the compiler has a fair amount of freedom in re-arranging your code during optimizations.

Answer 2

Naively, this uses the stack. But the language doesn't specific the operational semantics, so a compiler is free to reorder things as long as it doesn't change the observed strictness.