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屋！