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以上であると仮定すると、あなただけ（それは空のリストであるべきである）タプルの第二の部分を無視することができると最初のツリーを取得します（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 ""