(* Exercice 1 *)
let iterate l n =
  let rec aux n acc =
    if n = 0 then acc
    else aux (n - 1) (l @ acc)
  in aux n []

let rec cut_prefix prefix l =
  match prefix, l with
    [], _ -> true, l
  | _, [] -> false, []
  | x :: t, x' :: t' -> if x = x' then cut_prefix t t'
			else false, []

let rec is_iter l1 l2 =
  l2 = [] ||
    let p, s = cut_prefix l1 l2 in
    p && is_iter l1 s

(* Exercice 2 *)
type poly = int list

let rec poly_sum p1 p2 =
  match p1, p2 with
    [], _ -> p2
  | _, [] -> p1
  | c1 :: t1, c2 ::t2 -> (c1 + c2) :: poly_sum t1 t2

let rec multdeg n poly =
  if n = 0 then poly
  else multdeg (n - 1) (0 :: poly)

let rec multcons c poly =
  List.map (fun n -> c * n) poly

let rec remove_zeros l =
  match l with
    [] -> []
  | x :: t -> if x = 0 then remove_zeros t else l

let degree poly =
  if p = [] then 0
  else List.length (remove_zeros (List.rev poly)) - 1

let rec poly_mult p1 p2 =
  match p1 with
    [] -> []
  | c0 :: t -> poly_sum (multcons c0 p2) (multdeg 1 (poly_mult t p2))

let rec evaluate poly n =
  match poly with
    [] -> 0
  | c :: p -> (evaluate p n) * n + c

(* Exercice 3 *)
type dir = D | G
type 'a itree = dir list -> 'a

(* Exercice 3 *)
(* l'arbre dont tous les noeuds ont l'étiquette 1 *)
	      
let t_depth = fun l -> List.length l

let t_right = fun l -> l != [] && List.hd (List.tl l) = D
		     
let rec sub_right itree =
  fun directions -> itree (D :: directions)

type 'a btree = Empty | Node of 'a * 'a btree * 'a btree

let rec sub_left itree =
  fun directions -> itree (G :: directions)

let rec itree_to_btree itree n =
  if n = 0 then Node(t [], Empty, Empty)
  else Node(itree [], 
	    itree_to_btree (sub_left itree) (n - 1),
	    itree_to_btree (sub_right itree) (n - 1))