F#：N 叉树的递归收集和过滤

这可伤了我的脑子啊！

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

这是一个示例树结构

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,[])]

下面的递归函数应该可以解决这个问题：

// 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 ]

EDIT:更新了代码以返回 kvb 指出的节点。

顺便说一句：通常最好展示一些您迄今为止尝试编写的代码。这可以帮助人们理解你不明白的部分，这样你就会得到更有帮助的答案（这也被认为是礼貌的）