Is an optional tail function call being called?
I am new to haskell (first time trying to program fn) and just tried various exercises from the "realkelkell" book. Can someone please correct me and tell me if the function below is optimized or not? If so, can you please correct me how it is done? I am adding 1 to the recursive function, so I believe this should throw a stackoverflow exception?
I tried to call myLength [1..2000000] but didn't throw an exception from stackoverflow
myLength (x:xs) = 1 + myLength(xs)
myLength [] = 0
source to share
GHC can probably optimize this to be recursive, but the way you wrote it is not. To be a recursive tail, the "top" function in the tree must be a recursive call. When I run your code in GHCi with [1..20000000000000]
it runs out of memory with a segmentation fault, so it won't work for very large inputs.
If we change your definition a bit, I think it will be a little more clear why this is not a TCR:
myLength (x:xs) =
(+)
1
(myLength xs)
myLength [] = 0
Here I have broken it down into what is essentially a tree and can be represented as
(+) / \ / \ 1 myLength \ xs
So, as you can see, the last function called in this tree is (+)
, not myLength
. To fix this, you can use the addition 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 go
, which is a recursive call. Alternatively, you can use the built-in fold to implement it. In order not to build up a lot of tricks, I would recommend using foldl'
from Data.List
:
myLength = foldl' (\acc x -> acc + 1) 0
And while it can take a very long time, it won't explode on the stack and create bulky tomatoes that eat RAM.
But as @DonStewart says, the compiler has a fair amount of freedom to re-tune your code during optimization.
source to share
no, this is not a tail call function (the last call in the case of a non-empty list would be +
, but that doesn't really matter 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 Karl (a little more) happy, we can get rid of some tricks (without too many of them - or so I think I'm not that good when it comes to laziness 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)
source to share
In GHC, auto-elimination of the tail is automatic (you will not tell which compiler you are using, so I will consider the most common) due to the use of the GHC convention. But you have to be very careful about what the tail actually means. In your definition, a tail call (+)
.
As far as I know, GHC does not have any optimizations that would change this to a more memory-efficient form, and I suspect @ Ferruccio's comment on something.
source to share