[Haskell-cafe] why does a foldr not have a space leak effect?

[Ryan Ingram]

The difference is that foldl *must* produce the entire list of thunks, even
if f is lazy in its first argument.

There's no foldl that can perform better given a sufficiently-lazy f; given

head = foldr go fail where
    go x y = x
    fail = error "head: empty list"

head [a,b,c,d]
= foldr go fail [a,b,c,d]
= go a (foldr go fail [b,c,d])
= a

you might think you can define

last = foldl go fail where
    go x y = y
    fail = error "last: empty list"

but this fails to be sufficiently lazy:

last [a,b,c,d]
= foldl go fail [a,b,c,d]
= foldl go (go fail a) [b,c,d]
= foldl go (go (go fail a) b) [c,d]
= foldl go (go (go (go fail a) b) c) [d]
= foldl go (go (go (go (go fail a) b) c) d) []
= go (go (go (go fail a) b) c) d
= d

which allocates lots of extra space for thunks, which may even take more
memory than the original list.

Whereas if last uses foldl':

last [a,b,c,d]
= foldl' go fail [a,b,c,d]
= let z = go fail a in seq z $ foldl' go z [b,c,d]
= foldl' go a [b,c,d]
= let z = go a b in seq z $ foldl' go z [c,d]
= foldl' go b [c,d]
= ...
= let z = go c d in seq z $ foldl' go z []
= foldl' go d []
= d

  -- ryan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120730/710edec0/attachment.htm>