Instantly share code, notes, and snippets.

@bpatra /gist:6074217
Last active Dec 20, 2015

Embed
What would you like to do?
Implementation of a "tree builder" using mutability of the data structure
type Tree =
|Node of string*list<Tree ref>
|Empty
//create tree from a branch
let rec branchToTree (inputList:list<string>) =
match inputList with
| [] -> Tree.Empty
| head::tail -> Tree.Node (head, [ref (branchToTree tail)])
//branch cannot be empty list
let rec mergeInto (tree:Tree ref) (branch:list<string>) =
match !tree,branch with
| Node (value,_), head::tail when value <> head -> failwith "Oops invariant loop broken"
//the branch is singleton and by loop invariant its head is the current Tree node -> nothing to do.
| Node (value,_), [_] -> ignore()
| Node (value,children), _ ->
let nextBranchValue = branch.Tail.Head //valid because of previous match
// retrieve a ref to the proper child
let targetChild = children
|> List.tryFind (fun(child) -> match !child with
|Empty -> false
|Node (value,_) -> value = nextBranchValue)
match targetChild with
//a valid child match then go deeper. NB: branch.Tail cannot be empty here
|Some x -> mergeInto x branch.Tail
//attach the next branch value to the children
|None -> tree := Node(value, (ref (Node (nextBranchValue,[]))) :: children)
| Empty,_ -> tree := branchToTree branch
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment