Programmation OCaml

Sauf mention explicite du contraire, tout le code disponible sur cette page est distribué selon les termes de la GNU Library General Public License version 2, avec une exception concernant l'édition de lien, décrite dans le fichier LICENSE.

À propos des liens ci-dessous :

• Les .ps sont des fichiers PostScript produits à partir du source OCaml grâce à ocamlweb.
  
• Les .ml et .mli ont été produits avec l'outil caml2html de Sébastien Ailleret (maintenant Martin Jambon).
  
• Cliquer sur le nom de la bibliothèque / de l'application pour télécharger.
• Lorsqu'un dépôt github ou un paquet opam existe, il est indiqué entre parenthèses.

Structures de données

• Vector : Tableaux redimensionnables (.mli / .ml)

• Parray : Tableaux persistants (.mli / .ml) ; voir cet article

• Puf : Union-Find persistant (.mli / .ml) ; voir cet article

• Creal : arithmétique réelle exacte

• Bitv : une bibliothèque de vecteurs de bits (github | opam)

• Bitset : petits ensembles d'entiers codés par des vecteurs de bits (.mli | .ml) ;

• Arbres de Patricia : Ensembles et dictionnaires efficaces sur les entiers (ptset | ptmap) à partir d'un papier de Chris Okasaki
  Voir aussi les modules Hashcons, Hset et Hmap ci-dessous (pour utiliser les arbres de Patricia lorsque l'on fait du hash-consing)

• Trie : Dictionnaires sur des listes (.mli | .ml)

• Heaps : (tas = files de priorité)
  • structure impérative classique utilisant un tableau (.mli | .ml)
  • arbres de Braun (.mli | .ml)
  • tas gauches (leftist heaps) (.mli | .ml)

• Rbset : arbres rouges et noirs (.ps | .mli)
  Ce code a été certifié avec Coq; voir cette page

• Hashset : Ensembles codés par des tables de hachage (plus simple à utiliser et légèrement plus compact que l'utilisation du module Hashtbl) (.ps | .mli)

• Suffix_tree : Algorithme d'Ukkonen (.mli | .ml)

• Ropes : structure de corde (.mli | .ml)

  Un éditeur de texte vite-fait, mal-fait et incomplet utilisant les cordes : editor.ml (nécessite ocamlsdl, voir ci-dessous)

• Rbuffer : (.mli | .ml) Implantation du module Buffer à l'aide de cordes ; pour des cordes d'usage général, voir ci-dessus.

• Poly : Polynômes à coefficients dans un anneau quelconque (.mli | .ml)

• Bdd : Diagrammes de décision binaires (.mli)

Bibliothèques

• Combine, une bibliothèque de cominatoire (avec Remy El Sibaïe) (github | opam)

• Functory, une bibliothèque de calcul distribué, inspirée par MapReduce (avec Kalyan Krishnamani) (github)

• OCamlgraph, une bibliothèque de graphes pour OCaml (github | opam)

• Mlpost, une bibliothèque OCaml pour dessiner des figures (github | opam)

• cgi : une bibliothèque pour écrire des scripts CGI (.mli)

• ocamlsvga : interface pour de la bibliothèque Linux SVGAlib

• ocamlsdl : interface pour de la bibliothèque graphique SDL; inclus le support OpenGL, pour être utilisé par exemple avec lablGL
  
  Note : il existe un projet similaire plus avancé, OcamlSDL.sourceforge.net

• display : visualisation de la représentation interne des valeurs Caml (.ps | .mli)

• hashcons : tables de hash pour le hash consing (.ps | .mli | github). Cette technique est décrite dans ce papier.
  Hset / Hmap: Modules Ptset et Ptmap (voir ci-dessus) spécialisés sur les valeurs hash-consées (hset.mli | hmap.mli).

• prtree : pour imprimer des arbres à la manière de pstree (.ps | .mli)

• search : codes fonctorisés pour les recherches en profondeur, en largeur, et en approfondissement itératif (.ps | .mli)

Applications

• bibtex2html : convertisseur de BibTeX vers HTML

• ocamlweb : un outil de programmation litéraire pour OCaml (opam)

• ocamlwc : un programme pour compter les lignes de code et de documentation dans du source OCaml (.ps)

• yamlpp : un pré-processeur HTML très simple, inspiré par l'htmlpp de Nicolas Thiéry

Algorithmique

• Algorithme de Garsia-Wachs : suit la description faite dans The Art of Computer Prorgamming ; code OCaml décrit en détail dans cet article (.mli / .ml)

• Triangulation de Delaunay : implantation de l'algorithme de D. Knuth présenté dans Axioms and Hulls. Complexité : O(N log N) en temps (en moyenne) ; toujours O(N) en espace. S'applique à n'importe quel système CCC (voir Axioms and Hulls). Note : ce module fait partie d'OCamlgraph mais peut être utilisé indépendamment. (.mli)

• DLX: Implantation de l'algorithme de D. Knuth Dancing Links (.mli / .ml / .ps)

  Voir aussi la bibliothèque Combine.

• Knuth-Morris-Pratt : recherche d'une chaîne dans une autre (.mli / .ml / .ps)

• Pentaminos : calcul du nombre de solutions

• Solitaire : recherche de la solution (solitaire français) (.ps), en collaboration avec Xavier Urbain.

• anagram.ml : Anagrammes (.ps). Pour le tester, voici un dictionnaire anglais

• koda-ruskey.ml : Implantation de l'algorithme de Koda-Ruskey (.ps), inspiré d'une implantation par D. E. Knuth
  Ce code est détaillé dans cet article (en Français) et cet autre article (en Anglais, co-écrit avec François Pottier)

Jeux

• Un démineur à vocation pédagogique écrit en moins d'une heure : demineur.ml / download

Publications

• Type-Safe Modular Hash-Consing (avec Sylvain Conchon, ML workshop, 2006)
• A Persistent Union-Find Data Structure (avec Sylvain Conchon, ML workshop, 2007)
• Designing a Generic Graph Library using ML Functors (avec Sylvain Conchon, J. Signoles, Trends in Functional Programming, 2007)
• A Functional Implementation of the Garsia-Wachs Algorithm (ML workshop, 2008)

• Le petit guide du bouturage, ou comment réaliser des arbres mutables en OCaml (2013)
• Faire bonne figure avec Mlpost (avec R. Bardou, J. Kanig, S. Lescuyer, JFLA 2009)
• Polycopié de cours de Master Informatique (M1) : Initiation à la programmation fonctionnelle. Transparents : DVI (pour Active DVI) / PostScript

Divers

• Compilation : configure.in : un script de configuration autoconf pour les programmes OCaml, et une suggestion de Makefile.in

• Mon entrée au concours de programmation ICFP Programming Contest 2001 (en anglais)
• Mon entrée au concours de programmation ICFP Programming Contest 2003 (en anglais)
• Mon entrée au concours de programmation ICFP Programming Contest 2004 (en anglais)
• Mon entrée au concours de programmation ICFP Programming Contest 2006 (en anglais)

Hacker: One who programs enthusiastically (even obsessively) or who enjoys programming rather than just theorizing about programming.

Quelques applications écrites (par d'autres) en OCaml

• GeneWeb - logiciel de généalogie
• HeVeA - un traducteur LaTeX vers HTML

Quelques pointeurs

• OCaml home page
• OCaml Package Manager (OPAM)
• Le site de Daniel de Rauglaudre contient quelques beaux programmes OCaml

Détente

• The evolution of a Programmer