[Vos questions] suscitées par le tutoriel "L'approche qualité avec Objective-Caml"
Posez ici vos questions concernant le document en ligne L'approche qualité avec Objective-Caml.
Vous pouvez demander des compléments d'explication aussi bien sur les parties "cours" (les parties I, II et V) que sur les parties "application" (les parties III, IV et VI).
Quelques remarques utiles:
- utilisez le vocabulaire du tutoriel, en particulier un nom auquel est associé une valeur immuable est ou bien une variable (si la valeur ne peut être déterminée qu'à l'exécution) ou bien une constante (si la valeur peut être déterminée à la compilation)
- chaque chapitre est accessible par une balise html, de chapitre_1 à chapitre_47
Une liste des principales fonctionnalités du langage OCaml qui seront abordées dans les parties VII et VIII:
- le mot-clé when
- la définition de types exception
- les types algébriques
Une liste des autres principales fonctionnalités du langage OCaml (non couvertes par ce tutoriel):
- la notion d'êta-équivalence et les types '_a
- les mots-clé function, lazy, with, try...with
- les motifs pat1 | pat2
- l'égalité physique ==
- les fichiers d'interface *.mli
- les variants polymorphes
- les foncteurs
- la POO
- les labels
Pour les oublis, les fautes, les erreurs, les liens morts et autres modifications à apporter, veuillez me les soumettre par message privé, ceci afin de préserver au maximum cet espace au bénéfice des personnes en demande d'un soutien.
exercice pour le chapitre 57. Les catamorphismes
On revient sur le module du chapitre 57 qui implémente les arbres binaires 'a tree avec éléments aux noeuds, de taille size et de profondeur depth.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| module BinaryTree = struct
type 'a tree =
| Leaf
| Node of ('a tree) * 'a * ('a tree)
let fold f init t =
let rec loop t =
match t with
| Leaf -> init
| Node(l,a,r) -> f (loop l) a (loop r)
in loop t
let size t = fold (fun l a r -> l + r + 1) 0 t
let depth t = fold (fun l a r -> max l r + 1) 0 t
let mem x t = fold (fun l a r -> l or x=a or r) false t
end;; |
La fonction mem teste l'appartenance de x à un arbre binaire t.
Un arbre binaire ordonné est un arbre binaire qui vérifie les deux propriétés suivantes:
- l'élément porté par un fils gauche est strictement plus petit que l'élément porté par son parent
- l'élément porté par un fils droit est strictement plus grand que l'élément porté par son parent
Question 1:
La fonction mem x t effectue la recherche dans un arbre binaire (ordonné ou non).
Codez une fonction insert x t qui effectue l'ajout d'un élément x dans un arbre binaire ordonné t.
Question 2:
Recodez la fonction insert x t, mais cette fois-ci sans utiliser la récursion, à la place utilisez le catamorphisme fold.
EDIT: je m'excuse pour ceux qui ont cherché à coder le prédicat ordered qui dit si un arbre binaire est ordonné, cette question est probablement trop difficile, j'avais édité ce message et je croyais l'avoir retirée à temps mais apparemment ça n'était pas le cas.
