bifold.hs

module BiFold where
import Prelude hiding (foldr, foldl)

-- http://d.hatena.ne.jp/nobsun/20100824/1282617326
bifold :: ((a, c) -> b -> (a, c)) -> (a, c) -> [b] -> (a, c)
bifold f (a, c) (b:bs) = (a'', c'')
  where (a', c'') = f (a, c') b
        (a'', c') = bifold f (a', c) bs
bifold _ z      _      = z

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z = snd . bifold g (undefined, z)
  where g (_, c) z = (undefined, f z c)
        
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z = fst . bifold g (z, undefined)
  where g (a, _) z = (f a z, undefined)