Search code examples
haskellrecursion-schemes

How to implement an anamorphism such that it can be build upon any value of the the return type (rather than just the base case)

I've got anamorphism defined as follows:

-- Fixed point of a Functor 
newtype Fix f = In (f (Fix f))

deriving instance (Eq (f (Fix f))) => Eq (Fix f)
deriving instance (Ord (f (Fix f))) => Ord (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

I currently have to write a Coalgebra like this:

appendListCoAlg :: (ListF' a, ListF' a) -> ListF a (ListF' a, ListF' a)
appendListCoAlg (In (ConsF a as), listb) = ConsF a (as, listb)
appendListCoAlg (In NilF, In (ConsF b bs)) = ConsF b (In NilF, bs)
appendListCoAlg (In NilF, In NilF) = NilF

Here, an anamorphism has to be constructed from the "base case" (NilF).

I'm interested in whether it is possible to write ana such that I can do something list this:

appendListCoAlg :: (ListF' a, ListF' a) -> ?
appendListCoAlg (In (ConsF a as), listb) = ConsF a (as, listb)
appendListCoAlg (In NilF, **bs**) = **bs**
appendListCoAlg (In NilF, In NilF) = NilF

where I can return a value of type I'm constructing "early".

Solution

  • ana does not let you do that. You can use apo instead (although it's still not as neat as it could be; the Either should really be outside).

    apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t

    appendListCoAlg :: [a] -> [a] -> ListF a (Either [a] [a])
appendListCoAlg listb (a : as) = ConsF a (Right as)  -- Right: continue unfolding
appendListCoAlg listb [] = Left <$> project listb    -- Left: stop unfolding

    append :: [a] -> [a] -> [a]
append lista listb = apo (appendListCoAlg listb) lista