Friday, 15 June 2012

Unfolding with View Patterns

A while back I across a way of looking at fold / unfold duality which I've not seen anywhere else. It makes use of view patterns to highlight the symmetry in the implementation of the two combinators.

Firstly, for reference, the standard implementation:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f b [] = b
foldr f b (x : xs) = f x $ foldr f b xs
Then we rewrite the inputs slightly:

foldr3 :: (() -> b,(a,b) -> b) -> [a] -> b
foldr3 (b,f) [] = b ()
foldr3 (b,f) (x : xs) = f (x, foldr3 (b,f) xs)
...and rewrite them a little more...:
-- | (+) -| Delta    (Coproduct bifunctor is left adjoint to Diagonal functor)
foldr4 :: (Either () (a,b) -> b) -> [a] -> b
foldr4 f       [] = f $ Left  ()
foldr4 f (x : xs) = f $ Right (x, foldr4 f xs) we can create 'unfoldr' just by swapping the LHS and RHS of the definitions of 'foldr4':
-- | Now just swap the LHS and RHS of the '=' !!!
unfoldr2 :: (b -> Either () (a,b)) -> b -> [a]
unfoldr2 f (f -> Left  ()                   ) = []
unfoldr2 f (f -> Right (x, unfoldr2 f -> xs)) = (x : xs)


Oleksandr Manzyuk said...

Neat! Also generalizes to arbitrary catamorphisms / anamorphisms:

Fix f = In { out :: f (Fix f) }

cata :: (f a -> a) -> Fix f -> a
cata f (In x) = f $ fmap (cata f) x

ana :: (a -> f a) -> a -> Fix f
ana f (f -> (fmap (ana f) -> x)) = In x

winterkoninkje said...

This is, in fact, the standard presentation of cata-/anamorphisms, and is why we call them duals of one another. Note that there's also a change from using the least fixed-point (in cata) and the greatest fixed-point (in ana); these two fixedpoints just happen to coincide in Haskell.

That foldr/unfoldr have the types they do is mostly just to make things look simpler by compiling away the intermediate data structures.

Ben said...

Actually, I think the standard presentation is more like Oleksandr's abstracting and using the base functor directly.

It's the View Pattern way of looking at the underlying categorical duality that I was trying to draw attention to.