F＃：遞歸收集和篩選過N叉樹

Question

這是傷害我的大腦！

我想在遞歸樹結構，並收集了一些過濾條件的一個列表中的所有實例。

下面是一個示例樹結構

type Tree = 
| Node of int * Tree list 

這是一個測試樣本樹：

let test = 
    Node((1, 
      [Node(2, 
        [Node(3,[]); 
        Node(3,[])]); 
      Node(3,[])])) 

收集和過濾過與節點和3個int值應該給你的輸出是這樣的：

[Node(3,[]);Node(3,[]);Node(3,[])] 

Answer 1

下面的遞歸函數應該做的伎倆：

// The 'f' parameter is a predicate specifying 
// whether element should be included in the list or not 
let rec collect f (Node(n, children) as node) = 
    // Process recursively all children 
    let rest = children |> List.collect (collect f) 
    // Add the current element to the front (in case we want to) 
    if (f n) then node::rest else rest 

// Sample usage 
let nodes = collect (fun n -> n%3 = 0) tree 

功能List.collect應用所提供的功能將 列表children的所有元素 - 每調用返回的元素和List.collect 串聯所有返回列表成爲一個單一的列表。

或者你可以寫（這maay幫助理解代碼是如何工作的）：

let rec collect f (Node(n, children) as node) = 
    [ for m in children do 
     // add all returned elements to the result 
     yield! collect f m 
    // add the current node if the predicate returns true 
    if (f n) then yield node ] 

編輯：更新代碼

let rest = 
    children |> List.map (fun n -> collect f n) 
      |> List.concat 

同樣的事情可以用列表解析也寫如kvb指出的那樣返回節點。

BTW：它一般是要表明你試圖到目前爲止寫一些代碼是個好主意。這將有助於人們瞭解哪些部分你不明白，所以你會得到更多有用的答案（它也被認爲是禮貌）

Answer 2

托馬斯的做法看起來標準，但不完全匹配您的例子。如果你真的想匹配的節點，而不是值的列表，這應該工作：

let rec filter f (Node(i,l) as t) = 
    let rest = List.collect (filter f) l 
    if f t then t::rest 
    else rest 

let filtered = filter (fun (Node(i,_)) -> i=3) test 

Answer 3

只是用於顯示的F# Sequences Expression使用（也許不是最好的方法，托馬斯的解決方案更可能更好，我認爲）：

type Tree = 
    | Node of int * Tree list 

let rec filterTree (t : Tree) (predicate : int -> bool) = 
    seq { 
    match t with 
    | Node(i, tl) -> 
     if predicate i then yield t 
     for tree in tl do 
      yield! filterTree tree predicate 
    } 

let test = Node (1, [ Node(2, [ Node(3,[]); Node(3,[]) ]); Node(3,[]) ]) 

printfn "%A" (filterTree test (fun x -> x = 3)) 

Answer 4

一個更復雜的尾遞歸溶液。

let filterTree (t : Tree) (predicate : int -> bool) = 
    let rec filter acc = function 
     | (Node(i, []) as n)::tail -> 
      if predicate i then filter (n::acc) tail 
      else filter acc tail 
     | (Node(i, child) as n)::tail -> 
      if predicate i then filter (n::acc) (tail @ child) 
      else filter acc (tail @ child) 
     | [] -> acc 

    filter [] [t] 

Answer 5

下面是一個在設計的解決方案，但它顯示的與Partial Active Patterns關注政企分開。這不是部分主動模式的最好例子，但它仍然是一個有趣的練習。匹配語句按順序進行評估。

let (|EqualThree|_|) = function 
    | Node(i, _) as n when i = 3 -> Some n 
    | _ -> None 

let (|HasChildren|_|) = function 
    | Node(_, []) -> None 
    | Node(_, children) as n -> Some children 
    | _ -> None 

let filterTree3 (t : Tree) (predicate : int -> bool) = 
    let rec filter acc = function 
     | EqualThree(n)::tail & HasChildren(c)::_ -> filter (n::acc) (tail @ c) 
     | EqualThree(n)::tail -> filter (n::acc) tail 
     | HasChildren(c)::tail -> filter acc (tail @ c) 
     | _::tail -> filter acc tail 
     | [] -> acc 

    filter [] [t] 

Answer 6

當我的腦袋疼的Cuz它粘在樹上，我儘量說些什麼我想爲簡單明瞭，我可以：

• 鑑於信息的樹，列出所有子樹匹配謂詞（在這種情況下，info = 3）。

一個簡單的方法就是列出樹的所有節點，然後過濾謂詞。

type 'info tree = Node of 'info * 'info tree list 

let rec visit = function 
    | Node(info, []) as node -> [ node ] 
    | Node(info, children) as node -> node :: List.collect visit children 

let filter predicate tree = 
    visit tree 
    |> List.filter (fun (Node(info,_)) -> predicate info) 

這裏的樹過濾器對OP的樣本數據運行：

let test2 = 
    Node(("One", 
      [Node("Two", 
        [Node("Three",[Node("Five",[]);Node("Three",[])]); 
        Node("Three",[])]); 
      Node("Three",[])])) 

let res2 = filter (fun info -> info = "Three") test2 

：

令我驚訝的是代碼如何輕鬆地適用於任何「信息類型與相應的判定

let result = filter (fun info -> info = 3) test 

一件事

或者，如果您想列出信息而不是子樹，代碼很簡單：

let rec visit = function 
    | Node(info, []) -> [ info ] 
    | Node(info, children) -> info :: List.collect visit children 

let filter predicate tree = 
    visit tree 
    |> List.filter predicate 

支持相同的查詢，但只返回「信息記錄，而不是樹形結構：

let result = filter (fun info -> info = 3) test 

> val result : int list = [3; 3; 3; 3]