Haskell通过深度优先按顺序遍历来标记二叉树 [英] Haskell label a binary tree through depth-first in-order traversal

问题描述

我需要通过深度优先按顺序遍历来标记二叉树，因此我需要先通过树的左侧分支并标记它们，然后针对正确的分支执行相同的操作。我的二叉树只在内部节点（不在末端节点/叶节点）存储值：

  label :: MonadState m Int = >树a  - > m（Tree（Int，a））
 label（Branch lxr）= do n < -  get 
 l'< -  label l 
 r'< -  label r 
返回（Branch l'（n，x）r'）
 label（Leaf）=返回Leaf 
  

*编辑：需要使用状态Monad，但我并没有真正掌握它的用法。我目前的代码如上所示，但无法正常工作。

编辑：所需结果例如为：

 分支（分支叶（-2）叶）1叶
  

应该是：

 分支，-2）Leaf）（1,1）Leaf 
  

另外我不确定我应该如何使用State Monad，我仍然对它的使用感到困惑：

pre $实例Monad（State's s）其中

- return :: a - >状态'sa
return x = State'（\（s，c） - >（x，s，（c< 1Return）））

- （> ;> =）:: State'sa - > （a - >州的b） - >状态'b
st>>> = k =状态'$ \（s，c） - >在运行状态'（ka）（s'，（c''> 1Bind））中给出（a，s'，c'）= runState'st（s，c）


实例MonadState（State's s）其中

- get :: State'ss
get = State'$ \（s，c） - > （s，s，（c'oneGet））

- put :: s - >州的（）
把s =状态'$ \（_，c） - > （（），s，（c<> onePut））

解决方案

你不需要label_l，label_r函数。你不需要单子。
（你可以使用这个例子来了解状态monad，但是你不需要。）

只需使用（标准技巧）丰富来自

的规范

 树a  - > Tree（Int，a）
  

到

  f :: Int  - >树a  - > （Tree（Int a），Int）
  

函数获取开始标签（第一个参数）并返回标签树和下一个要使用的标签（在结果的第二个组件中）。

例如，

<$ （分支（分支叶子（-2）叶子）1叶子）
==（分支（分支叶子（8，-2）叶子）（9,1）pre> Leaf），10）


无需任何高级概念，即可轻松实现。 b
$ b

  f s0 t = 
的情况t分支lkr  - >让（l'，s1）= f s0 l 
（r'，s2）= f s1 r 
 in ... 
  

使用状态monad，您的程序将执行完全相同的操作
（next label是状态），但符号不同，
这可能会或可能不会有益（用于学习/理解）。

I need to label a binary tree through depth-first in-order traversal and I figured therefore I'd need to first go through the left branches of the tree and label those, then do the same for the right branches. My binary tree only stores values at the internal nodes (not at end nodes / leaves):

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

*EDIT: Need to use the State Monad however I'm not really grasping the usage of it. My current code is shown above but is not working properly.

EDIT: The desired result e.g. for:

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

should be:

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

Also I'm not sure how I should use the State Monad for it, I'm still quite confused for its use:

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))

解决方案

You don't need label_l, label_r functions. You don't need monads. (You can use this example for learning about the state monad, but you don't have to.)

Just use (the standard trick of) enriching the specification from

Tree a -> Tree (Int, a)

to

f :: Int -> Tree a -> ( Tree (Int a), Int )

the function gets the start label (first argument) and returns the labelled tree and the next label to use (in the second component of the result).

E.g.,

f 8 (Branch (Branch Leaf (-2) Leaf) 1 Leaf)
   == ( Branch (Branch Leaf (8,-2) Leaf) (9,1) Leaf), 10 )

This can be implemented easily, without any advanced concepts.

f s0 t = case t of
     Branch l k r -> let (l', s1) = f s0 l
                         (r', s2) = f s1 r
                     in  ...

With the state monad, your program would do exactly the same thing (the "next label" is the state), but the notation is different, which may or may not be beneficial (for learning/understanding).

这篇关于Haskell通过深度优先按顺序遍历来标记二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！