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]