Mes notes de cours en ligne:
  http://gasche.info/doc/cours-ocaml-paris8-2019.org

Exercices:
  http://gasche.info/tmp/cours-ocaml-paris8-2019.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/

* Cours 1: bases de OCaml (fonctions, tuples)
** Présentation de l'outil Learn-OCaml
URL (va changer): https://mlocaml17-postproceedings-hotcrp.saclay.inria.fr/
TODO: gasche.info/learn-ocaml-paris8-2019
** Définitions et fonctions.
*** Définition globale
#+BEGIN_SRC
let <nom> = <expression>
#+END_SRC

#+BEGIN_SRC ocaml
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
#+END_SRC

*** Définition locale
#+BEGIN_SRC
let <nom> = <expression> in <expression>
#+END_SRC

#+BEGIN_SRC ocaml
let x = 2

let x4 =
  let x2 = x * x in
  x2 * x2
#+END_SRC

Définition de fonction:
#+BEGIN_SRC 
let <nom> <param1> <param2> ... = <expression>
#+END_SRC

#+BEGIN_SRC ocaml
let pow5 x =
  let x2 = x * x in
  x2 * x2 * x

let abs x =
  if x >= 0 then x
  else (- x)
#+END_SRC

*** Fonctions
#+BEGIN_SRC
fun <nom> .. <nom> -> <expression>
#+END_SRC

#+BEGIN_SRC ocaml
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]
#+END_SRC

Remarque: les deux syntaxes suivantes sont équivalentes
#+BEGIN_SRC ocaml
let square x = x * x
let square = fun x -> x * x
#+END_SRC

Remarque avancée: les trois syntaxes suivantes sont équivalentes
#+BEGIN_SRC ocaml
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
#+END_SRC
*** Polymorphisme
#+BEGIN_SRC ocaml
let id x = x
let twice f x = f (f x)
let compose f g = fun x -> f (g x)
#+END_SRC

*** Types
#+BEGIN_SRC ocaml
(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
#+END_SRC

Définitions de type
#+BEGIN_SRC ocaml
type variable = string

type arith_op = int -> int -> int

type 't binop = 't -> 't -> 't
type arith_op = int binop
#+END_SRC

** N-uplets (tuples)
#+BEGIN_SRC ocaml
let date = (2019, 09, 16)
(*
  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
#+END_SRC

Remarque: 0-uplet noté ~~unit~~, expression ~~()~~
#+BEGIN_SRC ocaml
let pas_de_valeur = ()

let main () =
  print_endline "Hello World!"
#+END_SRC

Exercice:
#+BEGIN_SRC ocaml
val swap : ('a * 'b) -> ('b * 'a)
#+END_SRC

Exercice:
#+BEGIN_SRC ocaml
val nom : string * int -> string
val age : string * int -> int
#+END_SRC
* 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 !

** Définir un nouveau type somme

#+BEGIN_SRC
type <params> <nom> =
  | <Constructeur> of <type> * <type> * <...>
  | <Constructeur> of <type> * <type> * <...>
  <...>
#+END_SRC

#+BEGIN_SRC ocaml
type address =
  | Telephone of int * string
  | Email of string
#+END_SRC

Constructeurs sans paramètres:

#+BEGIN_SRC ocaml
type trois_elements =
  | A
  | B
  | C
#+END_SRC

** Construire une expression de type somme

#+BEGIN_SRC
<Constructeur> (<expr>, <expr>, <...>)
#+END_SRC

#+BEGIN_SRC ocaml
let me = Email "gabriel.scherer@inria.fr"
let not_really_me = Telephone (33, "123456789")
#+END_SRC

** Inspecter/décomposer une valeur de type somme

#+BEGIN_SRC
match <expression> with
| <Constructeur>(<nom>, <nom>, <...>) -> <expression>
| <Constructeur>(<nom>, <nom>, <...>) -> <expression>
| <...>
#+END_SRC

#+BEGIN_SRC ocaml
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
#+END_SRC

Exercice:
#+BEGIN_SRC ocaml
val categorie : address -> string
categorie (Email "gabriel.scherer@inria.fr") = "email"
categorie (Telephone (33, "123456789")) = "numero"
#+END_SRC

Remarque: ~~if .. then .. else~~ est un cas particulier de ~~match~~
#+BEGIN_SRC ocaml
let abs x =
  if x >= 0 then x else (- x)

let abs x =
  match x >= 0 with
  | true -> x
  | false -> (- x)
#+END_SRC

* Cours 3: bases de OCaml (types paramétrés, filtrage, records)
** Types paramétrés

#+BEGIN_SRC ocaml
type address =
  | Telephone of int * string
  | Email of string

type 'a option =
  | None
  | Some of 'a

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

let maybe_add a b = 
match b with 
| None -> a
| Some toto -> a + toto
#+END_SRC

Le type ~~'a option~~ est standard en OCaml, déjà présent dans
l'environnement de base.

Exercices:
#+BEGIN_SRC
val maybe_add : int -> int option -> int
val apply_opt : ('a -> 'b) option -> 'a option -> 'b option
#+END_SRC

** 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~~:
#+BEGIN_SRC ocaml
<nom>                       let two = 1 + 1
_                           let _ = 1 + 1
(<motif>, <motif>, <...>)   let (y, m, d) = date
#+END_SRC

Les motifs peuvent être imbriqués ou mélangés:
#+BEGIN_SRC ocaml
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
#+END_SRC

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.

#+BEGIN_SRC ocaml
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
#+END_SRC

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.

#+BEGIN_SRC ocaml
let my_email = "gabriel.scherer@inria.fr"

let is_me address =
  match address with
  | Email my_email -> true
  | Email _ -> false
  | Telephone _ -> false

let _ = assert (is_me (Email "toto@example.com"))
#+END_SRC

** Records
#+BEGIN_SRC
type <params> <nom> = {
  <champ>: <type>;
  <champ>: <type>;
  <...>
}

{ <champ> = <expr>; <champ> = <expr>; ... }

<expr>.<champ>

{ <champ> = <motif>; <champ> = <motif>; ... }
#+END_SRC

#+BEGIN_SRC ocaml
type point2d = {
  x: int;
  y: int;
}

let origin = { x = 0; y = 0 }

let norm2 p = p.x * p.x + p.y * p.y
#+END_SRC

* Cours 4: récursivité (entiers, types récursifs)
** Fonctions récursives sur les entiers/chaînes

#+BEGIN_SRC
let rec <nom> = ... <nom> ...
#+END_SRC

#+BEGIN_SRC ocaml
let rec pow a n =
  if n = 0 then 1
  else a * pow a (n - 1)
#+END_SRC
#+BEGIN_SRC ocaml
let rec repeat s n =
  if n = 0 then ""
  else s ^ repeat s (n - 1)
#+END_SRC

#+BEGIN_SRC ocaml
val repeat: string -> int -> string
repeat "to" 3 = "tototo"
#+END_SRC

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:

#+BEGIN_SRC ocaml
let pow a n =
  let rec pow' acc n =
    if n = 0 then acc
    else pow' (acc * a) (n - 1)
  in pow' 1 n
#+END_SRC

** Fonction récursive sur un type algébrique

Exercices:
#+BEGIN_SRC ocaml
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

val count_moves : moves -> int
val end_point : point -> moves -> point 
(* val points : point -> moves -> point list *)
#+END_SRC

#+BEGIN_SRC ocaml
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
#+END_SRC

~~moves~~ est en fait un cas particulier de liste:
#+BEGIN_SRC ocaml
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
#+END_SRC

#+BEGIN_SRC ocaml
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 *)
#+END_SRC

#+BEGIN_SRC ocaml
let rec length li =
  match li with
  | [] -> 0 
  | a :: rest -> 1 + length rest  
#+END_SRC

#+BEGIN_SRC ocaml
let rec nth n li =
 match li with
  | [] -> None
  | a :: rest ->
    if n=0 then Some a
    else nth (n-1) rest
#+END_SRC

#+BEGIN_SRC ocaml
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
#+END_SRC

Remarque: la structure récursive des fonctions respecte la structure
récursive des types.

Concept avancé: Arbres n-aires (documents, worklist, etc.)
#+BEGIN_SRC ocaml
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 ]
#+END_SRC

