# 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
``````