Развертывание непустых структур в списках

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-алгебр, но не 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

Вы ответили на свой вопрос: эта операция, естественно, структурирована как апоморфизм, а не анаморфизм.

Вы можете, конечно, реализовать 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