Tree Zipper with F#. References : http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf

TreeZipper.fs

module TreeZipper

type Tree<'value> = 
    | Item of 'value
    | Section of Tree<'value> list

type Path<'value> = 
    | Top
    | Node of Tree<'value> list * Path<'value> * Tree<'value> list

type Location<'value> = 
    | Loc of Tree<'value> * Path<'value>

let goLeft (Loc(tree, path)) = 
    match path with
    | Top -> failwith "left of top"
    | Node(l::left, up, right) -> Loc(l, Node(left, up, tree::right))
    | Node([], _, _) -> failwith "left of first"

let goRight (Loc(tree, path)) = 
    match path with
    | Top -> failwith "right of top"
    | Node(left, up, r::right) -> Loc(r, Node(tree::left, up, right))
    | _ -> failwith "right of last"

let goUp (Loc(tree, path)) = 
    match path with
    | Top -> failwith "up of top"
    | Node(left, up, right) -> Loc(Section((List.rev left) @ (tree::right)), up)

let goDown (Loc(tree, path)) = 
    match tree with
    | Item(_) -> failwith "down of item"
    | Section(leftChild::others) -> Loc(leftChild, Node([], path, others))
    | _ -> failwith "down of empty"

let insertLeft value (Loc(tree, path)) = 
    match path with
    | Top -> failwith "insert of top"
    | Node(left, up, right) -> Loc(tree, Node(value::left, up, right))

let insertRight value (Loc(tree, path)) = 
    match path with
    | Top -> failwith "insert of top"
    | Node(left, up, right) -> Loc(tree, Node(left, up, value::right))

let insertDown value (Loc(tree, path)) = 
    match tree with
    | Item(_) -> failwith "down of item"
    | Section(sons) -> Loc(value, Node([], path, sons))

let update tree (Loc(_, path)) = 
    Loc(tree, path)

let delete (Loc(_, path)) = 
    match path with
    | Top -> failwith "delete of top"
    | Node(left, up, r::right) -> Loc(r, Node(left, up, right))
    | Node(l::left, up, []) -> Loc(l, Node(left, up, []))
    | Node([], up, []) -> Loc(Section[], up)