Haskell總結了樹中的所有路徑

我嘗試總結所有路徑，儘管樹是從根到最低的子節點之間的每個級別擴展1到10次。我的函數對所有孩子都進行遞歸遞歸，但是我遇到這樣的問題，當我嘗試創建節點列表並在列表中執行此列表時，我將成爲列表的列表列表...列表。我認爲我的問題是組合步驟而我試圖做一個模式匹配方法，但應該比較列表，當它成爲列表的列表的方法，並應該做出新的列表，並比較它們，如果它只是一種方式（符合與節點列表而不是列表與列表）不起作用。Haskell總結了樹中的所有路徑

來源

2013-07-06 Dante Miller

你的（非工作）代碼可能會使你所嘗試的更清晰:-) – gspr

summarize :: Tree a -> [[a]] 
summarize Leaf = [[]] 
summarize (Node a t1 t2) = do 
    t <- [t1, t2] 
    map (a:) (summarize t)

編輯：請注意，上述承擔Tree定義如下：

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

編輯＃2：此代碼的版本可能更清楚：

summarize :: Tree a -> [[a]] 
summarize Leaf = [[]] 
summarize (Node a t1 t2) = do 
    t  <- [t1, t2] 
    summary <- summarize t 
    return (a:summary)

這個版本有它可以寫作列表理解的好的屬性：

summarize (Node a t1 t2) = [a:summary | t <- [t1, t2], summary <- summarize t]

來源

2013-07-06 14:49:55

我*喜歡*這個答案。 –

@rightfold雖然這不相同。您的版本將最終結果包裝在「返回」中。 –

@GabrielGonzalez哎呀，brainfart。下次應該多加註意。 :) – 2013-07-06 19:18:35

樹可以表示爲列表 - 一元列表（列表中有幾個選項可以在每個點恢復）。那麼，你想要的只是這個單子列表上的一個摺疊。

import Control.Monad.Trans.List.Funcs (repeatM) -- cabal install List 
import qualified Data.List.Class as L 

exampleTree = L.take 3 (repeatM [0, 1])

要查看所有路徑：

ghci> L.toList exampleTree 
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]

綜上所述所有路徑：

ghci> L.foldlL (+) 0 exampleTree 
[0,1,1,2,1,2,2,3]

WRT的樹木這個表示，該ListTree包提供了樹操作組合程序（如DFS/BFS迭代）表示爲ListT [] s。

來源

2013-07-07 20:33:34 yairchu

Haskell總結了樹中的所有路徑

回答

相關問題