modules Ocaml mise en œuvre

Question

bibliothèque standard de Ocaml contient différents modules: List, Map, Nativeint, etc. Je sais que des interfaces pour ces modules sont fournis (par exemple pour le List module), mais je suis intéressé par les algorithmes et leur mise en œuvre utilisés dans les modules ' les fonctions.

Où puis-je trouver cela?

Answer 1

Vous pouvez trouver les définitions dans le code source OCaml. Par exemple, l'implémentation des fonctions Map est dans stdlib/map.ml dans la distribution source OCaml.

Answer 2

Ils devraient déjà être installés sur votre système. Très probablement (en supposant un système Unix) ils sont situés dans/usr/lib/ocaml ou/usr/local/lib/ocaml. Il suffit d'ouvrir l'un des fichiers .ml.

Answer 3

• Sur votre système: /usr/lib/ocaml/list.ml et d'autres fichiers .ml
• Sur le web: https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml et d'autres .ml fichiers dans https://github.com/ocaml/ocaml/tree/trunk/stdlib

---

La mise en œuvre Liste est intéressante à étudier. Par exemple, la fonction map pourrait être mis en œuvre comme ceci:

let rec map f = function 
    | [] -> [] 
    | a::l -> f a :: map f l 

, mais est plutôt mis en œuvre comme ceci:

let rec map f = function 
    | [] -> [] 
    | a::l -> let r = f a in r :: map f l 

Quelle est la différence? Exécuter ceci:

List.map print_int [1;2;3] ;; 
map print_int [1;2;3] ;; 

Le premier imprime 123, mais le second imprime 321! Depuis l'évaluation de f a pourrait produire des effets secondaires, il est important de forcer l'ordre correct. C'est ce que fait l'implémentation officielle de la carte. En effet, le evaluation order of arguments is unspecified in OCaml même si toutes les implémentations suivent le même ordre.

Voir aussi le Optimizing List.map post on the Jane Street blog pour des considérations sur les performances (List.map est efficace sur les petites listes).