F#:递归收集和过滤 N 元树 [英] F#: Recursive collect and filter over N-ary Tree

问题描述

这伤害了我的大脑！

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

I want to recurse over a tree structure and collect all instances that match some filter into one list.

这是一个示例树结构

type Tree =
| Node of int * Tree list

这是一个测试样本树:

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

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

Collecting and filtering over nodes with and int value of 3 should give you output like this:

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

推荐答案

以下递归函数应该可以解决问题:

The following recursive function should do the trick:

// 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 将提供的函数应用于list children - 每次调用都会返回一个元素列表和 List.collect将所有返回的列表连接成一个.

The function List.collect applies the provided function to all elements of the list children - each call returns a list of elements and List.collect concatenates all the returned lists into a single one.

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

Alternatively you could write (this maay help understanding how the code works):

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

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

The same thing can be also written using list comprehensions:

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 指出的节点.

Updated code to return nodes as pointed out by kvb.

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

BTW: It is generally a good idea to show some code that you tried to write so far. This helps people understand what part you didn't understand and so you'll get more helpful answers (and it is also considered as polite)

这篇关于F#:递归收集和过滤 N 元树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！