(*
   Programmation fonctionnelle, générique et objet
   (Une introduction avec le langage OCaml)
   Ph. Narbel,  Vuibert, 2005
 
   Ces programmes ont pour but d'illustrer les sujets traités dans
   le livre. Il n'est donné aucune garantie quant à leur utilisation
   dans le cadre d'une activité professionnelle ou commerciale.
   Ces programmes peuvent être copiés sous réserve que leur provenance
   soit citée et que cet avertissement soit inclus.

   These programs are provided without warranty of any kind. Their
   purpose is just to serve as illustrations in the book.  Permission
   to copy is granted provided that citation and this disclaimer of
   warranty are included.
*)

type 'a bintree =
  | BinEmpty
  | BinNode of 'a * 'a bintree * 'a bintree

type 'a path =
  | Root
  | Left of 'a * 'a bintree * 'a path
  | Right of 'a * 'a bintree * 'a path

type 'a zipper = Zip of 'a bintree * 'a path

let move_left (Zip (tree, path)) = match tree with
  | BinEmpty -> failwith "Empty"
  | BinNode (x, t1, t2) -> Zip (t1, Left (x, t2, path))

let move_right (Zip (tree, path)) = match tree with
  | BinEmpty -> failwith "Empty"
  | BinNode (x, t1, t2) -> Zip (t2, Right (x, t1, path))

let move_up (Zip (tree, path)) = match path with
  | Root -> failwith "Root"
  | Left (x, t, path_tail)  -> Zip (BinNode (x, tree, t), path_tail)
  | Right (x, t, path_tail) -> Zip (BinNode (x, t, tree), path_tail)