找到一個電感定義的樹

Question

的葉子所以，我有類型的函數：

genTree :: Node -> [Nodes] 

給定一個節點，這個函數生成的集樹節點的孩子。該函數可以再次應用於這些孩子以生成他們的孩子，直到它最終生成沒有孩子的節點，即genTree返回[]的節點。

我想要做的是，給定一個起始節點，生成樹中所有葉節點的列表，以樹爲根。

有什麼建議嗎？

Answer 1

Martijn答案中的函數生成樹中所有節點的列表。您可以使用此列表，並篩選出節點無子，以獲得葉子：

nodes root = root : concatMap nodes (genTree root) 
leaves root = filter (null . genTree) (nodes root) 

你也可以將這兩個功能結合成一個直接生成只是葉子列表，如果你喜歡：

leaves node 
    | null children = [node] 
    | otherwise  = concatMap leaves children 
    where children = genTree node 

Answer 2

讓我們概括了一點：

leaves :: (a -> [a]) -> a -> [a] 
leaves tree x = case (tree x) of 
        [] -> [x] 
        -- the node x has no children and is therefore a leaf 
        xs -> concatMap (leaves tree) xs 
        -- otherwise get list of all leaves for each child and concatenate them 

應用靜態參數變換（http://hackage.haskell.org/trac/ghc/ticket/888），我們得到

leaves :: (a -> [a]) -> a -> [a] 
leaves tree x = leaves' x where 
    leaves' x = case (tree x) of 
       [] -> [x] 
       xs -> concatMap leaves' xs 

使用它作爲

leaves genTree root 

，或者如果你真的希望它只與一起工作，內聯成的定義：

leaves1 root = case (genTree x) of 
       [] -> [x] 
       xs -> concatMap leaves1 xs 

這在道德上是等同於某物的第二個答案。

Answer 3

flatten node = node : concatMap flatten (genTree node) 

Answer 4

（不完全的問題的答案，但相關的）

我喜歡代表的樹木爲「ListT [] a」。 （ListT from List package hackage）

然後這個問題的答案只是使用函數lastL。

「Monad m => ListT m a」是包含「a‘這裏，試圖讓下一個表項（這可能會發現不存在這樣的項目）一個一元列表中的’m」一個單子的行動。

爲ListT甲使用示例 - 一個程序，它從用戶讀取數字，直到用戶不鍵入號碼和每個輸入後打印數之和：

main = 
    execute . joinM . fmap print . 
    scanl (+) 0 . 
    fmap (fst . head) . 
    takeWhile (not . null) . 
    fmap reads . 
    joinM $ (repeat getLine :: ListT IO (IO String)) 

凡repeat，scanl和takeWhile是從Data.List.Class。他們既可以用於定期列表和單點列表。

joinM :: List l => l (ItemM l a) -> l a -- (l = ListT IO, ItemM l = IO) 
execute :: List l => l a -> ItemM l() -- consume the whole list and run its actions 

如果您熟悉Python，Python的迭代器/發電機是 「ListT IO」 S。

當使用[]而不是IO作爲monadic列表的monad時，結果是一棵樹。爲什麼？想象一下獲取下一個項目的列表是列表monad中的一個動作 - 列表monad意味着有多個選項，因此有幾個「下一個項目」，這使得它成爲一棵樹。

可以構建一元列表或者與高階函數（如上面的例子），或者與cons，或使用所述GeneratorT單子變壓器從generator包在hackage蟒發電機符號（帶yield）。

免責聲明：ListT和GeneratorT絕不廣泛使用。我寫了這些，除了我自己之外，我沒有意識到任何其他用戶。有幾個等效ListT的用戶，如Haskell wiki的和其他用戶。