Seance 2 -- Traitements des donnees

2.1 Systeme de typage

Definition — Types parametriques et variant

En OCaml, les types sont parametriques (generiques) et les types variant (algebriques) permettent de definir des structures de donnees par cas.

(* Type parametre *)
type ('a, 'b) pair = { fst: 'a; snd: 'b }

(* Type variant (somme) *)
type forme =
  | Cercle of float
  | Rectangle of float * float
  | Triangle of float * float * float

(* Type recursif (liste personnalisee) *)
type 'a mylist =
  | Nil
  | Cons of 'a * 'a mylist

(* Type pour les expressions arithmetiques *)
type expr =
  | Cst of float
  | Add of expr * expr
  | Mul of expr * expr

let rec eval = function
  | Cst c       -> c
  | Add (e1, e2) -> eval e1 +. eval e2
  | Mul (e1, e2) -> eval e1 *. eval e2

2.1.1 Types variant

Correspondance

Un type variant = somme de cas (comme un union en C, mais type-safe).
Un record = produit de champs (comme un struct).

2.2 Listes et operations fonctionnelles

Les trois operations fondamentales sur les listes :

(* fold_left : parcourt la liste, accumule un resultat *)
let rec fold_left f acc = function
  | [] -> acc
  | x :: xs -> fold_left f (f acc x) xs

(* map : applique une fonction a chaque element *)
let rec map f = function
  | [] -> []
  | x :: xs -> f x :: map f xs

(* filter : garde les elements satisfaisant un predicat *)
let rec filter p = function
  | [] -> []
  | x :: xs -> if p x then x :: filter p xs
               else filter p xs

(* Exemples d'utilisation *)
let somme lst = fold_left (+) 0 lst
let longueur lst = fold_left (fun acc _ -> acc + 1) 0 lst
let carres lst = map (fun x -> x * x) lst
let pairs lst = filter (fun x -> x mod 2 = 0) lst

(* Pipeline : traitement compose *)
let traitement lst =
  lst |> filter (fun x -> x > 0)
     |> map (fun x -> x * x)
     |> fold_left (+) 0

2.3 L'operateur `|>` et les dataflows

Definition — Pipe operator

let (|>) x f = f x
Passe le resultat de gauche comme premier argument de la fonction de droite. Lisibilité : on lit de gauche a droite comme un flux de donnees.

(* Sans pipe : imbriqué et illisible *)
fold_left (+) 0 (map (fun x -> x * x) (filter (fun x -> x > 0) lst))

(* Avec pipe : lecture naturelle *)
lst |> filter (fun x -> x > 0)
   |> map (fun x -> x * x)
   |> fold_left (+) 0

2.4 Monades : return et bind

Definition — Monade

Une monade 'a m est un type parametrique avec deux operations :

return : 'a -> 'a m (envelopper une valeur)
bind : 'a m -> ('a -> 'b m) -> 'b m (enchaainer des calculs)

Avec les trois lois : identite a gauche, identite a droite, associativite.

2.4.1 La monade option

(* Option : gerer l'absence de valeur *)
let return_option x = Some x

let bind_option m f =
  match m with
  | None   -> None
  | Some x -> f x

(* Syntaxe let* pour enchaainer *)
let (let*) = bind_option

let diviser a b =
  if b = 0 then None else Some (a /. b)

let calculer x =
  let* a = diviser 100.0 x in
  let* b = diviser a (x -. 1.0) in
  return_option (b +. 1.0)

2.4.2 La monade list

(* List : calcul non-deterministe / combinatoire *)
let bind_list xs f =
  List.concat (List.map f xs)

(* Combinaisons : paires de couleurs *)
let combinaisons =
  bind_list ["rouge"; "bleu"] (fun c1 ->
  bind_list ["S"; "M"; "L"] (fun c2 ->
  [(c1, c2)]))
(* = [("rouge","S"); ("rouge","M"); ... ("bleu","L")] *)

2.5 Tables et dictionnaires

(* Listes d'association *)
let etudiants = [(123, "Alice"); (456, "Bob"); (789, "Charlie")]

let cle k lst = List.assoc k lst

(* Hashtbl (mutable, plus efficace) *)
let tbl = Hashtbl.create 16
let () = Hashtbl.add tbl 123 "Alice"
let () = Hashtbl.add tbl 456 "Bob"
let trouve = Hashtbl.find_opt tbl 123  (* Some "Alice" *)
let () = Hashtbl.replace tbl 123 "Alice Marie"

2.6 Application — Calcul vectoriel

(* Vecteurs comme listes de float *)
let dot_product v1 v2 =
  List.fold_left2 (+.) 0.0 v1 v2

let vec_add v1 v2 = List.map2 (+.) v1 v2
let vec_scale c v = List.map (( *. ) c) v
let vec_norme v = sqrt (dot_product v v)

Descente de gradient — Regression lineaire

(* Gradient descente : theta_{k+1} = theta_k - alpha * nabla J *)
let gradient_descente f grad theta0 alpha n =
  let rec aux theta k =
    if k = 0 then theta
    else aux (vec_add theta (vec_scale (-. alpha) (grad theta))) (k - 1)
  in aux theta0 n

Exercices

Implementez fold_right en termes de fold_left.
Implementez la multiplication de matrices (listes de listes).
Etendez la monade option avec map et join.
Implementez group_by : ('a -> 'b) -> 'a list -> ('b * 'a list) list.

Seance 2 — Traitements des donnees