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