将非空结构展开到列表

Question

我想Foldable.toList使用变形来编写一个非空的玫瑰树,但似乎不可能提取最后一个元素:

import Data.Functor.Foldable

data RoseTree a = RoseNode a [RoseTree a]

ana5 :: RoseTree a -> [a]
ana5 = ana coalg5

coalg5 :: RoseTree a -> ListF a (RoseTree a)
coalg5 (RoseNode a []) = Nil
coalg5 (RoseNode a (RoseNode b1 b2:t)) = Cons a $ RoseNode b1 (b2 ++ t)

它确实是不可能的,它是否适用于所有非空结构？

另外(它是一种可选的奖励问题)是否有一般规则来确定何时Fix f -> Fix g可以使用f-algebras而不是g-coalgebras实现？

Btw apomorphism工作:

coalg6 (RoseNode a []) = Cons a $ Left []
coalg6 (RoseNode a (RoseNode b1 b2:t)) = Cons a $ Right $ RoseNode b1 (b2 ++ t)

apo coalg6具有相同的类型,ana5但不会丢失一个元素

Answer 1

你已经回答了你自己的问题：这个操作自然地被构造为非同构，而不是变形。

当然，您可以apo按照以下方式实施ana：

apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f
apo f = ana (either (fmap Left . unFix) f) . Right

para（我通过将“对偶化为cata”来想出这个： para f = snd . cata (Fix . fmap fst &&& f)。）

你可以将你的插入coalg6到这个并得到一个余代数，当给它时它会做同样的事情ana：

ana5 = ana coalg5 . Right
    where coalg5 = either (fmap Left . unFix) coalg6