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.
- Persistent Vectors: Data structures that behave similar to vectors but using immutable trees (of arrays).
- 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.