I have a list of tuples int*string where int is level and string is name
let src = [
(0, "root");
(1, "a");
(2, "a1");
(2, "a2");
(1, "b");
(2, "b1");
(3, "b11");
(2, "b2");
]
and i need to transform it to following
let expectingTree =
Branch("root",
[
Branch("a",
[
Leaf("a1");
Leaf("a2")
]);
Branch("b",
[
Branch("b1", [Leaf("b11")]);
Leaf("b2")
]);
]);
Below is the way how i did it, but could anybody advice with a better way to achieve that. I'm new to F#, and C# code to do the same thing would be some shorter, so i guess i'm going it 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, 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
To reset your password if you're not logged in to Facebook: Click Forgot Password?. Type the email, mobile phone number, full name or username associated with your account, then click Search. Follow the on-screen instructions.
Email: You can log in with any email that's listed on your Facebook account. Phone number: If you have a mobile number confirmed on your account, you can enter it here (don't add any zeros before the country code, or any symbols). Username: You can also log in with your username, if you set one up.
First of all, you do not really need to have a distinguished case for Leaf
if your branch is containing a list of sub-trees, because leaf is just a branch with no sub-trees. So, I'm going to use the following tree type:
type Tree =
| Branch of string * list<Tree>
The core function for turning list to a tree is probably easier to implement using explicit recursive list processing. You can do it in one pass - just go over the elements and start a new branch whenever you find nested index (or return from an appropriate 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 takes initial offset and trees collected so far. The trees
parameter is always going to be []
and you need some value for initial offset
. The result is a list of trees below the given level and a list of remaining elements:
let res = buildTrees -1 [] src
Assuming root is above -1, you can just ignore the second part of the tuple (it should be 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 ""
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With