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.

Sabina Khan said...

I am offering high profile Hyderabad Escorts in your city Hyderabad at your affordable rate.if you are searching for beautiful escorts then you can contact me.

Sandeep saini said...

We're again using most services that are enormous to fulfill sex requirements and your bodily. We the well known manufacturer recognized for the greatest Club therapy services, and that proceeding the marketplace correctly as well as escort club Ludhiana escorts

Ludhiana Escorts Service
Ludhiana Escort Service
Ludhiana call girls
Ludhiana Female Escorts
call girls in Ludhiana
Ludhiana Escorts Agency
Ludhiana Independent Escorts
Escorts in Ludhiana
Escorts Service in Ludhiana
VIP Escorts in Ludhiana
Independent Escorts in Ludhiana
Escorts in Ludhiana
Escorts Agency in Ludhiana
VIP Escort in Ludhiana
Ludhiana Escorts Services
Ludhiana escorts
Ludhiana escort
escorts in Ludhiana
Ludhiana escorts
Ludhiana escort service
Ludhiana escorts service
escort in Ludhiana