У меня есть анаморфизм, определенный следующим образом:
-- 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
В настоящее время мне нужно написать коалгебру следующим образом:
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
Здесь анаморфизм должен быть построен из «базового случая» (NilF).
Меня интересует, можно ли написать ana такое, что я могу сделать что-то перечислить это:
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
Где я могу вернуть значение типа, которое я создаю "рано".
Ana не позволяет вам сделать это. Вместо этого вы можете использовать apo (хотя это все еще не так аккуратно, как могло бы быть; Either действительно должен быть снаружи).
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
Да, и он страдает от той же проблемы, что и para использование cata выполнения избыточной работы.
Можно ли определить apo через ana так же, как para можно определить из cata?