Comment by tel

This sort of reminds me of the Church-encoded form of a list.

    newtype Fold a = Fold (forall r . (a -> r -> r) -> r -> r)

    fold :: [a] -> Fold a
    fold xs = Fold (spin xs) where
      spin []     cons nil = nil
      spin (a:as) cons nil = cons a (spin as cons nil)

    refold :: Fold a -> [a]
    refold (Fold f) = f (:) []

Notably, since `fold` and `refold` are isomorphisms then we can do everything we can do to `[a]` to `Fold a`

    map :: (a -> b) -> (Fold a -> Fold b)
    map x (Fold f) = Fold $ \cons nil -> f (cons . x) nil

    filter :: (a -> Bool) -> Fold a -> Fold a
    filter p (Fold f) =
      Fold $ \cons nil -> f (\a r -> if p a then cons a r else r) nil

but all of this work is done without concrete reference to `(:)` and `[]`... you instead just use stand-ins I've been calling cons and nil. What's nice about this is that `Fold` can be used to build anything which can be "constructed from the left"

    foldSet :: Fold a -> Set a
    foldSet (Fold f) = f Set.insert Set.empty

It's sort of dual to the stuff I was exploring in Swift here [0]. It also creates laziness for free because you can't really execute the chain until the end—Church-encoding is really a form of continuation passing.

The downside of this idea is that each time you "consume" a Fold you redo work—there's no place to put caching necessarily.

Maybe that's what they're solving with the Fold transformers representation.

[0] http://tel.github.io/2014/07/30/immutable_enumeration_in_swi...