如何用Haskell中的共享表示树 [英] How to represent tree with sharing in Haskell

问题描述

  / \ 
我想在Haskell中表示一个如下形状的树：
 / \ / \ 
 / \ / \ / \ 
 / \ / \ / \ / \ 
`````
  

/和\是分支和叶子。您可以看到，从任意节点开始，沿着左侧路径，然后右侧将您引导至相同的节点，如右侧路径和左侧。您应该能够标记叶子，在每个节点上应用两个子女的功能，并将这些信息传播到O（n ^ 2）时间的根。我天真的努力给了我一个指数运行时间。任何提示？

解决方案

当然可以构建一个共享节点的树。例如，我们可以定义：



 数据树a =叶a |节点（Tree a）（Tree a）
  

然后仔细构造这个类型的值，如

  tree :: Tree Int 
 tree = Node t1 t2 
其中
 t1 = Node t3 t4 
 t2 =节点t4 t5 
 t3 =叶子2 
 t4 =叶子3 
 t5 =叶子5 
   
 
）来实现子树的共享然而，由于这种形式的共享在Haskell中是不可观察的，所以很难维护：例如，如果你遍历一棵树来重新标记它的叶子
  relabel ::（a  - > b） - >树a  - >树b 
 relabel f（Leaf x）= Leaf（fx）
 relabel f（Node lr）= Node（重新标记fl）（重新标记fr）
  pre> 
 
 
你松散分享。另外，当进行自下而上的计算时，比如 
 
 
  sum :: Num a =>树a  - > a 
 sum（Leaf n）= n 
 sum（Node lr）= sum l + sum r 
  
你最终没有利用分享和可能重复的工作。
为了克服这些问题，你可以通过以下方式使显式共享（并因此可观察）：以类似图形的方式编码您的树：
  type Ptr = Int 
数据树'a = Leaf a |节点Ptr Ptr 
数据树a =树{root :: Ptr，env :: Map Ptr（Tree'a）} 
  
上面这个例子中的树现在可以写成： 
 
 
  tree：Tree Int 
 tree = Tree {root = 0，env = fromList ts} 
其中
 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） - >树a  - >树b 
 relabel f（树根env）=树根（fmap g env）
其中
g（Leaf x）= Leaf（fx）
g（Node lr）=节点lr 
  
和 sum 函数当树共享节点时重复工作： 
 
 
  sum :: Num a =>树a  - >一个
总和（Tree root env）= fromJust（lookup root env'）
其中
 env'= fmap f env 
f（Leaf n）= n 
f lr）= fromJust（lookup l env'）+ fromJust（lookup r env'）
  
 
I would like to represent a "tree" of the following shape in Haskell:
   /\                            
  /\/\
 /\/\/\
/\/\/\/\
` ` ` ` `
/ and \ are the branches and ` the leaves.  You can see that starting at any node, following the left path, then the right gets you to the same node as following the right path then the left.  You should be able to label the leaves, apply a function of the two decendants at each node, and propagate this information to the root in O(n^2) time.  My naive efforts are giving me an exponential run time.  Any hints?
解决方案
It is certainly possible to construct a tree with shared nodes. For example, we could just define:
data Tree a = Leaf a | Node (Tree a) (Tree a)
and then carefully construct a value of this type as in
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
to achieve sharing of subtrees (in this case t4).


However, as this form of sharing is not observable in Haskell, it is very hard to maintain: for example if you traverse a tree to relabel its leaves
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)
you loose sharing. Also, when doing a bottom-up computation such as
sum :: Num a => Tree a -> a
sum (Leaf n) = n
sum (Node l r) = sum l + sum r
you end up not taking advantage of sharing and possibly duplicate work.

To overcome these problems, you can make sharing explicit (and hence observable) by encoding your trees in a graph-like manner:
type Ptr = Int
data Tree' a = Leaf a | Node Ptr Ptr
data Tree a = Tree {root :: Ptr, env :: Map Ptr (Tree' a)}
The tree from the example above can now be written as
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)]
The price to pay is that functions that traverse these structures are somewhat cumbersome to write, but we can now define for example a relabeling function that preserves sharing
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
and a sum function that doesn't duplicate work when the tree has shared nodes:
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')


                        
这篇关于如何用Haskell中的共享表示树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！