f# - recursivo - imprimir rama mas larga de un arbol binario

F#: recolección recursiva y filtro sobre árbol N-ary

Question

¡Esto está lastimando mi cerebro!

Quiero recurrir a través de una estructura de árbol y recopilar todas las instancias que coinciden con algún filtro en una lista.

Aquí hay una estructura de árbol de muestra

type Tree =
| Node of int * Tree list

Aquí hay un árbol de muestra de prueba:

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

Recolectar y filtrar sobre nodos con un valor int de 3 debería darte resultados como este:

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

Answer 1

Aquí hay una solución sobre ingeniería, pero muestra una separación de preocupaciones con los patrones activos parciales . Este no es el mejor ejemplo para patrones activos parciales, pero fue un ejercicio divertido, no obstante. Los enunciados de coincidencia se evalúan en orden.

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]

Answer 2

El enfoque de Tomás parece estándar, pero no coincide exactamente con tu ejemplo. Si realmente desea la lista de nodos coincidentes en lugar de valores, esto debería funcionar:

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 3

La siguiente función recursiva debería hacer el truco:

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

La función List.collect aplica la función proporcionada a todos los elementos de la lista children - cada llamada devuelve una lista de elementos y List.collect concatena todas las listas devueltas en una sola.

Alternativamente, podría escribir (esto puede ayudar a entender cómo funciona el código):

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

Lo mismo también se puede escribir usando listas de comprensión:

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 ]

EDITAR: Código actualizado para devolver nodos tal como lo señala kvb.

Por cierto: en general, es una buena idea mostrar algún código que haya intentado escribir hasta ahora. Esto ayuda a las personas a comprender qué parte no comprendió y obtendrá más respuestas útiles (y también se considera amable)

Answer 4

Solo por mostrar el uso de F# Sequences Expression (quizás no sea el mejor enfoque, creo que la solución de Tomás es mejor):

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 5

Una solución recursiva de cola más compleja.

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 6

Cuando me duele el cerebro porque está pegado a un árbol, trato de decir lo que quiero de la manera más simple y clara que puedo:

• Dado un árbol de información, enumere todos los subárboles que coincidan con un predicado (en este caso, info = 3).

Una manera directa de hacerlo es hacer una lista de todos los nodos del árbol y luego filtrar el predicado.

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)

Aquí está el filtro de árbol ejecutado contra los datos de muestra del OP:

let result = filter (fun info -> info = 3) test

Una cosa que me sorprendió es la facilidad con la que funciona el código para cualquier tipo de información con el predicado apropiado:

let test2 =
Node(("One",
[Node("Two",
[Node("Three",[Node("Five",[]);Node("Three",[])]);
Node("Three",[])]);
Node("Three",[])]))
let res2 = filter (fun info -> info = "Three") test2

Alternativamente, si desea enumerar la información en lugar de los subárboles, el código es increíblemente simple:

let rec visit = function
| Node( info, [] ) -> [ info ]
| Node( info, children ) -> info :: List.collect visit children
let filter predicate tree =
visit tree
|> List.filter predicate

que admite las mismas consultas pero solo devuelve los ''registros de información, no la estructura de árbol:

let result = filter (fun info -> info = 3) test
> val result : int list = [3; 3; 3; 3]