Summary

We've covered a few data structures that you don't typically see in an introductory data structures course—streams, red-black trees, promises, and monads—as well as mutable data structures.

There are many other exciting data structures out there in the world for you to learn. One great source is Chris Okasaki's book, cited below. It goes much deeper into how to implement various data structures from the imperative world, but in a functional language.

Terms and concepts

  • address
  • alias
  • array
  • assignment
  • associative
  • asynchronous
  • bind
  • blocking
  • caching
  • callback
  • channel
  • computations
  • concurrent
  • concurrent composition
  • cooperative
  • cycle
  • delayed evaluation
  • dereference
  • determinstic
  • eager
  • effects
  • force
  • immutable
  • index
  • infinite data structure
  • interleaving
  • latency hiding
  • lazy
  • left identity
  • loop
  • Lwt monad
  • maybe monad
  • memoization
  • memory safety
  • monads
  • monads laws
  • mutable
  • mutable field
  • non-blocking
  • nondeterministic
  • parallelism
  • pending
  • persistent
  • physical equality
  • pointer
  • preemptive
  • promises
  • pure
  • race conditions
  • recursive values
  • ref
  • ref cell
  • reference
  • rejected
  • resolution loop
  • resolved
  • resolver
  • right identity
  • sequencing
  • sequential
  • sequential composition
  • standard input
  • standard output
  • stream
  • strict
  • structural equality
  • synchronous
  • threads
  • thunk
  • writer monad

Further reading

  • Introduction to Objective Caml, chapters 7 and 8.

  • OCaml from the Very Beginning, chapter 13.

  • More OCaml: Algorithms, Methods, and Diversions, chapters 2 and 11, by John Whitington. This book is a sequel to OCaml from the Very Beginning.

  • Real World OCaml, chapters 8, 13, and 18.

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

results matching ""

    No results matching ""