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)


...now 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)