[Haskell-cafe] Bifold: a simultaneous foldr and foldl

Henning Thielemann lemming at henning-thielemann.de
Tue Dec 7 19:36:36 CET 2010

Noah Easterly wrote:
> Somebody suggested I post this here if I wanted feedback.
> So I was thinking about the ReverseState monad I saw mentioned on r/haskell a 
> couple days ago, and playing around with the concept of information flowing 
> two directions when I came up with this function:
> bifold :: (l -> a -> r -> (r,l)) -> (l,r) -> [a] -> (r,l)
> bifold _ (l,r) [] = (r,l)
> bifold f (l,r) (a:as) = (ra,las)
>  where (ras,las) = bifold f (la,r) as
>          (ra,la) = f l a ras
> (I'm sure someone else has come up with this before, so I'll just say I 
> discovered it, not invented it).
> Basically, it's a simultaneous left and right fold, passing one value from 
> the start of the list toward the end, and one from the end toward the start.

I also needed a bidirectional fold in the past. See foldl'r in

You can express it using foldr alone, since 'foldl' can be written as 'foldr':

You may add your example to the Wiki.

More information about the Haskell-Cafe mailing list