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

Ryan Ingram ryani.spam at gmail.com
Mon Jul 30 23:15:45 CEST 2012

```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"

= 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...