将树的叶值更改为有序序列，同时保留树的结构

Question

给定的是递归树结构

data Tree = Leaf Int | Node Tree Tree deriving Show

我想以一种保留树结构的方式对其进行归一化，但使叶子上的整数按深度优先顺序顺序排列。我怎样才能做到这一点？我当前的设置代码如下所示：

myTree = Node (Leaf 3) (Node (Leaf 5) (Leaf 2))

myTree' = normalize myTree

-- preserve tree structure, but make Ints sequential in depths-first traversal
normalize :: Tree -> Tree
normalize = id -- todo: implement

main = do
    print myTree  -- prints      : Node (Leaf 3) (Node (Leaf 5) (Leaf 2))
    print myTree' -- should print: Node (Leaf 1) (Node (Leaf 2) (Leaf 3))

Answer 1

不使用monads，你可以写一个函数映射树携带一定的状态

mapLRS :: (s -> Int -> (s, Int)) -> s -> Tree -> (Tree, s)
mapLRS f s (Leaf x  ) =
    let (s', x') = f s x
    in  (Leaf x', s')                  -- the mapped leaf and the new state
mapLRS f s (Node l r) =
    let (l', s' ) = mapLRS f s  l      -- the mapped left branch and the new state
        (r', s'') = mapLRS f s' r      -- the mapped right branch and the new state
    in  (Node l' r', s'')

现在

normalize :: Tree -> Tree
normalize = fst . mapWithStateLeftRight (\s _ -> (s + 1, s)) 1

使用 monad 可能更具可读性（f 与使用 state 的简单性不同）

import Control.Monad.State

mapLRS :: (s -> (Int, s)) -> Tree -> State s Tree
mapLRS f (Leaf   x) = Leaf <$> state f
mapLRS f (Node l r) = Node <$> mapLRS f l <*> mapLRS f r

normalize :: Tree -> Tree
normalize tree = evalState (mapLRS (\s -> (s, s + 1)) tree) 1

Answer 2

执行此操作的标准方法是在状态 monad 中记录当前标签：

import Control.Monad.State

data Tree = Leaf Int | Node Tree Tree deriving (Show)

normalize :: Tree -> Tree
normalize t = evalState (go t) 1 where

  go :: Tree -> State Int Tree
  go (Leaf _)   = Leaf <$> (get <* modify (+1))
  go (Node l r) = Node <$> go l <*> go r

此解决方案将状态初始化为 1，然后遍历树并在每次遇到 Leaf 时将当前标签放入返回的 Leaf 并递增标签。

或者，我们可以为 Tree 导出 Traversable 实例：

{-# language DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

import Control.Monad.State

data Tree a = Leaf a | Node (Tree a) (Tree a)
  deriving (Show, Functor, Foldable, Traversable)

normalize :: Tree a -> Tree Int
normalize = (`evalState` 1) . traverse (\_ -> get <* modify (+1))

这以相同的方式工作，但请注意，它依赖于派生的 Traversable 实例具有正确的遍历顺序这一事实。当然，如果我们想要一些其他顺序，那么我们将不得不编写自己的遍历。

将树的叶值更改为有序序列，同时保留树的结构

Change leaf values of a tree to ordered sequence while preserving the tree's structure

tree

haskell

tree-traversal