如何在Haskell中使用共享来表示树

Question

如何在Haskell中使用共享来表示树

16

我想在Haskell中表示以下形状的“树”：

   /\                            
  /\/\
 /\/\/\
/\/\/\/\
` ` ` ` `

/ 和 \ 是分支，而 ` 是叶子。你可以看到从任何一个节点开始，沿着左路径然后右路径可以让你到达与沿着右路径然后左路径到达同一节点。你应该能够标记叶子节点，在每个节点应用两个后代的函数，并在 O(n^2) 时间内将此信息传播到根节点。我的天真尝试给我带来了指数级的运行时间。有什么提示吗？

- Tom Ellis

我不太明白树的目的。是否也可以使用列表？如果您的叶子从左到右标记为v1到v5，您是否也可以通过列表[v1，...，v5]表示树？例如，要查找一个值，您只需计算路径中向右步骤的数量，以识别列表中的正确值。换句话说，如果您标记了一个叶子，您是否想保留共享结构？也就是说，如果我们标记了左边、左边、左边、右边的叶子，左边、左边、右边、左边的叶子是否也应该更改？ - Jan Christiansen

1

Jan，我想要标记内部节点，并根据叶子结点的值进行标记。然后在程序的未来某个时刻高效地查找这些信息。 - Tom Ellis

2个回答

2

也许您可以将其简单表示为叶子列表，并逐层应用该函数，直到只剩下一个值，例如：

type Tree a = [a]

propagate :: (a -> a -> a) -> Tree a -> a
propagate f xs =
  case zipWith f xs (tail xs) of
    [x] -> x
    xs' -> propagate f xs'

- hammar

当然可以，但我也希望保留中间节点以供检查，并能够高效地从一个节点导航到其子节点。 - Tom Ellis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stefan Holdermans · Accepted Answer

构建具有共享节点的树是完全可行的。例如，我们可以定义：

data Tree a = Leaf a | Node (Tree a) (Tree a)

然后仔细构建这种类型的值，就像下面这样

tree :: Tree Int
tree = Node t1 t2
  where
    t1 = Node t3 t4
    t2 = Node t4 t5
    t3 = Leaf 2
    t4 = Leaf 3
    t5 = Leaf 5

为了实现子树的共享（在这种情况下是 t4），

然而，在 Haskell 中，由于这种形式的共享不可观察，因此很难维护：例如，如果你遍历一棵树以重新标记其叶子节点。

relabel :: (a -> b) -> Tree a -> Tree b
relabel f (Leaf x) = Leaf (f x)
relabel f (Node l r) = Node (relabel f l) (relabel f r)

你失去了共享。此外，在进行自底向上的计算（例如）时

sum :: Num a => Tree a -> a
sum (Leaf n) = n
sum (Node l r) = sum l + sum r

如果你不利用共享，可能会导致工作的重复。

为了克服这些问题，你可以通过以类似于图形的方式对树进行编码来使共享变得明确（并因此可观察）：

type Ptr = Int
data Tree' a = Leaf a | Node Ptr Ptr
data Tree a = Tree {root :: Ptr, env :: Map Ptr (Tree' a)}

上面示例中的树现在可以写成

tree :: Tree Int
tree = Tree {root = 0, env = fromList ts}
  where
    ts = [(0, Node 1 2), (1, Node 3 4), (2, Node 4 5),
          (3, Leaf 2), (4, Leaf 3), (5, Leaf 5)]

代价是，遍历这些结构的函数有点难写，但现在我们可以定义一个保留共享的重新标记函数。

relabel :: (a -> b) -> Tree a -> Tree b
relabel f (Tree root env) = Tree root (fmap g env)
  where
    g (Leaf x)   = Leaf (f x)
    g (Node l r) = Node l r

还需要一个 sum 函数，当树具有共享节点时不会重复计算：

sum :: Num a => Tree a -> a
sum (Tree root env) = fromJust (lookup root env')
  where
    env' = fmap f env
    f (Leaf n) = n
    f (Node l r) = fromJust (lookup l env') + fromJust (lookup r env')