ocaml-data-structures

ocaml-data-structures copied to clipboard

ocaml-data-structures

I'm learning OCaml and re-learning some data structures.

Index

• Stack (tests) - A simple stack implementation that pops, pushes, and peeks.
• Trie (tests) - An implementation of a trie which can map strings to values in a performant way.
• Setoid (tests) - Contract for setoids, which have an equivalence operation that allows these items to be placed into sets. The unit tests include an implementation to "uniquify" a list of "Person" setoids.
• Functor (tests) - Haskell-type functors which implement an fmap function. Unit tests include implementations for Maybe and Either.
• Algebra (tests) - Mechanism for representing algebraic instructions, with the ability to compute their derivatives.
• Queue (tests) - An immutable queue, built from two Stacks.
• Finite State Machine (tests) - Contracts for implementing a finite state machine (see unit tests for TrafficLight and Turnstile implementations). Built during @DavidKPiano's excellent ReactRally talk!
• Wire (tests) - A mechanism which allows you to write procedures and populate their arguments later (, based on a really interesting Advent of Code problem.
• Binary Search Tree (tests) - A binary search tree parameterized over a general Ord type (any struct with a compare: t -> t -> int operation).
• Red-Black Tree (tests) - A Red-black tree implementation, which is a more specific type of binary search tree that self-balances on insert.
• Levenshtein Distance (tests) - A Levenshtein distance calculator, or the number of insertions, deletions, modification required to get from one sequence to another.
• Binary Heap (tests) - A binary heap data structure parameterized with a comparable type to define min- and max- heaps.
• Huffman Coding (tests) - Huffman coding implementation which losslessly compresses strings and is built using Binary Heap.

Development

# Build all the things
make

# Run the tests
make test