はHaskellの

Question

で共有してツリーを表現するためにどのように私はHaskellで、以下の形状の「木」を表すしたいと思います。左のパスに続いて、任意のノードから開始すると、右は右のパスをたどり、その後は左のノードと同じノードに移動します。葉にラベルを付け、各ノードで2つの下位関数の関数を適用し、この情報をO（n^2）時間内にルートに伝播できるようにする必要があります。私の素朴な努力は私に指数関数的な実行時間を与えています。何かヒント？

Answer 1

構築することは確かに可能です共有ノードを持つツリー。

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

をして、慎重に（この場合はt4中）サブツリーの共有を実現するために

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 

のように、この型の値を構築する：たとえば、私たちは定義することができます。共有のこのフォームは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') 

Answer 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'