Working on a project and trying to write longzip using an anamorphism. I'm having some trouble writing a coalgebra for this use case. I've defined my anamorphism in terms of Fix
below:
-- Fixed point of a Functor
newtype Fix f = In (f (Fix f))
deriving instance (Eq (f (Fix f))) => Eq (Fix f)
out :: Fix f -> f (Fix f)
out (In f) = f
-- Anamorphism
type Coalgebra f a = a -> f a
ana :: (Functor f) => Coalgebra f a -> a -> Fix f
ana f = In . fmap (ana f) . f
This is the definition for ana
derived from "reversing the arrows" of cata:
-- Catamorphism
type Algebra f a = f a -> a
cata :: (Functor f) => Algebra f a -> Fix f -> a
cata f = f . fmap (cata f) . out
I've seen zip
written using a version of ana that is obviously defined differently (takes a predicate as a parameter):
zip2 = ana unsp fin
where
fin (as,bs) = (as==[]) || (bs ==[])
unsp ((a:as), (b:bs)) = ((a,b),(as,bs))
(Taken from https://en.wikipedia.org/wiki/Anamorphism)
But I'm unsure how to move forward using the version of ana
defined above, particularly in regards to writing a Coalgebra
of type a -> fa
. Like, would it have to take the two list parameters to zip
and combine them into a single a
?
CodePudding user response:
First off, give yourself a starting point. Actually write down what you're going to do:
-- make this example actually complete
{-# Language StandaloneDeriving, UndecidableInstances, DeriveFunctor #-}
import Prelude hiding (zip)
-- Fixed point of a Functor
newtype Fix f = In (f (Fix f))
deriving instance (Eq (f (Fix f))) => Eq (Fix f)
deriving instance (Show (f (Fix f))) => Show (Fix f)
out :: Fix f -> f (Fix f)
out (In f) = f
-- Anamorphism
type Coalgebra f a = a -> f a
ana :: (Functor f) => Coalgebra f a -> a -> Fix f
ana f = In . fmap (ana f) . f
-- Base functor for a list
data ListF a f = Nil | Cons a f deriving (Eq, Show, Functor)
type List a = Fix (ListF a)
-- write down the type. It helps you think about things
zip :: List a -> List b -> List (a, b)
zip x y = ana undefined undefined
You know zip
has to be implemented as a call to ana
, so what remains is figuring out the seed and the coalgebra. It should be fairly clear the seed needs to contain x
and y
. It doesn't seem like any further information should be necessary, so let's just assume the seed will be (x, y)
until/unless it poses a problem. That's enough information to pin down the types:
zip :: List a -> List b -> List (a, b)
zip x y = ana zipCoalgebra (x, y)
zipCoalgebra :: (List a, List b) -> ListF (a, b) (List a, List b)
zipCoalgebra = undefined
I feel like this is the step you've missed: actually writing down what you're trying to do and following the types to pin down what you need. The rest of this is sort of trivial if you've ever seen any implementation of zip
. It's just a matter of writing down the obvious thing that type-checks (paying close attention to the difference between List
and ListF
in the type). I strongly recommend you stop reading here and give it a try yourself. There isn't much else I can say that's actually helpful for learning how to think about this.
If you really have no idea at all:
zipCoalgebra :: (List a, List b) -> ListF (a, b) (List a, List b)
zipCoalgebra (In (Cons a as), In (Cons b bs)) = Cons (a, b) (as, bs)
zipCoalgebra _ = Nil
It really is exactly what you'd expect if you've ever seen an implementation of zip
before, with the necessary noise to make it type-check around Fix
. Let's give it a spin:
ghci> zip (In (Cons 1 (In Nil))) (In Nil)
In Nil
ghci> zip (In (Cons 1 (In Nil))) (In (Cons 2 (In Nil)))
In (Cons (1,2) (In Nil))
Yep. Behaving as expected. It seems the two lists were sufficient as the seed, and all is well.