Unfolding non-empty structures to lists

Question

I want to write Foldable.toList for a non-empty rose tree using an anamorphism, but it seems impossible to extract the last element:

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)

Is it indeed impossible and does it generalize to all non-empty structures?

Also (it's sort of an optional bonus question) is there a general rule to determine when Fix f -> Fix g can be implemented using f-algebras but not g-coalgebras?

Btw apomorphism worked:

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

apo coalg6 has the same type as ana5 but doesn't lose one element

Dambrosio

Answer 1

You've answered your own question: this operation is naturally structured as an apomorphism, not an anamorphism.

You can, of course, implement apo in terms of ana:

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

(I came up with this by dualising "para in terms of cata": para f = snd . cata (Fix . fmap fst &&& f).)

You can just plug your coalg6 into this and get a coalgebra which does the same thing when given to ana:

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

Sheik