F # convert list to tree

Question

I have a list of tuples int * string, where int is the level and string is the name

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

and i need to convert it to the next

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

Below is the way I did it, but could anyone consult the best way to achieve this. I am new to F #, and C # code to do the same would be shorter, so I think I'm wrong.

 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, eg 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

First of all, you do not need to have a dedicated case for Leaf if your branch contains a list of subtrees, because a leaf is just a branch without subtrees. So, I am going to use the following tree type:

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

The main function for converting a list to a tree is probably easier to implement using explicit recursive list processing. You can do this in one pass - just go through the elements and start a new branch when you find the nested index (or return from the corresponding number of recursive calls when you get a smaller index). This is my attempt:

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

The function accepts the initial offset and the trees collected so far. The trees parameter will always be [] , and you need some value for the initial offset . The result is a list of trees below a given level and a list of the remaining elements:

 let res = buildTrees -1 [] src 

Assuming the root is above -1, you can simply ignore the second part of the tuple (this should be an empty list) and get the first tree (there should be only one):

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