F#:递归收集和过滤 N 元树

Question

这是在伤害我的大脑!

我想递归遍历树结构并将与某个过滤器匹配的所有实例收集到一个列表中。

这是一个示例树结构

type Tree =
| Node of int * Tree list

这是一个测试样本树:

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

收集和过滤 int 值为 3 的节点应该会给你这样的输出:

[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将所有返回的列表连接成一个列表。

或者，您可以编写(这可能有助于理解代码的工作原理):

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

同样的事情也可以用列表推导式来写:

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 ]

编辑:更新代码以返回 kvb 指出的节点。

顺便说一句:展示一些您迄今为止尝试编写的代码通常是个好主意。这有助于人们了解您不理解的部分，因此您会得到更多有用的答案(这也被认为是礼貌的)