haskell - トラバース可能な F 代数が認められたとして、適用代数上でカタモルフィズムを持つことは可能ですか?

Question

この F 代数 (前の質問で紹介) があり、それに効果的な代数を適用したいと考えています。必死の試行錯誤の末、機能するモナドカタモルフィズムをまとめることができました。アプリケーションに一般化できるのではないかと思います。そうでない場合は、なぜですか。

これは私が定義した方法ですTraversable：

instance Traversable Expr where
    traverse f (Branch xs) = fmap Branch $ traverse f xs
    traverse f (Leaf   i ) = pure $ Leaf i

これは単項カタモルフィズムです:

type AlgebraM a f b = a b -> f b

cataM :: (Monad f, Traversable a) => AlgebraM a f b -> Fix a -> f b
cataM f x = f =<< (traverse (cataM f) . unFix $ x)

そして、これがどのように機能するかです：

λ let printAndReturn x = print x >> pure x
λ cataM (printAndReturn . evalSum) $ branch [branch [leaf 1, leaf 2], leaf 3]
1
2
3
3
6
6

私の考えは、次のように書き直すことができるということです。

cataA :: (Applicative f, Traversable a) => AlgebraM a f b -> Fix a -> f b
cataA f x = do
    subtree <- traverse (cataA f) . unFix $ x
    value <- f subtree
    return value

残念ながら、ここではapplicative do-notation に関する論文にvalue依存してsubtreeおり、そのような場合、Applicative に desugar することはできません。これを回避する方法はないようです。ネストの深さから浮かび上がるモナドが必要です。

本当ですか？アプリケーション効果のみで折り畳めるのはフラットな構造のみであると結論付けてよいでしょうか?