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 fol

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_swift/ http://tel.github.io/2014/07/30/immutable_enumeration_in_swi...