caminos Extracción de hojas de árbol de n-aria en F #

Question

Inspirado por this question, yo quería probar mi mano en la última ponder this challenge, utilizando F #

Mi enfoque es probablemente completamente fuera de curso, pero en el transcurso de la solución de este problema , Estoy tratando de obtener una lista de todas las permutaciones de los dígitos 0-9.

estoy mirando a resolverlo utilizando un árbol n-ario de este modo:

type Node = 
    | Branch of (int * Node list) 
    | Leaf of int 

estoy bastante satisfecho de mí mismo, porque me las he arreglado para encontrar la manera de generar el árbol de que yo querer.

Mi problema ahora es que no puedo averiguar cómo atravesar este árbol y extraer la 'ruta' de cada hoja como un int. Lo que me confunde es que necesito unirme en nodos individuales, pero mi función 'externa' debe tomar una lista de nodos.

Mi intento de corriente casi hace lo correcto, excepto que me devuelve la suma de todos los caminos ...

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

let rec visitor lst acc = 
    let inner n = 
     match n with 
     | Leaf(h) -> acc * 10 + h 
     | Branch(h, t) -> visitor t (acc * 10 + h) 
    List.map inner lst |> List.sum 

visitor [test] 0 //-> gives 633 (which is 321 + 312) 

Y ni siquiera estoy seguro de que este es recursiva de cola.

(Eres muy bienvenido a proponer otra solución para encontrar permutaciones, pero todavía estoy interesado en la solución a este problema en particular)

EDIT: He publicado un algoritmo de permutaciones genéricos en Fa # here.

Answer 1

con respecto a su pregunta sobre el recorrido de la lista - puede comenzar escribiendo una función que devuelve listas que representen la ruta - eso es más fácil y más tarde será fácil convertirlo en una función que devuelve un número.

Éste toma una lista como el primer argumento (ruta hasta ahora) y un árbol y devuelve una lista> tipo - que son todas las rutas posibles de la rama actual.

let rec visitor lst tree = 
    match tree with 
    | Branch(n, sub) -> List.collect (visitor (n::lst)) sub 
    | Leaf(n) -> [List.rev (n::lst)] 

// For example... 
> let tr = Branch(1, [Leaf(3); Branch(2, [Leaf(4); Leaf(5)])]);; 
> visitor [] tr;; 
val it : int list list = [[1; 3]; [1; 2; 4]; [1; 2; 5]] 

En el caso de 'hoja', sólo tenemos que añadir el número actual a la lista y devuelve el resultado como una lista que contiene una lista única (tenemos que invertir en primer lugar, porque estábamos agregando números al comienzo) . En el caso 'Rama', agregamos 'n' a la lista y recursivamente llamamos al visitante para procesar todos los nodos secundarios de la rama actual. Esto devuelve un montón de listas y usamos 'map_concat' para convertirlas en una sola lista que contiene todas las rutas posibles de la rama actual.

Ahora, puede volver a escribir esto para devolver una lista de números enteros:

let rec visitor2 lst tree = 
    match tree with 
    | Branch(n, sub) -> List.collect (visitor2 (lst * 10 + n)) sub 
    | Leaf(n) -> [lst * 10 + n] 

// For example... 
> visitor2 0 tr;; 
val it : int list = [13; 124; 125] 

En lugar de la concatenación de listas, que ahora calcular el número.

Answer 2

Relativo a la pereza - Puede hacer esto vago usando el tipo F # "seq" en lugar del tipo "list". Este es un ejemplo:

let rec visitor2 lst tree = 
    match tree with 
    | Branch(n, sub) -> Seq.map_concat (visitor2 (lst * 10 + n)) sub 
    | Leaf(n) -> 
     seq { do printfn "--yielding: %d" (lst * 10 + n) 
      yield lst * 10 + n };; 

Lo "ss" es una expresión de secuencia, que representa una corriente perezoso de valores.He añadido "printfn" al código, para que podamos realizar un seguimiento de cómo las cosas están ejecutando:

> visitor2 0 tr |> Seq.take 2;; 
--yielding: 13 
--yielding: 124 
val it : seq<int> = seq [13; 124] 

es probable que pueda usar algo como Seq.first para encontrar el primer valor que representa el resultado.