View on GitHub

OCamlverse

Documenting everything about OCaml

Edit

Data Structures and Algorithms

Standard Library Data Structures

A major part of a standard library’s role is providing basic data structures and algorithms. All the standard libraries provide these:

  • The standard library contains basic data structures: List, Array, Immutable Map, Hashtable, Mutable Queue, Mutable Stack.
  • Base contains many additional data structures.
  • Containers is a data structure-oriented extension of the standard library.
  • Batteries Included is an older extension of the standard library with many data structures.
  • Vocal: A data structure library for OCaml, verified in Coq. See here.

Specific Data Structure Libraries

  • Ropes: Persistent, functional views on top of strings.
  • Patricia Trees: implementation of high performance functional map.
  • Persistent Vectors: Data structures that behave similar to vectors but using immutable trees (of arrays).
  • baby: Immutable sets and maps that perform better than the standard library’s.
  • OCamlGraph is a library for graphs and graph algorithms.
  • bimap: Bi-directional map, from key to value and value-to-key.
  • ods is an algorithm/data structure library, though it isn’t as fully-featured as the standard libraries.
  • Discrete Interval Encoding Trees: Useful for storing interval sets and testing membership efficiently.
  • Interval: An interval arithmetic library.
  • bitv: A bit-vector library.
  • psq: Functional priority search queues library.
  • bloomf: Fast Bloom filter library.
  • skip-list: Pure skip lists. Seems incomplete.
  • art: Adaptive Radix Trees: speed of hashtables but based on an order.
  • bitmasks: Use bitmasks as sets.

Heterogeneous Maps

  • Containers (a standard library) contains the CCHet data structure, which uses generative first-class modules on the inside to store values of different types.
  • hmap: Hmap is another variation of a heterogeneous map.
  • gmap: Allows for the creation of a heterogeneous map wrapped in a user-provided GADT. As opposed to the above solution, the full closed universe of possible types to be stored must be known by the user.