Haskell通过深度优先顺序遍历标记二叉树

Question

我需要通过深度优先顺序遍历来标记二叉树,因此我认为我需要首先遍历树的左侧分支并标记它们,然后对正确的分支执行相同的操作.我的二叉树只在内部节点(而不是在末端节点/叶子)存储值:

label :: MonadState m Int => Tree a -> m (Tree (Int, a))
label (Branch l x r) = do n <- get
                          l' <- label l
                          r' <- label r
                          return (Branch l' (n, x) r')
label (Leaf) = return Leaf

*编辑:需要使用State Monad然而我并没有真正掌握它的用法.我当前的代码如上所示,但无法正常工作.

编辑:所需的结果,例如:

Branch (Branch Leaf (-2) Leaf) 1 Leaf

应该:

Branch (Branch Leaf (0,-2) Leaf) (1,1) Leaf

另外我不确定我应该如何使用State Monad,我仍然对其使用感到困惑:

instance Monad (State' s) where

    -- return :: a -> State' s a
    return x = State' (\(s,c) -> (x, s, (c <> oneReturn) ))

    -- (>>=) :: State' s a -> (a -> State' s b) -> State' s b
    st >>= k = State' $ \(s,c) -> let (a, s', c') = runState' st (s,c)
                                  in runState' (k a) (s',(c' <> oneBind) )

instance MonadState (State' s) s where

    -- get :: State' s s
    get = State' $ \(s,c) -> (s,s, (c <> oneGet))

    -- put :: s -> State' s ()
    put s = State' $ \(_,c) -> ((),s, (c <> onePut))

Answer 1

我担心你的问题比目前为止建议的答案更容易解决,只要你看到如何利用你在制作类型定义时所识别的结构.这是怎么回事.

{-# LANGUAGE DeriveTraversable, FlexibleContexts #-}

module LBT where

import Control.Monad.State

data Tree x
  = Leaf
  | Branch (Tree x) x (Tree x)
  deriving (Functor, Foldable, Traversable)

这使得traverse操作从左到右工作,即根据需要按顺序工作.

现在解释如何处理单个元素.

next :: MonadState Int m => m Int
next = do x <- get ; modify (+ 1) ; return x

labelElt :: MonadState Int m => x -> m (Int, x)
labelElt x = (,) <$> next <*> pure x

该next操作为您提供下一个值并更新计数器.然后,labelElt操作用其计数器装饰单个值.现在

label :: MonadState Int m => Tree x -> m (Tree (Int, x))
label = traverse labelElt

在定义类型时,您将获得已支付的程序.当您知道如何处理一个元素时,您可以管理整个结构.免费.这里不需要临时递归!您的类型结构提供了程序的结构.只要你愿意,Haskell就会为你做到这一点.