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
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