Itérateurs

val mystere : 'a list -> ('a -> 'b) -> 'b list

À partir du type de mystere, tentez de deviner ce que fait cette fonction.

Les itérateurs : traverser un type de donnée

Il existe plusieurs types d'itérateurs :

  • Le map:
val map : 'a list -> ('a -> 'b) -> 'b list
  • L'iter:
val iter : 'a list -> ('a -> unit) -> unit
  • Le fold:
val fold_left : 'a list -> ('acc -> 'a -> 'acc) -> 'acc -> 'acc
val fold_right : 'a list -> ('a -> 'acc -> 'acc) -> 'acc -> 'acc

...

Faites les exercices

Récursion terminale

Lorsqu'une fonction termine par un (unique) appel récursif, on dit qu'elle est récursive terminale.

let rec length l = match l with 
  | [] -> 0
  | _ :: q ->
    let lq = length q in
    lq + 1
let rec length l = match l with 
  | [] -> 0
  | _ :: q -> 1 + (length q)
let rec length acc l = match l with 
  | [] -> acc
  | _ :: q -> length (acc + 1)

Une fonction récursive terminale ne fera pas de Stack_overflow. Comparons l'execution dans le cas non-récursif terminal:

   length [1; 2; 3]
=> 1 + length [2; 3]
=> 1 + (1 + length [3])
=> 1 + (1 + (1 + length []))
=> 1 + (1 + (1 + 0))
=> 1 + (1 + 1)
=> 1 + 2
=> 3

et dans le cas récursif terminal:

   length 0 [1; 2; 3]
=> length 1 [2; 3]
=> length 2 [3]
=> length 3 []
=> 3

Refaire les exercices en mode "récursif terminale"