(**
   TP : expliciter le flot de contrôle par des continuations dans
   des petits parcours d'arbres.
*)

(* Arbres binaires *)
type 'a tree =
  | Leaf 
  | Node of 'a * 'a tree * 'a tree

(**
   Fonction simple de parcours d'arbre en profondeur, qui produit une
   liste des étiquettes des nœuds rencontrés.
*)
let rec dfs t =
  match t with
    | Leaf -> []
    | Node(a, t, u) -> a :: (dfs t) @ (dfs u)

(**
   Exemple de transformation de [dfs] en style par passage de continuations.
   Remarquez que la fonction obtenue est récursive terminale.
*)
let tailrec_dfs t =
  (* La fonction [cps_dfs] prend en paramètre supplémentaire une
     continuation, qui à partir d'une liste d'élément de types ['a]
     produit un résultat de type ['b].
     On force ce changement de type pour que le typeur de Caml nous
     prévienne en cas d'oubli d'application d'une continuation. *)
  let rec cps_dfs (t: 'a tree) (k: 'a list -> 'b) : 'b =
    match t with
      (* Un arbre réduit à une feuille donne une liste vide d'étiquettes.
	 On applique la continuation à ce résultat. *)
      | Leaf -> k []
      | Node(a, t, u) ->
	(* On produit d'abord la liste d'étiquettes correspondant au sous-
	   arbre [t]. Le résultat est noté [dfst] et est transmis à la
	   continuation, qui commence par produire la liste d'étiquettes
	   correspondant au sous-arbre [u]. Le résultat est noté [dfsu]
	   est transmis à la continuation en charge de la dernière étape :
	   construire la liste résultat [a :: dfst @ dfsu] et la transmettre
	   à la continuation globale [k]. *)
	cps_dfs t (fun dfst ->
	  cps_dfs u (fun dfsu ->
	    k (a :: dfst @ dfsu)
	  )
	)
  in
  cps_dfs t (List.iter print_int)

(**
   Question 1 :
   - Modifier la fonction [cps_dfs] pour faire le parcours de droite à gauche
     (mais toujours en profondeur).

   Question 1bis pour creuser un peu plus :
   - Modifier la fonction [cps_dfs] pour faire un parcours en largeur.
     Indication : commencer par coder le parcours en largeur en style direct.
*)

    
(**  
   Question 2 : écrire en CPS une fonction
     [prefix: 'a -> 'a tree -> 'a list]
   qui affiche les éléments rencontrés avant le premier paramètre.
*)

(**
   Question 3 : écrire en CPS une fonction
     [find: 'a -> 'a tree -> 'a list option]
   telle que, si [a] existe dans [t], alors [find a t] renvoie la liste des
   nœuds sur un chemin de la racine vers [a].
*)

(**
   Cadeau : voici une fonction qui le fait en style direct, en utilisant
   des exceptions.
*)
exception Found of int list
let find a t =
  let rec find t = match t with
    | Leaf -> ()
    | Node(b, g, d) ->
      if a = b
      then raise (Found [])
      else
	try find g; find d
	with Found(path) -> raise (Found(b::path))
  in
  try find t; None
  with Found(path) -> Some path

(**
   Technique : CPS à deux canons.
   La fonction auxiliaire avec continuations prend deux continuations en
   paramètres :
   - la continuation [kf] est à utiliser si l'élément cherché a été trouvé
   - la continuation [knf] est à utiliser si l'élément n'a pas été trouvé
*)
let double_barrel_cps_find a t =
  let rec find t kf knf = match t with
    | Leaf -> (* À compléter *)
    | Node(b, g, d) -> (* À compléter *)
  in
  find t (* À compléter *)