6

我想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 代数而不是 g 代数来实现？

顺便说一句，同构起作用了：

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

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

4

1 回答 1

2

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

当然，您可以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插进去，得到一个 coalgebra，它在给定时做同样的事情ana：

ana5 = ana coalg5 . Right
    where coalg5 = either (fmap Left . unFix) coalg6
于 2017-02-15T10:52:15.530 回答