TD6

(* Feuille de TD 6 *)

(* Exercice 1 *)

type 'a list = Vide | Const of 'a * 'a list

let rec inserer a l =
  match l with
    Vide -> Const (a, Vide)
  | Const (x, l') -> Const (x, inserer a l')

let decaler l =
  match l with
    Vide -> failwith "Liste Vide"
  | Const (h, t) -> inserer h t

let rec applyn f x n =
  if n > 0 then applyn f (f x) (n-1) else x

let rotation l n = applyn decaler l n

let _ = rotation [1;2;3;4] 2

(* Exercice 3 *)

type tree = Val of int | Node of int * tree * tree

(* Pour réaliser la multiplication sur un arbre on a deux cas
   - soit on a une feuille et on retourne sa valeur
   - soit on a un noeud, et on multiplie sa valeur et celles de ces fils
   - le schéma ressemble à celui du fold sur les listes, la fonction est ici une
   fonction ternaire qui combine la valeur du noeud et celles de ces fils *)

let rec tree_fold =
  fun f g t ->
  match t with
    Val x -> g x
  | Node (n, a, b) -> f n (tree_fold f g a) (tree_fold f g b)

let rec mult = tree_fold (fun x y z -> x * y * z) (fun x -> x)

let _ = mult (Node (1, Node (2, Val 3, Val 4), Val 5))

let in0 = tree_fold (fun x y z -> x = 0 || y || z) (fun x -> x = 0)

exception ZeroFound

let mult0 = fun t ->
  if in0 t then raise ZeroFound else mult t

let mult_exn = fun t ->
  try mult0 t with ZeroFound -> 0

(* Exercice 4 *)

(* Partie 1 *)

type 'a tab = int -> 'a

let init_tab (e : 'a) : 'a tab  = fun x -> e

let val_tab (t : 'a tab) (i : int) : 'a = t i

let maj_tab (t : 'a tab) (i : int) (e : 'a) =
  fun x -> if x = i then e else t i

(* Partie 2 *)


type message = Taille | Val of int

type itab = message -> int

let tableau (n : int) ( e : int) : itab  =
  let t = init_tab e in
  fun x ->
    match x with
      Taille -> n
    | Val i -> val_tab t i

let maj (t :itab) (i : int) (e : int) : itab =
  fun x ->
  match x with
    Val j when i = j -> e
  | _ -> t x