8.8. Summary

This chapter has taken a deep dive into some advanced data structures, analysis techniques, and programming patterns. Our goal has been to write correct, efficient, beautiful code. Did we succeed? You can be the judge.

8.8.1. Terms and Concepts

  • amortized analysis

  • association list

  • associative

  • associative array

  • asymptotic bound

  • asynchronous

  • banker’s method

  • big oh

  • bind

  • binding

  • blocking

  • brute force

  • bucket

  • caching

  • callback

  • chaining

  • channel

  • collision

  • complexity

  • computations

  • concurrent

  • concurrent composition

  • cooperative

  • credits

  • cycle

  • delayed evaluation

  • deterministic

  • dictionary

  • diffusion

  • direct address table

  • eager

  • effects

  • efficiency

  • execution steps

  • exponential time

  • force

  • hash function

  • infinite data structure

  • injective

  • input size

  • interleaving

  • key

  • latency hiding

  • lazy

  • left identity

  • load factor

  • Lwt monad

  • map

  • maybe monad

  • memoization

  • monads

  • monads laws

  • mutable map

  • non-blocking

  • nondeterministic

  • parallelism

  • pending

  • persistent

  • physicist’s method

  • polynomial time

  • potential energy

  • preemptive

  • probing

  • promises

  • race conditions

  • recursive values

  • red-black map

  • rejected

  • resizing

  • resolution loop

  • resolved

  • resolver

  • right identity

  • sequential

  • sequential composition

  • serialization

  • set

  • standard input

  • standard output

  • stream

  • strict

  • synchronous

  • threads

  • thunk

  • worst case performance

  • writer monad

8.8.2. Further Reading

  • More OCaml: Algorithms, Methods, and Diversions, chapters 2 and 11, by John Whitington.

  • Introduction to Objective Caml, chapter 8, section 4

  • Real World OCaml, chapters 13 and 18

  • Purely Functional Data Structures, by Chris Okasaki. Cambridge University Press, 1999.