cataM 的评估顺序

Question

在下面的代码中，cataM 如何自上而下（而不是像当前那样自下而上）遍历树？

我想我应该以不同的方式实现 foldMap 但是如何在子节点之前处理 branch 节点本身，因为 branch 没有 t 的实例，它们不是子节点？

module Catatree where

import Data.Foldable
import Data.Traversable
import Data.Monoid
import Data.Generic
import Prelude
import Control.Monad.Writer
import Control.Monad.Eff (Eff)
import Control.Monad.Eff.Console (CONSOLE, log, logShow)

import Data.Functor.Mu (Mu)
import Matryoshka (class Corecursive, class Recursive, Algebra, AlgebraM, cata, embed, cataM, project)

data TreeF a t = Leaf | Branch a (Array t)

type IntTree = Mu (TreeF Int)

derive instance treeGeneric :: (Generic a, Generic t) => Generic (TreeF a t)
derive instance treeFunctor :: Functor (TreeF a)

instance showTree :: (Generic a, Generic t) => Show (TreeF a t) where
  show = gShow

instance treeTraversable :: Traversable (TreeF a) where
  -- traverse :: forall a b m. Applicative m => (a -> m b) -> t a -> m (t b)
  traverse f Leaf = pure Leaf
  traverse f (Branch a children) = Branch a <$> traverse f children
  sequence f = sequenceDefault f


instance treeFoldable :: Foldable (TreeF a) where
  foldr f = foldrDefault f
  foldl f = foldlDefault f
  -- foldMap :: forall a m. Monoid m => (a -> m) -> f a -> m
  foldMap f Leaf = mempty
  foldMap f (Branch a children) = foldMap f children

evalM :: AlgebraM (Writer (Array String)) (TreeF Int) Int
evalM Leaf = do
  tell $ [ "visiting leaf " ]
  pure 4
evalM (Branch a children) = do
  tell $ [ "visiting branch " <> show a ]
  pure 2

runM :: forall t. Recursive t (TreeF Int) => t -> Writer (Array String) Int
runM = cataM evalM

branch :: forall t. Corecursive t (TreeF Int) => Int -> Array t -> t
branch i children = embed (Branch i children)

exp :: IntTree
exp = branch 3 [(branch 1 []), (branch 2 [])]

main :: forall eff. Eff (console :: CONSOLE | eff) Unit
main = do
  logShow $ runWriter $ runM exp
  -- outputs (Tuple 2 ["visiting branch 1","visiting branch 2","visiting branch 3"])

Answer 1

听起来你在找 topDownCataM 的功能，这个功能也是 Matryoshka 提供的。

cataM 的评估顺序

Order of evaluation for cataM

catamorphism

purescript

recursion-schemes