CODEWITHSUNDEEP
haskellrecursiontail-recursion
Rohit Sharma
Rohit Sharma

Reputation: 6500

Is the following function tail call optmized?

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

Upvotes: 3

Views: 189

Answers (4)

Random Dev
Random Dev

Reputation: 52300

no, this is not a tail-calling function (the last call in the non-empty list case will be + but this is not a big deal in Haskell (see here for some details).

So you don't need to restructure it but if you want you can do it with an accumulator:

myLength :: [a] -> Int
myLength = myLength' 0
  where myLength' acc [] = acc
        myLength' acc (_:xs) = myLength' (acc+1) xs

if we want to make Carl (a bit more) happy we can get rid of some thunks (without overcomplicating it to much - or so I think , I'm not that good when it comes to lazyness in Haskell, sorry):

myLength :: [a] -> Int
myLength = myLength' 0
  where myLength' acc []     = acc
        myLength' acc xs     = let acc' = acc+1
                               in seq acc' $ myLength' acc' (tail xs)

Upvotes: 1

bheklilr
bheklilr

Reputation: 54078

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.

Upvotes: 7

Carl
Carl

Reputation: 27023

Tail call elimination is automatic in GHC (you don't mention what compiler you're using, so I'll assume the most common) because of the calling convention GHC uses. But you have to be very wary of what the tail call actually is. In your definition, the tail call is (+).

As far as I know, GHC doesn't have any optimizations that will change that to a more memory-efficient form, and I suspect @Ferruccio 's comment is on to something.

Upvotes: 0

Don Stewart
Don Stewart

Reputation: 138007

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.

Upvotes: 4

Related Questions