[Haskell-cafe] generalized, tail-recursive left fold that can finish tne computation prematurely

[Roman Cheplyaka]

* oleg at okmij.org <oleg at okmij.org> [2013-02-19 06:27:10-0000]
> 
> As others have pointed out, _in principle_, foldr is not at all
> deficient. We can, for example, express foldl via foldr. Moreover, we
> can express head, tail, take, drop and even zipWith through
> foldr. That is, the entire list processing library can be written in
> terms of foldr:
> 
>         http://okmij.org/ftp/Algorithms.html#zip-folds
> 
> That said, to express foldl via foldr, we need a higher-order
> fold. There are various problems with higher-order folds, related to
> the cost of building closures. The problems are especially severe 
> in strict languages or strict contexts. Indeed,
> 
> foldl_via_foldr f z l = foldr (\e a z -> a (f z e)) id l z
> 
> first constructs the closure and then applies it to z. The closure has
> the same structure as the list -- it is isomorphic to the
> list. However, the closure representation of a list takes typically
> quite more space than the list. So, in strict languages, expressing
> foldl via foldr is a really bad idea. It won't work for big lists.

If we unroll foldr once (assuming l is not empty), we'll get

  \z -> foldr (\e a z -> a (f z e)) id (tail l) (f z (head l))

which is a (shallow) closure. In order to observe what you describe (a
closure isomorphic to the list) we'd need a language which does
reductions inside closures.

Am I wrong?

Roman