Is it possible to implement foldl/foldr using unsided fold?

Question

By unsided fold, I mean a hypothetic primitive fold operation for associative operators that, does not guarantee any ordering. That is, (fold + 0 [a b c d]) could be (+ (+ a b) (+ c d)) or (+ (+ (+ a b) c) d).

Given that this operation is fusionable, highly paralelizable and universal, I've thought in including it together with map and concat as the only list primitives for my non-recursive minimalist language. I've managed to implement most list functions with it, but not the sided folds foldl/foldrthemselves. Is it possible?

Answer 1

If you have fold and map that is universal. The slogan here is foldr is made of monoids In fact, the standard haskell typeclass Foldable implements foldr and foldl in just this way

The trick is that the set of endomorphisms over a set forms a monoid under function composition with the identity function as the identity.

Note though that foldr and foldl are inherently sequential. So, this trick has to give up any parallelism you have in your implementation of fold and map. Essentially, the encoding of foldr into foldMap is the encoding of a delayed sequential computation into a potentially unordered one. That is why I encourage the use of foldMap over foldr when possible--it supports implicit parallism when that is possible, but is equivalent in expressive power.

EDIT: Putting everything in one place

We define the set of endo morphisms over a

newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
    mempty = Endo id
    Endo f `mappend` Endo g = Endo (f . g)

then in foldable, we see the definition for foldr

foldr f z t = appEndo (foldMap (Endo . f) t) z

this uses foldMap which has type Monoid m => (a -> m) -> t a -> m (where t is the collection we are folding over, we can pretend it is a list from now on giving Monoid m => (a -> m) -> [a] -> m and is equivalent to

foldMap f ls = fold (map f ls)

where fold is the monoid fold. If you have a unordered fold called fold' :: (a -> a -> a) -> a -> [a] -> a then that is just

fold = fold' mappend mempty

so

foldr f z t = appEndo (foldMap (Endo . f) t) z
 = appEndo (fold (map (Endo . f) t)) z
 = appEndo (fold' mappend mempty (map (Endo . f) t)) z
 = appEndo (fold' (\(Endo f) (Endo g) -> Endo (f . g) (Endo id) (map (Endo . f) t)) z

which can be further simplified to

foldr f z t = (fold' (.) id (map f t)) z

and dropping the unecessary parens

foldr f z t = fold' (.) id (map f t) z

which is what Daniel Wagner gave as his answer. You can implement foldl in a similar way, or via foldr.

Answer 2

foldr f z xs = fold (.) id (map f xs) z

For example, in ghci:

*Dmwit Debug.SimpleReflect> let foldr' f z xs = foldb (.) id (map f xs) z
*Dmwit Debug.SimpleReflect> foldr' f z [w,x,y]
f w (f x (f y z))
*Dmwit Debug.SimpleReflect> foldr f z [w,x,y]
f w (f x (f y z))