1

在下面的代码中，如何让 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"])
4

1 回答 1

1

听起来您正在寻找topDownCataM同样由 Matryoshka 提供的功能。

于 2017-04-27T13:26:24.373 回答