如何表示在Haskell

與共享樹我謹代表在Haskell一個以下形狀的「樹」：如何表示在Haskell

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

/和\是樹枝和`樹葉。您可以看到，從任意節點開始，沿着左側路徑，然後右側將您引導至相同的節點，如右側路徑和左側。您應該能夠標記葉子，在每個節點上應用兩個子女的功能，並將這些信息傳播到O（n^2）時間的根。我天真的努力給了我一個指數運行時間。任何提示？

來源

2011-12-07 Tom Ellis

我不完全得到樹的目的。是否也可以使用列表？如果您的葉子從左到右標記爲值v1到v5，您是否可以通過列表[v1，...，v5]表示您的樹？例如，要查找值，您只需計算路徑中正確步驟的數量即可確定列表中的正確值。換句話說，如果你標記一片葉子，你想保持共享結構嗎？也就是說，如果我們在左邊，左邊，左邊，右邊標記葉子，左邊，左邊，右邊，左邊的葉子是否也應該改變？ –

1月，我想根據樹葉上的值標記內部節點，然後在程序的未來點高效查找這些信息。 –

這當然是可以構建一個樹與共享節點。例如，我們可以只定義：

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

來源

2011-12-07 08:51:29

謝謝Stefan！你的第一種形式就是我最初的形式，並且在你陳述時很難維持共享。我希望有一個不需要明確標籤的版本（在你的情況下是Ints），但也許這是不可能的。 –

在今年的荷蘭計劃生育日，我已經談到了如何充分利用兩個世界：仍然寫下你的功能，就好像你正在遍歷樹木（使用變質等），同時還有可觀察分享的好處。該演講的幻燈片可以在我的網站上找到：http：//www.holdermans.nl/talks/assets/nlfp11.pdf。關於這個問題的文件正在準備中。 –

@dblhelix - 幾年之後，這篇論文是否實現了？ – ajp

也許你可以簡單地代表它作爲樹葉的列表，直到你到一個值，即通過級別應用功能水平是這樣的：

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'

來源

2011-12-07 08:06:08 hammar

當然，但我也想讓中間節點可供檢查，並有效地從一個節點導航到它的後代。 –

如何表示在Haskell

回答

相關問題