Introduction a laprogrammation fonctionnelle et au langage Caml

Algorithmes et structures de donnees. Une introduction a laprogrammation fonctionnelle et au langage CamlJocelyn Serot22 avril 2004PreambuleCe document constitue une introduction a la programmation fonctionnelle { et en particulier au langageObjective Caml { a travers la mise en uvre de structures de donnees classiques en informatique (listes,arbres, graphes). Dans cette optique, les implantations et les algorithmes proposes restent deliberementsimples. Il existe de nombreux documents traitant de maniere beaucoup plus approfondie des aspects pu-rement algorithmiques. Par ailleurs, bien que ce cours puisse ^etre vu comme une initiation a Caml, il neconstitue en aucune fa con une formation complete a ce langage et encore moins d’un manuel de reference.Le lecteur est donc invite, correlativement, a se reporter aux ouvrages, documents et publications (pourla plupart disponibles en lignes) traitant du langage et de ses applications (voir la bibliographie en n dedocument).La forme du document privilegie une approche < en situation > des problemes, les types de donneeset fonctions etant construits et valides < en temps reel> via un interpreteur Caml. Ces notes constituentune trace commentee de ces sessions de travail : les phrases entrees par le programmeur sont precedees ducaractere d’invite # et suivies de la reponse de l’interpreteur.1Chapitre 1Rudiments1.1 Expressions, valeurs et typesLa notion cle en Caml (et plus ...