Un décideur

Exercice · OCaml (option informatique), chapitre 20 — Calculabilité et décidabilité

Énoncé

Écrire un décideur pour « tous les éléments de la liste l sont positifs » et justifier qu'il s'arrête toujours.

Corrigé

let rec tous_positifs l =
  match l with
  | [] -> true
  | x :: reste -> x > 0 && tous_positifs reste

La récursion porte sur une liste strictement plus courte à chaque appel : elle atteint [] en un nombre fini d'étapes (variant : la longueur). La fonction s'arrête sur toute entrée et donne la bonne réponse : le problème est décidable.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.