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。