Pierre Weis Xavier Leroy
LE LANGAGE CAML
Deuxi`me ´dition e e
Copyright 1992, 1993, 2009 Pierre Weis et Xavier Leroy. Ce texte est distribu´ sous les termes de la licence Creative Commons BY-NC-SA. Le e texte complet de la licence est disponible ` l’adresse suivante : a
http://creativecommons.org/licenses/by-nc-sa/2.0/fr/legalcode
Voici un r´sum´ des droits et conditions de cettelicence. e e • Vous ˆtes libres : e – de reproduire, distribuer et communiquer cette cr´ation au public e – de modi?er cette cr´ation e • Selon les conditions suivantes : – Paternit´. Vous devez citer le nom de l’auteur original de la mani`re indiqu´e e e e par l’auteur de l’oeuvre ou le titulaire des droits qui vous conf`re cette e autorisation (mais pas d’une mani`re qui sugg´rerait qu’ils voussoutiennent e e ou approuvent votre utilisation de l’oeuvre). – Pas d’Utilisation Commerciale. Vous n’avez pas le droit d’utiliser cette cr´ation ` des ?ns commerciales. e a – Partage des Conditions Initiales ` l’Identique. Si vous modi?ez, transformez a ou adaptez cette cr´ation, vous n’avez le droit de distribuer la cr´ation qui e e en r´sulte que sous un contrat identique ` celui-ci. e a • A chaquer´utilisation ou distribution de cette cr´ation, vous devez faire ape e paraˆ clairement au public les conditions contractuelles de sa mise ` disposition. ?tre a La meilleure mani`re de les indiquer est un lien la page Web ci-dessus. e • Chacune de ces conditions peut ˆtre lev´e si vous obtenez l’autorisation du titue e laire des droits sur cette oeuvre. • Rien dans ce contrat ne diminue ou nerestreint le droit moral de l’auteur ou des auteurs.
` A ` A ` A ` A
mes parents, Suzanne et Michel, Lise, Marie, Jean-Baptiste et Ir`ne, e H´l`ne. ee
Pierre Weis
Table des mati`res e
Avant-propos xi
I
Programmer en Caml
1
3 5 5 6 6 8 13 13 15 17 19 19 27 28 31 37 37 39 40 42 46 47 49 50 52 53 57 57 59 61 64
Avertissement 1 Premiers pas 1.1 Id´es g´n´rales sur Caml e e e1.2 Dialoguer avec Caml 1.3 Les d´?nitions e 1.4 Fonctions 1.5 Valeurs et programmes 1.6 Impression 1.7 Conventions syntaxiques 1.8 Diagrammes syntaxiques 2 R´cursivit´ e e 2.1 Fonctions r´cursives simples e 2.2 D´?nitions par cas : le ?ltrage e 2.3 Les tours de Hanoi 2.4 Notions de complexit´ e 3 Programmation imp´rative e 3.1 La programmation imp´rative e 3.2 Boucles 3.3 Manipulation depolynˆmes o 3.4 Impression des polynˆmes o 3.5 Caract`res et chaˆ e ?nes de caract`res e 3.6 Les r´f´rences ee 3.7 Un programme utilisant des r´f´rences ee 3.8 R´cursivit´ et boucles e e 3.9 R`gle d’extensionnalit´ e e 3.10 E?ets et ´valuation e 4 Fonctionnelles et polymorphisme 4.1 Notion de polymorphisme 4.2 Fonctions d’ordre sup´rieur e 4.3 Typage et polymorphisme 4.4 Curry?cation
viii 4.5 4.6 4.7Une fonctionnelle de tri polymorphe La pleine fonctionnalit´ e Composition de fonctions
Table des mati`res e 65 67 70 75 75 77 78 81 83 84 85 88 91 98 103 105 109 109 113 116 116 118 118 120 122 125 125 126 130 133 135 140 143 144 147 147 148 149 149 152 154 155 155 156
5 Listes 5.1 Pr´sentation e 5.2 Programmation assist´e par ?ltrage e 5.3 Tri par insertion 5.4 Fonctionnelles simples surles listes 5.5 Les polynˆmes creux o 5.6 Filtrage explicite 5.7 Op´rations sur les polynˆmes creux e o 5.8 Animation des tours de Hanoi 5.9 Fonctionnelles complexes sur les listes 5.10 E?cacit´ des fonctions sur les listes : ´tude de cas e e 5.11 Listes et r´currence e ` 5.12 A la recherche de l’it´rateur unique e 6 Les structures de donn´es e 6.1 Polynˆmes pleins et polynˆmes creux o o 6.2 Typessommes ´labor´s e e 6.3 Les types somme 6.4 Les types produit 6.5 M´lange de types somme et types produit e 6.6 Structures de donn´es mutables e 6.7 Structures de donn´es et ?ltrage e 6.8 Structures de donn´es et r´currence e e 7 Le docteur 7.1 Vue d’ensemble 7.2 Les exceptions 7.3 Fonctions de recherche dans les listes 7.4 Traitements de chaˆ ?nes de caract`res e 7.5 Cam´lia e 7.6 Dialogue avec…