This library defines a simple newtype

newtype Folding f m a = Folding {getFolding::
     forall r. (f r -> r) -> (m r -> r) -> a -> r}

which wraps and generalizes the unwrapped type GHC uses to optimize Data.List

forall r . (a -> r -> r) -> r -> r

which is equivalent to

Folding ((,) a) Identity ()

This library defines a Prelude of functions on Folding especially Folding (Of a) m r and proposes a number of bytestring and other such things. The hope is to employ this type for a fairly straightforward optimization of a number of types of the ListT and Producer sort, using the almost-correct equivalences

 Producer a m r ~ Folding ((,) a) m r
 FreeT f m r  ~ Folding f m r
 Series f m r ~ Folding f m r

and a number of potential others, e.g. LogicT, Conduit.Source, etc which are equivalent to Folding ((,) a) m (). The Series type defined here is an attempt at an optimized FreeT aimed at improving the pipes usage FreeT (Producer a m) m r and the like. (Some decisions have been made homogeneous with ertes's similarly motivated fuse package, which calls it FreeT replacement List; it may be more interesting.)

In each of the Preludes included here, operations with types like

 f_producer :: Producer a m r -> Producer b m z
 f_freet :: FreeT f m r -> FreeT g m s
 f_series :: Series (Of a) m r -> Series (Of b) m r
 f_list :: [a] -> [a]

are implemented as

 buildProducer . f_folding . foldProducer
 buildFreeT . f_folding . foldFreeT
 buildSeries . f_folding . foldSeries
 buildList . f_folding . foldList

where f_folding is the appropriate function of Foldings. The different Prelude s thus differ mostly by find-and-replace. Functions that enter or exit space of 'serial' types use only one of the fusion operators.

In each case the principal (only) "fusion" rule is of the form

 buildProducer (foldProducer phi) = phi
 buildFreeT (foldFreeT phi) = phi
 buildSeries (foldSeries phi) = phi
 buildList (foldList phi) = phi  

It may be that the resulting implementations are better at making it past the impediments of criterion, but some benchmarks on more and less complex compositions of functions f.g.h, with and without defintions via Folding, can be seen here:

The rest of the report is here. Lines marked 'f.g.h/FOLDING' bench compositions of functions defined through the fusion framework described above; those marked 'f.g.h' bench compositions of functions given ordinary definitions using the constructors or as they are exported by suitable libraries. Functions from Data.Vector.Unboxed are marked 'vector' and are included for comparison.

The benchmarks are pure and thus use Folding (Of a) Identity (), Series (Of a) Identity () and [a]. It is interesting that for these benchmarks, the present fusion framework is always faster than Data.List. It is also more reliable than both vector and Data.List (though vector is of course much faster where fusion succeeds.) But these cases are perhaps somewhat stylized, and in my experience criterion is a bit cruel to anything that requires specialization and other optimization. I am surprised though that so far the newtype = ]wrapping makes the fusion rules more reliable.

The real objective is to optimize pipes functions with types like

 lines :: Monad m 
       => Producer ByteString m r 
       -> FreeT (Producer ByteString m) m r

which introduce a certain perceptible clunkiness.