If you have fold and map , that is universal. The slogan here is foldr made of monoids. In fact, the standard haskell typeclass Foldable implements foldr and foldl in this way.
The trick is that the set of endomorphisms over the set forms a monoid in the composition of functions with an identical function as an identity.
Note that foldr and foldl are inherently consistent. So, this trick should discard any parallelism that you have when implementing fold and map . Essentially, the foldMap coding in foldMap is the encoding of a deferred sequential calculation to a potentially unordered one. That's why I recommend using foldMap by foldr when possible - it supports implicit parallelism when possible, but equivalent to expressive power.
EDIT: All in one place
Define the set of endomorphisms 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 folding we see a definition for foldr
foldr fzt = appEndo (foldMap (Endo . f) t) z
this uses foldMap , which has type Monoid m => (a -> m) -> ta -> m (where t is the collection we are adding, we can pretend that now it is a list giving Monoid m => (a -> m) -> [a] -> m and equivalent
foldMap f ls = fold (map f ls)
where fold is the monoid fold. If you have an unordered fold fold' :: (a -> a -> a) -> a -> [a] -> a , then it's simple
fold = fold' mappend mempty
So
foldr fzt = 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 fzt = (fold' (.) id (map ft)) z
and reset unnecessary partners
foldr fzt = fold' (.) id (map ft) z
what Daniel Wagner gave as an answer. You can implement foldl same way or through foldr .