Purely Functional Data Structures, by Chris Okasaki 1.
However, there is one aspect of functional programming that no amount of cleverness on the part of the compiler writer is likely to mitigate - the use of inferior or inappropriate data structures.
Why a language with strict evaluation?
Strict languages can describe worst-case data structures, but not amortized ones, and lazy languages can describe amortized data structures, but not worst-case ones.
To be able to describe both kinds of data structures, we need a programming language that supports both evaluation orders.
Robert Harper 2,
[..] content ourselves with the observation that laziness is a special case of eagerness.
- Abstract data type: A type and a collection of functions on that type. Also, simply an abstraction.
- Concrete realization: Also implementation. Implementation need not be actualized as code - a concrete design is sufficient.
- Instance of data type: Such as a particular list or tree. Refer to such an instance in general as object or a version.
- Unique identity, invariant under updates: Refer to this identity as a persistent identity. When we speak of different versions of the same data structure, we mean that the different versions share a common persistent identity.
| Concept | SML |
|---|---|
| Abstractions | Signatures in Standard ML |
| Implementations | Structures or functors |
| Objects/versions | Values |
- Chapter 1: Introduction (you are here)
- Chapter 2: Persistence
- Chapter 3: Some Familiar Data Structures in a Functional Setting
- Chapter 4: Lazy Evaluation
Files in lib/ define shared definitions.
Files in driver/ are type-checked, compiled, linked and executed by Github actions.