cataM 的评估顺序
Order of evaluation for cataM
在下面的代码中,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"])
听起来你在找 topDownCataM
的功能,这个功能也是 Matryoshka 提供的。
在下面的代码中,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"])
听起来你在找 topDownCataM
的功能,这个功能也是 Matryoshka 提供的。