val mystere : 'a list -> ('a -> 'b) -> 'b list
À partir du type de mystere
, tentez de deviner ce que fait cette fonction.
Il existe plusieurs types d'itérateurs :
map
:val map : 'a list -> ('a -> 'b) -> 'b list
iter
:val iter : 'a list -> ('a -> unit) -> unit
fold
:val fold_left : 'a list -> ('acc -> 'a -> 'acc) -> 'acc -> 'acc
val fold_right : 'a list -> ('a -> 'acc -> 'acc) -> 'acc -> 'acc
...
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