CODEWITHSUNDEEP
haskellrecursion-schemes
cocorudeboy
cocorudeboy

Reputation: 141

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

Upvotes: 3

Views: 132

Answers (1)

Li-yao Xia
Li-yao Xia

Reputation: 33569

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

Upvotes: 2

Related Questions