haskell - 如何实现变形，使其可以建立在返回类型的任何值上(而不仅仅是基本情况)

Question

我的变形定义如下:

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

我目前必须像这样编写 Coalgebra:

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

我可以在其中返回我“早”构建的类型的值。

Answer 1

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