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объединяет все возвращенные списки в один.

В качестве альтернативы вы можете написать (это поможет понять, как работает код):

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.

Кстати, как правило, неплохо показать код, который вы пытались написать до сих пор. Это помогает людям понять, какую часть вы не поняли, и поэтому вы получите более полезные ответы (и это также считается вежливым)

Answer 2

Более сложное хвостовое рекурсивное решение.

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

Когда мой мозг болит, потому что он застрял в дереве, я стараюсь говорить то, что хочу, настолько просто и четко, насколько могу:

• Учитывая дерево информации, перечислите все поддеревья, соответствующие предикату (в этом случае, 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 result = filter (fun info -> info = 3) test

Одна вещь, которая удивила меня, это то, как легко код работает для любого информационного типа с соответствующим предикатом:

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

Answer 5

Подход Томаса выглядит стандартно, но не совсем соответствует вашему примеру. Если вы действительно хотите список совпадающих узлов, а не значений, это должно работать:

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 6

Вот слишком спроектированное решение, но оно показывает разделение проблем с частичными активными образцами. Это не лучший пример для частичных активных паттернов, но, тем не менее, это было забавное упражнение. Заявления о совпадении оцениваются по порядку.

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]