[Haskell-cafe] Re: Re: Definition of "tail recursive" wrt Folds

Ben Franksen ben.franksen at online.de
Wed Apr 1 18:07:20 EDT 2009

Bertram Felgenhauer wrote:
> Ben Franksen wrote:
>> Mark Spezzano wrote:
>> > Just looking at the definitions for foldr and foldl I see that foldl is
>> > (apparently) tail recursive while foldr is not.
>> The point is that foldr still needs to do something (namely to apply  (y
>> `k`)) to the result of applying itself. It needs to remember to do so,
>> and thus the stack grows linearly with the size of the list.
> Sorry, but that's wrong. It would be right in a strict language. In
> [...snip...]

Thanks very much for this very nice explanation. I was aware that what I
wrote is not the whole truth in a lazy language. Indeed I hoped someone
else would explain the finer points better than I could. I was right. ;-)


More information about the Haskell-Cafe mailing list