How to implement an anamorphism such that it can be build upon any value of the the return type (rat-CodePudding

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".

CodePudding user response：

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