* o...@okmij.org <o...@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
