F # lista de transformar a un árbol

Question

Tengo una lista de tuplas int * cadena, donde int es el nivel y la cadena es el nombre

let src = [ 
     (0, "root"); 
      (1, "a"); 
       (2, "a1"); 
       (2, "a2"); 
      (1, "b"); 
       (2, "b1"); 
        (3, "b11"); 
       (2, "b2"); 
     ] 

y necesito para transformarlo a continuación

let expectingTree = 
    Branch("root", 
    [ 
     Branch("a", 
      [ 
       Leaf("a1"); 
       Leaf("a2") 
      ]); 
     Branch("b", 
      [ 
       Branch("b1", [Leaf("b11")]); 
       Leaf("b2") 
      ]); 
    ]); 

A continuación se la forma en que lo hice, pero podría alguien aconsejar con una mejor manera de lograr eso. Soy nuevo en F #, y el código C# para hacer lo mismo sería algo más corto, así que supongo que me equivoco.

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

let src = [ 
      (0, "root"); 
       (1, "a"); 
        (2, "a1"); 
        (2, "a2"); 
       (1, "b"); 
        (2, "b1"); 
         (3, "b11"); 
        (2, "b2"); 
      ] 

let rec setParents (level:int) (parents:list<int>) (lst:list<int*int*string>) : list<int*int*string> = 
    //skip n items and return the rest 
    let rec skip n xs = 
     match (n, xs) with 
     | n, _ when n <= 0 -> xs 
     | _, [] -> [] 
     | n, _::xs -> skip (n-1) xs 

    //get parent id for given level 
    let parentId (level) = 
     let n = List.length parents - (level + 1) 
     skip n parents |> List.head 

    //create new parent list and append new id to begin 
    let newParents level id = 
     let n = List.length parents - (level + 1) 
     id :: skip n parents 

    match lst with 
    | (id, l, n) :: tail -> 
         if l = level then (id, parentId(l), n) :: setParents l (newParents l id) tail 
         elif l <= level + 1 then setParents l parents lst 
         else [] //items should be in order, e.g. there shouldnt be item with level 5 after item with level 3 
    | _ -> [] 


let rec getTree (root:int) (lst: list<int*int*string>) = 

    let getChildren parent = 
     List.filter (fun (_, p, _) -> p = parent) lst 

    let rec getTreeNode (id:int) (name:string) = 
     let children = getChildren id 
     match List.length children with 
     | 0 -> Leaf(name) 
     | _ -> Branch(name, 
         children 
         |> List.map (fun (_id, _, _name) -> getTreeNode _id _name)) 

    match getChildren root with 
    | (id, _, n) :: _ -> getTreeNode id n 
    | _ -> Leaf("") 

let rec printTree (ident:string) (tree:Node) = 
    match tree with 
    | Leaf(name) -> 
     printfn "%s%s" ident name 
    | Branch(name, children) -> 
     printfn "%s%s" ident name 
     List.iter (fun (node) -> printTree (" " + ident) node) children 

let tree = 
    src 
    |> List.mapi (fun i (l, n) -> (i+1, l, n)) //set unique id to each item 
    |> setParents 0 [0] //set parentId to each item 
    |> getTree 0 


printTree "" tree 

Console.ReadKey() |> ignore 

Answer 1

En primer lugar, usted realmente no necesita tener un caso distingue por Leaf si su rama es que contiene una lista de sub-árboles, porque la hoja es sólo una rama sin sub-árboles. Por lo tanto, voy a utilizar el siguiente tipo de árbol:

type Tree = 
    | Branch of string * list<Tree> 

La función básica para la lista de giro a un árbol es probablemente más fácil de implementar utilizando el procesamiento recursivo lista explícita. Puede hacerlo de una sola vez: simplemente revise los elementos e inicie una nueva bifurcación cuando encuentre un índice anidado (o regrese de una cantidad adecuada de llamadas recursivas cuando obtenga un índice más pequeño). Este es mi intento:

/// Build a tree from elements of 'list' that have larger index than 'offset'. As soon 
/// as it finds element below or equal to 'offset', it returns trees found so far 
/// together with unprocessed elements. 
let rec buildTree offset trees list = 
    match list with 
    | [] -> trees, [] // No more elements, return trees collected so far 
    | (x, _)::xs when x <= offset -> 
     trees, list // The node is below the offset, so we return unprocessed elements 
    | (x, n)::xs -> 
     /// Collect all subtrees from 'xs' that have index larger than 'x' 
     /// (repeatedly call 'buildTree' to find all of them) 
     let rec collectSubTrees xs trees = 
     match buildTree x [] xs with 
     | [], rest -> trees, rest 
     | newtrees, rest -> collectSubTrees rest (trees @ newtrees) 
     let sub, rest = collectSubTrees xs [] 
     [Branch(n, sub)], rest 

La función toma desplazamiento inicial y árboles recogidos hasta el momento. El parámetro trees siempre va a ser [] y necesita algún valor para el offset inicial. El resultado es una lista de árboles por debajo del nivel dado y una lista de elementos restantes:

let res = buildTrees -1 [] src 

Suponiendo que la raíz está por encima de -1, puede simplemente ignorar la segunda parte de la tupla (debe estar lista vacía) y obtener el primer árbol (debe haber solo uno):

/// A helper that nicely prints a tree 
let rec print depth (Branch(n, sub)) = 
    printfn "%s%s" depth n 
    for s in sub do print (depth + " ") s 

res |> fst |> Seq.head |> print ""