Firstly, for reference, the standard implementation:

foldr :: (a -> b -> b) -> b -> [a] -> bThen we rewrite the inputs slightly:

foldr f b [] = b

foldr f b (x : xs) = f x $ foldr f b xs

...and rewrite them a little more...:

foldr3 :: (() -> b,(a,b) -> b) -> [a] -> b

foldr3 (b,f) [] = b ()

foldr3 (b,f) (x : xs) = f (x, foldr3 (b,f) xs)

-- | (+) -| 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)

## 3 comments:

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

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.

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.

Post a Comment