# 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"