9.7. 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.

9.7.1. Terms and Concepts

• amortized analysis

• association list

• associative

• associative array

• asymptotic bound

• asynchronous

• banker’s method

• big oh

• binding

• brute force

• bucket

• caching

• chaining

• collision

• complexity

• credits

• cycle

• delayed evaluation

• dictionary

• diffusion

• direct address table

• eager

• efficiency

• execution steps

• exponential time

• force

• hash function

• infinite data structure

• injective

• input size

• key

• lazy

• load factor

• map

• memoization

• mutable map

• persistent

• physicist’s method

• polynomial time

• potential energy

• probing

• recursive values

• red-black map

• resizing

• serialization

• set

• stream

• thunk

• worst case performance

9.7.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.