(* SECTION 1 *)

(* mem : 'a -> 'a list -> bool
 * mem x l renvoie true si x est dans l, false sinon *)
let mem ...

(* lenght : 'a list -> int
 * length l renvoie la taille de l *)
let length ...

(* rev : 'a list -> 'a list
 * rev l renvoie la liste des éléments de l dans l'ordre inverse *)
let rev ...

(* append : 'a list -> 'a list -> 'a list
 * append l1 l2 concatène les deux listes *)
let append ...

(* Le type du zipper sur les listes *)
type 'a path = Start | Succ of 'a path * 'a
type 'a position = 'a path * 'a list

exception Out_of_bounds

(* go_right : 'a position -> 'a position
 * go_right p renvoie la position avancée d'un élément dans la liste *)
let go_right ...

(* go_left : 'a position -> 'a position
 * go_left p renvoie la position reculée d'un élément *)
let go_left ...

let lazy_beaver ...

let append_pos ...

(* SECTION 2 *)

type ('a,'b) tree = Bleaf of 'a 
                   | Bnode of ('a,'b) tree * 'b * ('a,'b) tree

type ('a,'b) path = Top 
                  | Left of ('a,'b) path * 'b * ('a,'b) tree
                  | Right of ('a,'b) tree * 'b * ('a,'b) path

type ('a,'b) position = ('a,'b) path * ('a,'b) tree

(* go_down_left : ('a,'b) position -> ('a,'b) position
 * go_down_left p explore le sous-arbre left de la position p *)
let go_down_left ...

(* go_down_right : ('a,'b) position -> ('a,'b) position
 * go_down_right p explore le sous-arbre droit de la position p *)
let go_down_right ...

(* go_up : ('a,'b) position -> ('a,'b) position
 * go_up p remonte dans l'arbre à partir de la position p *)
let go_up ...

type dir = Bas_Gauche | Bas_Droite | Haut | Droite | Gauche

let go_left ...

let go_right ...

let rec play p =
    match p with
    | (_,Bleaf a) -> a
    | (_,Bnode (t1,d,t2)) -> begin 
        match d with
        | Bas_Droite -> play (go_down_right p)
        | Bas_Gauche -> play (go_down_left p)
        | Haut -> play (go_up p)
        | Droite -> play (go_right p)
        | Gauche -> play (go_left p)
    end

let ex1 =
Node
 (Node (Node (Leaf 1, Gauche, Leaf 2), Bas_droite,
    Node (Leaf 3, Droite, Leaf 4)),
     Bas_gauche,
      Node (Node (Leaf 4, Haut, Leaf 6), Bas_droite,
        Node (Leaf 7, Bas_gauche, Leaf 8)))

(* SECTION 3 *)

(* attrape : 'a -> 'a tree -> 'a tree
 * attrape a t renvoie l'arbre t enraciné par un noeuc étiquetté par a *)
let attrape = ...

let ex2 = 
    Gdi (1,[Gdi (3,[Gdi (7,[]);Gdi (8,[])]);Gdi (5,[Gdi (2,[Gdi (4,[])])]);Gdi (6,[])])

let affiche t = 
    let rec aux s = function
    | Gdi (x,[]) -> (print_string s ; print_int x ; print_newline ())
    | Gdi (x,l) -> (print_string s ; print_int x ; print_newline () ; List.iter (aux ("    "^s)) l) in
    affiche ""