Table of Contents
Mes notes de cours en ligne: http://gasche.info/tmp/cours-ocaml-paris8-2020.org
Exercices: http://gasche.info/tmp/cours-ocaml-paris8-2020.html
Autre référence: un bon cours sur OCaml en ligne, de Maxence Guesdon, en français:
https://www.good-eris.net/formation-ocaml/
0.1 Livres sur OCaml:
- "Real World OCaml", disponible aussi en ligne (gratuitement), plutôt centré sur la pratique, suppose plutôt qu'on sait déjà programmer dans un autre langage https://dev.realworldocaml.org/index.html
- "OCaml from the Very Beginning", pour les débutants, très bon
- "Apprendre à programmer avec OCaml : Algorithmes et structures de données" utilisé pour des cours à l'université
- "Le langage Caml": très bon, plus édité, pour une très vieille version du langage (Caml Light), mais la plupart du cours reste pertinent pour OCaml
1 Cours 1: bases de OCaml (fonctions, tuples)
1.1 Exemple de programme
let rec split = function | [] -> ([], []) | [x] -> ([x], []) | x1::x2::rest -> let (r1, r2) = split rest in (x1::r1, x2::r2) let rec merge la lb = match la, lb with | [], li | li, [] -> li | a::ra, b::rb -> if a < b then a :: merge ra lb else b :: merge la rb let rec sort = function | [] -> [] | [x] -> [x] | li -> let l1, l2 = split li in merge (sort l1) (sort l2)
1.2 Présentation de l'outil Learn-OCaml
1.3 Définitions et fonctions.
1.3.1 Définition globale
let <nom> = <expression>
let me = "Gabriel" let message = "Bonjour " ^ me let bonjour name = "Bonjour " ^ name let greeting2 (name1 : string) name2 : string = "Bonjour " ^ name1 ^ " et " ^ name2 (* quand le nom n'a pas d'importance, on veut juste le résultat: *) let _ = 1 + 2
1.3.2 Définition locale
let <nom> = <expression> in <expression>
let x = 2 let x4 = let x2 = x * x in x2 * x2
Définition de fonction:
let <nom> <param1> <param2> ... = <expression>
let pow5 x = let x2 = x * x in x2 * x2 * x let abs x = if x >= 0 then x else (- x)
1.3.3 Fonctions
fun <nom> .. <nom> -> <expression>
let square = fun x -> x * x let square_dist = fun x y -> square x + square y let squares = List.map (fun x -> x * x) [1; 2; 3; 4; 5]
Remarque: les deux syntaxes suivantes sont équivalentes
let square x = x * x let square = fun x -> x * x
Remarque avancée: les trois syntaxes suivantes sont équivalentes
let square_dist x y = square x + square y let square_dist = fun x y -> square x + square y let square_dist = fun x -> fun y -> square x + square y (* et on peut écrire: *) let square_dist_to_one = square_dist 1 let _ = square_dist_to_one 2 let _ = square_dist 1 2
1.3.4 Polymorphisme
let id x = x let twice f x = f (f x) let compose f g = fun x -> f (g x)
1.3.5 Types
(fun x -> x) : 'a -> 'a (fun x -> x + 1) : int -> int (fun x -> x > 0) : int -> bool (fun b -> if b then 1 else (- 1)) : bool -> int (fun x y -> x + y > 0) : int -> int -> bool ( + ) : int -> int -> int (fun f x -> f x) : ('a -> 'b) -> 'a -> 'b
Définitions de type
type variable = string type arith_op = int -> int -> int type 't binop = 't -> 't -> 't type arith_op = int binop
*
1.4 N-uplets (tuples)
let date = (2020, 09, 21) (* int * int * int *) let next_year date = let (year, month, day) = date in (year + 1, month, day) let next_year (year, month, day) = (year + 1, month, day) let _ = next_year date
Remarque: 0-uplet noté ~unit~
, expression ~()~
let pas_de_valeur = () let main () = print_endline "Hello World!"
Exercice:
val swap : ('a * 'b) -> ('b * 'a)
Exercice:
val nom : string * int -> string val age : string * int -> int
2 Cours 2: bases de OCaml (sommes)
Une somme: le type d'une donnée qui est "soit un Truc, soit un Machin" – et on sait lequel des deux.
Très courant en pratique !
2.1 Définir un nouveau type somme
type <params> <nom> = | <Constructeur> of <type> * <type> * <...> | <Constructeur> of <type> * <type> * <...> <...>
type address = | Telephone of int * string | Email of string
Constructeurs sans paramètres:
type trois_elements = | A | B | C
2.2 Construire une expression de type somme
<Constructeur> (<expr>, <expr>, <...>)
let me = Email "gabriel.scherer@inria.fr" let not_really_me = Telephone (33, "123456789")
2.3 Inspecter/décomposer une valeur de type somme
match <expression> with | <Constructeur>(<nom>, <nom>, <...>) -> <expression> | <Constructeur>(<nom>, <nom>, <...>) -> <expression> | <...>
type address = | Telephone of int * string | Email of string let how_to_contact address = match address with | Email mail -> "send an email to <" ^ mail ^ ">" | Telephone(country_code, number) -> "call 0" ^ number ^ " or " ^ "+" ^ string_of_int country_code ^ "-" ^ number
Exercice:
val categorie : address -> string categorie (Email "gabriel.scherer@inria.fr") = "email" categorie (Telephone (33, "123456789")) = "numero"
Remarque: ~if .. then .. else~
est un cas particulier de ~match~
let abs x = if x >= 0 then x else (- x) let abs x = match x >= 0 with | true -> x | false -> (- x)
3 Cours 3: bases de OCaml (types paramétrés, filtrage, records)
3.1 Types paramétrés
type address = | Telephone of int * string | Email of string type 'ty option = | None | Some of 'ty let safe_div a b = if b = 0 then None else Some (a / b) let maybe_add a (b : int option) = match b with | None -> a | Some x -> a + x
Le type ~'a option~
est standard en OCaml, déjà présent dans
l'environnement de base.
Exercices:
val maybe_add : int -> int option -> int val bonjour : string option -> string bonjour None = "Bonjour" bonjour (Some "Alex") = "Bonjour Alex" val apply_opt : ('a -> 'b) option -> 'a option -> 'b option val if_opt : bool option -> 'a -> 'a -> 'a option if_opt (Some false) "toto" "tata" = Some "tata" if_opt (Some true) 1 37 = Some 1 if_opt None 1 37 = None val pair_opt : 'a option -> 'b option -> ('a * 'b) option
3.2 Motifs généraux
Dans le cas général, ce qui est à gauche de la flèche dans la
construction ~match~
s'appelle un "motif". Un motif "reconnaît"
certaines valeurs, et permet de donner des noms à ses sous-composants.
Nous avons déjà vu d'autres exemples de motifs avec la construction ~let~
:
<nom> let two = 1 + 1 _ let _ = 1 + 1 (<motif>, <motif>, <...>) let (y, m, d) = date
Les motifs peuvent être imbriqués ou mélangés:
let same_address addr1 addr2 = match (addr1, addr2) with | (Email em1, Email em2) -> em1 = em2 | (Telephone(cc1, n1), Telephone(cc2, n2)) -> cc1 = cc2 && n1 = n2 | _ -> false
Il est très courant de "matcher" sur un n-uplet quand on veut inspecter plusieurs choses à la fois. Dans ce cas les parenthèses ne sont pas nécessaires.
let same_address addr1 addr2 = match addr1, addr2 with | Email em1, Email em2 -> em1 = em2 | Telephone(cc1, num1), Telephone(cc2, num2) -> cc1 = cc2 && n1 = n2 | _ -> false
Attention! Un nom dans un motif est toujours interprété comme la déclaration d'une variable, quitte à cacher un nom existant.
Il n'y pas de test d'égalité sur les noms.
let my_email = "gabriel.scherer@inria.fr" let is_me address = match address with | Email my_email -> true | Email _ -> false | Telephone _ -> false let _ = is_me (Email "toto@example.com") (* version corrigée *) let is_me address = match address with | Email email -> email = my_email | Telephone _ -> false
3.3 Records
type <params> <nom> = { <champ>: <type>; <champ>: <type>; <...> } { <champ> = <expr>; <champ> = <expr>; ... } <expr>.<champ> { <champ> = <motif>; <champ> = <motif>; ... }
type point2d = { x: int; y: int; } let origin = { x = 0; y = 0 } let norm2 p = p.x * p.x + p.y * p.y
4 Cours 4: récursivité (entiers, types récursifs)
4.1 Fonctions récursives sur les entiers/chaînes
let rec <nom> = ... <nom> ...
let rec pow a n = if n = 0 then 1 else a * pow a (n - 1)
let rec repeat s n = if n = 0 then "" else s ^ repeat s (n - 1)
val repeat: string -> int -> string repeat "to" 3 = "tototo"
Schéma typique pour les fonctions récursives:
- un ou plusieurs "cas d'arrêt", où on répond immédiatement
- un ou plusieurs "cas récursifs", où on se rappelle sur un sous-problème
Idée d'ensemble: une fonction récursive résoud un problème en le découpant en sous-problèmes plus faciles.
Récursion avec accumulateur:
let pow a n = let rec pow' acc n = if n = 0 then acc else pow' (acc * a) (n - 1) in pow' 1 n
4.2 Fonction récursive sur un type algébrique
Exercices:
type point = Point of int * int type vecteur = Vect of int * int let deplace (Point (x, y)) (Vect (dx, dy)) = Point (x+dx, y+dy) type moves = | Done | Slide of vecteur * moves | Goto of point * moves Goto(Point(2,3), Slide(Vect(1,-1), Done)) val count_moves : moves -> int val end_point : point -> moves -> point (* val points : point -> moves -> point list *)
let rec count_moves m = match m with | Done -> 0 | Slide (vect, rest) -> 1 + count_moves rest | Goto (point, rest) -> 1 + count_moves rest
let rec count_moves moves = match moves with | Done -> 0 | Slide(vec, rest) -> 1 + count_moves rest | Goto(point, rest) -> 1 + count_moves rest let rec end_point depart moves = match moves with | Done -> depart | Slide(vec, rest)-> let point = deplace depart vec in end_point point rest | Goto(point, rest) -> end_point point rest
~moves~
est en fait un cas particulier de liste:
type moves = | Done | Slide of vecteur * moves | Goto of point * moves type 'a option = | None | Some of 'a type 'a mylist = | Nil | Cons of 'a * 'a mylist type 'a list = | [] | (::) of 'a * 'a list (* on peut écrire *) 1 :: [] 1 :: (2 :: []) 1 :: (2 :: (3 :: [])) (* syntaxe courte: [1; 2; 3] *) match li with | [] -> ... | a :: rest -> ... (* on peut redéfinir `moves` ainsi: *) type move = Slide of vecteur | Goto of point type moves = move list (* exercice *) val end_point : point -> moves -> point
type 'a list = | [] | (::) of 'a * 'a list let rec length li = match li with | [] -> 0 | a :: rest -> 1 + length rest
val length : 'a list -> int val nth : int -> 'a list -> 'a option (* nth 0 [1; 2; 3] = Some 1 nth 2 [1; 2; 3] = Some 3 nth 4 [1; 2; 3] = None *) val last : 'a list -> 'a option (* last [1; 2; 3] = Some 3 *)
let rec length li = match li with | [] -> 0 | a :: rest -> 1 + length rest
let rec nth n li = match li with | [] -> None | a :: rest -> if n = 0 then Some a else nth (n-1) rest
let rec last li = match li with | [] -> None | a :: rest -> match rest with | [] -> Some a | _ :: _ -> last rest let rec last li = match li with | [] -> None | a :: rest -> match last rest with | None -> Some a | Some last -> Some last let last li = let rec last' a li = match li with | [] -> Some a | b :: rest -> last' b rest in match li with | [] -> None | a :: rest -> last' a rest let last li = let rec last' o li = match li with | [] -> o | b :: rest -> last' (Some b) rest in last' None li
Remarque: la structure récursive des fonctions respecte la structure récursive des types.
Concept avancé: Arbres n-aires (documents, worklist, etc.)
type ('leaf, 'node) ntree = | Leaf of 'leaf | Node of 'node * ('leaf, 'node) ntree list let node n children = Node (n, children) type doc = (string, string) ntree let homepage = node "page" [ node "title" [ Leaf "Home Page" ]; node "menu" [ Leaf "foo/"; Leaf "bar/" ]; node "body" [ Leaf "..." ]; node "contact" [ node "email" [ Leaf "gabriel.scherer@inria.fr" ]; node "reddit" [ Leaf "gasche" ] ]; ] type 't worklist = ('t, unit) ntree let task t = Leaf t let group worklists = Node ((), worklists) let worklist = let teach = group [ task "prepare lecture"; task "go to class"; task "teach" ] in let code_review = group [ task "new major allocator"; task "statmemprof"; task "TRMC"; ] in group [ teach; code_review ]
type ('leaf, 'node) ntree = | Leaf of 'leaf | Node of 'node * ('leaf, 'node) ntree list type 't worklist = ('t, unit) ntree val replace : 't worklist -> ('t -> 't worklist) -> 't workslit let _ = replace worklist (fun task -> if task <> "prepare lecture" then task else group ["detailed plan"; "lecture notes"] val replace : ('a, 'n) ntree -> ('a -> ('b, 'n) ntree) -> ('b, 'n) ntree
5 Cours 5: récursivité (listes, ordre supérieur)
5.1 Fonctions d'ordre supérieur sur les listes
La définition des listes est une définition récursive comme les autres (standard, pas besoin de la redéfinir), avec juste une syntaxe un peu particulière pour les construteurs:
type 'a list = | [] (* liste vide *) | (::) of 'a * 'a list (* élément suivi d'une liste *)
De plus, la syntaxe `[a; b; c]` est disponible, comme une façon plus concise d'écrire `a :: (b :: (c :: []))`.
On analyse les listes par filtrage de motif:
match li with | [] -> ... (* cas liste vide *) | head :: rest -> (* élément suivi du reste de la liste *)
Les listes sont un type récursif, et les fonctions qui manipulent des listes seront souvent récursives. Par exemple:
let rec length li = match li with | [] -> 0 | _ :: rest -> 1 + length rest
Exercices:
val map : ('a -> 'b) -> 'a list -> 'b list val filter : ('a -> bool) -> 'a list -> 'a list val fold_left : ('v -> 'a -> 'a) -> 'v -> 'a list -> 'a list val fold_right : ('a -> 'v -> 'v) -> 'a list -> 'v -> 'v val append : 'a list -> 'a list -> 'a list val rev : 'a list -> 'a list val rev_append : 'a list -> 'a list -> 'a list
let rec map f li = match li with | [] -> [] | head :: rest -> f head :: map f rest let rec map f = function | [] -> [] | x :: xs -> f x :: map f xs append [1; 2; 3] [4; 5; 6] = [1; 2; 3; 4; 5; 6] let rec append li1 li2 = match li1 with | [] -> li2 | p :: r -> p :: append r li2
5.2 foldleft et foldright
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a fold_left f a [x1; x2; ...; xn] = f (... (f (f a x1) x2)) xn val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b fold_right f [x1; x2; ...; xn] a = f x1 (f x2 (... (f xn a) ..))
Exemple: calculer la taille d'une liste
let length li = fold_left (fun acc _elem -> 1 + acc) 0 li let length li = fold_right (fun _elem acc -> 1 + acc) li 0
Exemple: calculer la somme de tous les éléments (entiers) d'une liste:
let sum li = fold_left (fun acc e -> acc + e) 0 li
Exercice: calculer le plus grand élément d'une liste d'entiers positifs.
let list_max li = fold_left ??? 0 li let list_max li = fold_left (fun acc e -> if acc > e then acc else e) 0 li let list_max li = let update acc e = if acc > e then acc else e in fold_left update 0 li
La fonction `foldleft` applique son argument `f` d'abord au premier élément de la liste, puis à tous les éléments jusqu'au dernier.
La fonction `foldright` applique son argument `f` d'abord au dernier élément de la liste, puis à tous les éléments jusqu'au premier.
let rev li = fold_left (fun acc e -> e::acc) [] li let stutter li = fold_right (fun e acc -> e :: e :: acc) li []
Exercice: écrire une fonction
val count_yes_no : ('a -> bool) -> 'a list -> int * int let count_yes_no p li = fold_left (fun (y,n) e -> if p e then (y+1,n) else (y,n+1)) (0,0) li
tel que si `countyesno p li` vaut `(yes, no)`, alors `yes` est le nombre d'éléments `x` de `li` tels que `p x` est vrai, et `no` est le nombre d'éléments `x` de `li` tel que `p x` est faux.
Exercice avancé: une fonction
val eval_poly : int list -> int -> int
telle que, par exemple `evalpoly [a0; a1; a2; a3] x` est égale à `a0 + a1 * x + a2 * x2 + a3 * x3`.
let eval_poly li x = let update (sum, p) e = (sum + e * p, p * x) in let (sum, _) = fold_left update (0, 1) li in sum
5.3 Pipelines, collections (avancé)
5.3.1 Opérateur de pipeline
let ( |> ) x f = f x let add n = fun a -> a+n let double = fun a -> a*2 let _ = 2 |> add 3 |> double |> add 2
(En programmation objet, "method chaining")
Courant avec les collections:
input |> List.map (fun n -> n + 1) |> List.filter (fun n -> n < 10) |> List.sort
5.3.2 Collections (avancé)
Exercices avancés:
type 'a seq = unit -> 'a node and 'a node = Nil | Cons of 'a * 'a seq val empty : 'a seq val return : 'a seq val map : ('a -> 'b) -> 'a seq -> 'b seq val filter_map : ('a -> 'b option) -> 'a seq -> 'b seq val concat : 'a seq -> 'a seq -> 'a seq val concat_map : ('a -> 'b seq) -> 'a seq -> 'b seq
Remarque: utiliser ~map~
plusieurs fois (par exemple)
6 Cours 6: un peu de complexité
6.1 Exemples
Ajouter un élément à la fin d'une liste:
let add_to_end x li = append li [x]
Ajouter un élément en tête d'une liste:
let add_to_beginning x li = x :: li
Coût de calcul ?
Tester si un élément apparaît dans une liste
let rec mem x li = match li with | [] -> false | head :: rest -> head = x || mem x rest
Tester si une liste est incluse dans une autre:
let rec included li1 li2 = match li1 with | [] -> true | head :: rest -> mem head li2 && included rest li2 let rec included_sorted li1 li2 = match li1, li2 with | [], _ -> true | _ :: _, [] -> false | a1 :: r1, a2 :: r2 -> if a1 < a2 then false else if a1 = a2 then included r1 li2 else (* a1 > a2 *) included li1 r2 (* exercice *) let included l1 l2 = included_sorted (List.sort compare li1) (List.sort compare li2)
6.2 Notion de complexité
Comment parler de la vitesse d'une fonction ?
- Mesurer le temps ? Dépend de la machine.
- Mesurer le nombre d'instruction ? Dépend de l'entrée.
- Mesurer la variation du nombre d'instruction, "à la louche".
Notation O(…).
Ajouter un élément au début d'une liste: O(1) Ajouter un élément à la fin d'une liste: O(n) `reverse` naïf: O(n2) `reverse` malin: O(n)
Exemple concret: le programme qui génère la documentation du compilateur OCaml mettait 6s à assembler la page web finale. La plupart du temps était passé dans un appel à une fonction qui enlève les éléments dupliqués dans une liste, avec une implémentation en O(n2); utiliser un meilleur algorithme (basé sur un tri; O(n log n)) passe le temps de calcul à 0.4s.
6.3 Exemple de bug de complexité
let rec example n = if n = 0 then 1 else let a = example (n - 1) in a + a let rec example_slow n = if n = 0 then 1 else example_slow (n - 1) + example_slow (n - 1)
example(0) = K' example(n) = K + example(n-1) O(n)
Complexité de exampleslow?
exampleslow(n) = 2 * exampleslow(n-1) 2 * 2 * 2 * 2 * 2 * … * K' 2n O(2n)
6.4 À retenir
La complexité, c'est la mesure de l'augmentation du temps de calcul en fonction de l'augmentation de la taille de l'entrée, sans tenir compte du facteur multiplicatif précis.
Notions importantes:
- temps constant, O(1)
- temps linéaire, O(n)
- temps quadratique, O(n2)
- temps exponentiel, O(2n)
7 Cours 7: tableaux
7.1 Motivation: accès en temps constant
let rec nth i li = (* exercice: aller chercher le i-ìème élément dans li *) let li = [10; 11; 12] let _ = nth 2 li
Les listes permettent d'ajouter un nouvel élément en temps constant, mais l'accès à un élément existant est en temps linéaire (en la position).
Les tableaux sont une structure de donnée différente: leur taille est fixée à la création (ajouter un élément demande de recréer un nouveau tableau, coût linéaire), mais l'accès à un élément se fait en temps constant.
let t = [| 10; 11; 12 |] let _ = t.(2)
7.2 Utilisation de base
Pour créer un tableau on utilise soit un litéral `[| e1; e2; ..; en |]`, soit les fonctions
Array.make : int -> 'a -> 'a array Array.init : int -> (int -> 'a) -> 'a array
Pour accéder à la taille d'un tableau (opération en temps constant), on utilise la fonction `Array.length`.
Array.length : 'a array -> int
Exercice: ajouter la somme des éléments d'un tableau d'entier:
let sum_all (t : int array) = let rec sum_from i = if i >= Array.length t then 0 else t.(i) + sum_from (i + 1) in sum_from 0 let () = assert (sum_all [|1; 2; 3|] = 6)
Exercice: renverser un tableau (le premier élément du tableau en entrée devient le dernier élément du tableau en sortie):
let reverse t = (* exercice *) let () = let t = reverse [|1; 2; 3|] in assert (t.(0) = 3)
7.3 Modification en place
Un tableau OCaml est un espace modifiable, on peut changer la valeur des éléments en temps constant.
# let t = [|10; 11; 12|];; val t : int array = [|10; 11; 12|] # t.(1) <- 21;; - : unit = () # t;; - : int array = [|10; 21; 12|]
Par exemple, on peut imaginer un tableau qui représente la position de voitures sur une route: None s'il n'y a pas de voiture sur un segment de la route, et (Some "foo") s'il y a une voiture nommée "foo".
let route = [|None; None; Some "toto"; None; Some "tata"; None|]
On écrit une fonction (avance : string option array -> unit) qui fait avancer chaque voiture d'un segment vers la droite; les voitures à la fin de la route quittent la route.
let avance route = let rec loop i = if i < 0 then () else match route.(i) with | None -> () | Some voiture -> if i + 1 < Array.length route then begin route.(i + 1) <- Some voiture; end; route.(i) <- None in loop (Array.length route - 1)
let route = [|None; None; Some "toto"; None; Some "tata"; None|];; avance route;; route;; avance route;; route;;
7.4 Tableaux de tableaux
let matrice = Array.init 3 (fun i -> Array.init 3 (fun j -> (i, j)))
Exercice:
val count_true : bool array array -> int val negate : bool array array -> unit
Exercices:
val valid : 'a array array -> int * int -> bool val get : 'a array array -> int * int -> 'a val set : 'a array array -> int * int -> 'a -> unit
Exercice:
let dirs = [(0, 1); (0, -1); (1, 0); (-1, 0)] val count_true_neigbors : bool array array -> int * int -> int val negate_neighbors : bool array array -> int * int -> unit
8 Cours avancé: Property-based testing
8.1 vérifier des propriétés par le test
Formule avec quantificateurs "pour tout": forall li. List.append li [] = li
Idée: tester la formule par génération aléatoire.
#use "topfind";; #require "qcheck";; let test_neutral_right = QCheck.Test.make ~name:"forall li. append li [] = li" QCheck.(list int) (fun li -> List.append li [] = li) let _ = QCheck_runner.run_tests ~verbose:true [ test_neutral_right ] let test_head = QCheck.Test.make ~name:"forall la lb. head (append la lb) = head la" QCheck.(pair (list int) (list int)) (fun (la, lb) -> List.hd (List.append la lb) = List.hd la) let _ = QCheck_runner.run_tests ~verbose:true [ test_head ]
let test_head = QCheck.Test.make ~name:"forall la lb. head (append la lb) = head la" QCheck.(pair (list int) (list int)) (fun (la, lb) -> QCheck.assume (la <> []); (List.hd (List.append la lb) = List.hd la)) let _ = QCheck_runner.run_tests ~verbose:true [ test_head ]
let rec sum_naive a b = if a = 0 then b else if a > 0 then sum_naive (a - 1) (b + 1) else sum_naive (a + 1) (b - 1) let test_sum = QCheck.Test.make ~name:"(a + b)" QCheck.(let i = int_range (-10) 10 in pair i i) (fun (a, b) -> (a + b) = sum_naive a b) let _ = QCheck_runner.run_tests ~verbose:true [ test_sum ]
8.2 property-testing et force des conditions
let rec sum li = match li with | [] -> 0 | n :: ns -> n + sum ns let even n = (n mod 2 = 0) let test_sum_even = QCheck.Test.make ~name:"even lists have an even sum" QCheck.(list int) (fun li -> QCheck.assume (List.for_all even li); even (sum li)) let _ = QCheck_runner.run_tests ~verbose:true [ test_sum_even ] let test_sum_even = QCheck.Test.make ~name:"even lists have an even sum" QCheck.(list (map (fun n -> 2*n) int)) (fun li -> QCheck.assume (List.for_all even li); even (sum li)) let _ = QCheck_runner.run_tests ~verbose:true [ test_sum_even ]
Difficulté: comment "inverser" une condition de bonne formation pour obtenir un générateur qui la satisfait le plus souvent ?
On veut tester un compilateur => comment générer un programme syntaxiquement valide?
8.3 property-testing et conception d'APIs
val split : sep:string -> string -> string list split ~sep:"," "foo,bar" = ["foo"; "bar"]
Question : que renvoyer dans les cas tordus ?
split ~sep:"" "toto" split ~sep:"," "toto" ["toto"] split ~sep:"," "" [] [""] split ~sep:"," "," [""; ""] split ~sep:"," ",," [""; ""; ""]
join ~sep (split ~sep input) = input
Question: quelles propriétés pour ~split~
?
Propriété proposée par la salle:
assume (not (String.contains ~sep input)); split ~sep input = [input]
Propriété supplémentaire (trop compliquée):
forall sep input1 input2. assume (sep <> ""); split ~sep (input1 ^ input2) = merge_splits (split ~sep input1) (split ~sep input2) sachant que merge_splits (li1 @ [x]) ([y] @ li2) = li1 @ [x ^ y] @ li2
Propriétés de sérialisation:
val foo_of_json : JSON.t -> foo val json_of_foo : foo -> JSON.t forall foo. equal_foo foo_of_json (json_of_foo foo) foo forall json. let json_carré = json_of_foo (foo_of_json json) in json_carré = json_of_foo (foo_of_json json_carré)