将非空结构展开为列表

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)

它真的不可能吗？它是否泛化到所有非空结构？

此外（这是一个可选的奖励问题）是否有一般规则来确定何时可以使用 f-代数而不是 g-coalgebras 来实现 Fix f -> Fix g？

顺便说一句同构有效：

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

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

当然，您可以根据 ana:

实施 apo

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 插入这个并得到一个 coalgebra 给 ana 做同样的事情:

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

将非空结构展开为列表

Unfolding non-empty structures to lists

haskell

recursion-schemes

corecursion