#+BEGIN_SRC ocaml
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
#+END_SRC
* Cours 5: récursivité (listes, ordre supérieur)
** 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:

#+BEGIN_SRC ocaml
type 'a list =
  | [] (* liste vide *)
  | (::) of 'a * 'a list (* élément suivi d'une liste *)
#+END_SRC

De plus, la syntaxe `[a; b; c]` est disponible, comme une façon plus
concise d'écrire `a :: (b :: (c :: []))`.

Exercices:
#+BEGIN_SRC ocaml
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
#+END_SRC

Remarque: sens de propagation des informations pendant le calcul:
- de l'appelant à l'appelé (fold_left, rev)
- de l'appelé à l'appelant (map, append, fold_right)

** Pipelines, collections (exemples)
*** Opérateur de pipeline

#+BEGIN_SRC ocaml
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
#+END_SRC

(En programmation objet, "method chaining")

Courant avec les collections:
#+BEGIN_SRC ocaml
input
|> List.map (fun n -> n + 1)
|> List.filter (fun n -> n < 10)
|> List.sort
#+END_SRC

*** Collections (avancé)

Exercices avancés:
#+BEGIN_SRC ocaml
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 concat : 'a seq -> 'a seq -> 'a seq
val concat_map : ('a -> 'b seq) -> 'a seq -> 'b seq
#+END_SRC

Remarque: utiliser ~~map~~ plusieurs fois (par exemple)
* Cours 6: références, boucles, tableaux

En OCaml, une déclaration de variable conserve toujours la même valeur
dans la portée où elle est accessible.

Pour pouvoir modifier de l'état, il faut utiliser des constructions
explicites de mémoire modifiable, les *références* et les *tableaux*.

** Références

#+BEGIN_SRC ocaml
# let x = ref 1;;
val x : int ref = {contents = 1}
# x := 2;;
#+END_SRC


* Cours avancé: Property-based testing
** 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.

#+BEGIN_SRC ocaml
#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 ]
#+END_SRC

#+BEGIN_SRC ocaml
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 ]
#+END_SRC

#+BEGIN_SRC ocaml
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 ]
#+END_SRC

** property-testing et force des conditions

#+BEGIN_SRC ocaml
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 ]
#+END_SRC

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?

** property-testing et conception d'APIs

#+BEGIN_SRC ocaml
val split : sep:string -> string -> string list

split ~sep:"," "foo,bar" = ["foo"; "bar"]
#+END_SRC

Question : que renvoyer dans les cas tordus ?
#+BEGIN_SRC ocaml
split ~sep:"" "toto"
split ~sep:"," "toto" ["toto"]
split ~sep:"," ""    []  [""]
split ~sep:"," ","   [""; ""]
split ~sep:"," ",,"  [""; ""; ""]
#+END_SRC

join ~sep (split ~sep input) = input

Question: quelles propriétés pour ~~split~~?

Propriété proposée par la salle:
#+BEGIN_SRC
assume (not (String.contains ~sep input));
split ~sep input = [input]
#+END_SRC

Propriété supplémentaire (trop compliquée):
#+BEGIN_SRC
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
#+END_SRC

Propriétés de sérialisation:
#+BEGIN_SRC
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é)
#+END_SRC