Skip to content

Instantly share code, notes, and snippets.

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

Embed
What would you like to do?
Core algorithm for building a tree using the zippers
//core algorithm that returns a new zipper with the branch appended
let rec appendToTreeZipper (Loc (t,p) as l) (branch:list<string>) =
let rightSiblings = match p with
| Top(_) -> []
| PathNode(_,_,_,rights) -> rights
let label = match t with
| Empty -> None
| TreeNode(lbl,_) -> Some(lbl)
match label,rightSiblings,branch with
//empty tree in the zipper, just build a basic tree with zipper with the current branch
| None,_,_ -> insert_down <| branchToTree branch <| l
//the current tree label and the head of the branch match -> then go deeper
| Some(x), _, head::tail when x = head -> appendToTreeZipper <| go_down l <| tail
//if the label and the head does not match and there is no right simblings then we have to insert node here.
| _, [] ,_ -> insert_right <| TreeNode(branch.Head,[Tree.Empty]) <| l
//Remaining case: try to find a match with the right most simbling.
| _, _ ,_ -> appendToTreeZipper <| go_right l <| branch
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.