F＃轉換列表以樹形

Question

我的元組INT *字符串的一個列表，其中int是水平和字符串名稱

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

，我需要把它轉換爲以下

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

下面是我如何做到這一點，但任何人都可以通過更好的方式來達到這個目的。 我是F＃的新手，C＃代碼做同樣的事情會更短，所以我想我錯了。所有的

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

首先，你並不真的需要有一個傑出案例Leaf，如果你的分支包含的子樹的列表，因爲葉僅僅是一個沒有子樹的分支。所以，我將使用下面的樹類型：

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

車削列表樹的核心功能是使用明確的遞歸列表處理來實現可能更容易。您可以一次完成 - 只要查找嵌套索引（或者在得到較小索引時從適當數量的遞歸調用中返回），只需查看元素並開始新分支即可。這是我的嘗試：

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

該函數採用初始偏移量和目前收集的樹。 trees參數始終爲[]，初始offset需要一些值。結果是低於給定電平的樹列表和其餘元件的列表：

let res = buildTrees -1 [] src 

假設根以上是-1，則可以忽略該元組的第二部分（它應該是空的列表），並得到第一棵樹（應該只有一個）：

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