如何在 Haskell 中标记树中的节点？

Question

假设我有一个Data.Tree持有字符：Tree Char:

    A
   / \
  B   C
     /|\
    D A F

请注意，树中可能存在重复项。我想通过存储边将这棵树存储在关系数据库中，但是由于重复项，我不能使用节点的内容作为键（注意不同级别的 A）。

也许一个解决方案是遍历 de tree 并用唯一的 id 映射它，例如：

    (1,A)
    / \
 (2,B) (3,C)
        /|\
  (4,D)(5,A),(6,F)

现在存储边缘没有任何问题，因为我使用了 ids。

(1, null, A)
(2, 1, B)
(3, 1, C)
(4, 3, D)
(5, 3, A)
(6, 3, F)

但我看不出如何将静态树节点“映射”到无限 ID 生成器。

从功能的角度来看，您的方法是什么？请注意，我无法对分支因子的数量做出任何假设，因此我无法展平、压缩 ID 和重建树

Answer 1

您可以使用 State 来发送 ID，因此：

import Control.Monad.State.Lazy(State, get, put)

labelNext :: State Int Int
labelNext = do
    val <- get
    put (val+1)
    return val

然后我们可以用以下标记树：

{-# LANGUAGE TupleSections #-}

labelTree :: Tree a -> Tree (Int, a)
labelTree tree = evalState (traverse (\a -> (,a) <$> labelNext) tree) 1

例如，这给了我们：

ghci> labelTree (Node 'A' [Node 'B' [], Node 'C' [Node 'D' [], Node 'A' [], Node 'F' []]])
Node {rootLabel = (1,'A'), subForest = [Node {rootLabel = (2,'B'), subForest = []},Node {rootLabel = (3,'C'), subForest = [Node {rootLabel = (4,'D'), subForest = []},Node {rootLabel = (5,'A'), subForest = []},Node {rootLabel = (6,'F'), subForest = []}]}]}

如何在 Haskell 中标记树中的节点？

How do I label nodes in a Tree in Haskell?

algorithm

tree

haskell

functional-programming