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)

6 comments:

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

Anonymous 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

Divyarana
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

Cirali said...

Which means as Cirali Sharma may be the correct location wherever you'll obtain the many appealing escort in Ludhiana at an inexpensive cost you merely don’t need certainly to squander your useful period by phoning additional agencies. The girls will always be drawn to popularity, the cash and allure of the business. This really is among the main reasoned explanations why this occupation was chosen by each one of these top quality escorts girls in Ludhiana. Cirali
Ludhiana Escorts Service
Ludhiana Escort Service
Ludhiana call girls
Ludhiana Female Escorts
Ludhiana Female Escort
call girls in Ludhiana
Ludhiana Escorts Agency
Ludhiana Independent Escorts
Ludhiana Independent Escort
Escorts in Ludhiana
Escorts Service in Ludhiana
Escort Service in Ludhiana
VIP Escorts in Ludhiana
Independent Escorts in Ludhiana
Escorts in Ludhiana
Escorts Agency in Ludhiana
Escort Agency in Ludhiana
VIP Escort in Ludhiana
Ludhiana Escorts Services
Ludhiana escorts
Ludhiana escort