dépliage structures non vides aux listes

Question

Je veux écrire Foldable.toList pour un arbre rose non vide en utilisant un anamorphisme, mais il semble impossible d'extraire le dernier élément:

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) 

est-il en effet impossible et le fait généraliser à toutes les structures non vides? En outre (il s'agit en quelque sorte d'une question de bonus facultative) existe-t-il une règle générale pour déterminer quand Fix f -> Fix g peut être implémenté en utilisant des algèbres f mais pas des g-coalgebras?

BTW apomorphism travaillé:

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

apo coalg6 a le même type que ana5 mais ne perd pas un élément

Answer 1

Vous avez répondu à votre propre question: cette opération est naturellement structurée comme un apomorphism, pas un anamorphisme.

Vous pouvez, bien sûr, mettre en œuvre apo en termes de ana:

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

(je suis venu avec ce par dualisant "para en termes de cata". para f = snd . cata (Fix . fmap fst &&& f))

Vous pouvez juste branchez votre coalg6 dans ceci et obtenez un coalgebra qui fait la même chose quand donné à ana:

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