F # Transformations Liste an einen Baum

Question

ich eine Liste von Tupeln int * string, wo int level ist und String Name

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

und ich brauche es zu transformieren, um folgende

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

Nachfolgend finden die Art, wie ich es gemacht habe, aber könnte jemand mit einem besseren Weg beraten, das zu erreichen. Ich bin neu in F #, und C# -Code, um das Gleiche zu tun, wäre etwas kürzer, also schätze ich, dass ich falsch liege.

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

Zunächst einmal brauchen Sie nicht wirklich einen ausgezeichneten Fall für Leaf zu haben, wenn Ihre Branche ist eine Liste der Teilbäume enthalten, weil Blatt nur ein Zweig ohne Unterbäumen ist. Also, ich werde den folgenden Baumtyp verwenden:

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

Die Kernfunktion für das Drehen Liste an einen Baum wahrscheinlich einfacher ist, mit expliziter rekursive Listenverarbeitung zu implementieren. Sie können dies in einem Durchgang tun - gehen Sie einfach über die Elemente und starten Sie einen neuen Zweig, wenn Sie einen verschachtelten Index finden (oder geben Sie eine angemessene Anzahl von rekursiven Aufrufen zurück, wenn Sie einen kleineren Index erhalten). Dies ist mein Versuch:

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

Die Funktion übernimmt den anfänglichen Offset und die bisher gesammelten Bäume. Der trees Parameter wird immer [] sein und Sie benötigen einen Wert für die erste offset. Das Ergebnis ist eine Liste der Bäume unter den angegebenen Werten und eine Liste der übrigen Elemente:

let res = buildTrees -1 [] src 

Unter der Annahme, Wurzel oben -1 ist, können Sie nur den zweiten Teil des Tupels ignorieren (es soll leere Liste sein) und Holen Sie sich den ersten Baum (es sollte nur einen geben):

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