Chris Okasaki has a very good chapter in his book Purely Functional Data Structures that discusses “Numerical Representations”: essentially, take some representation of a number and convert it into a data structure. To give a flavor, here are the sections of that chapter:
- Positional Number Systems
- Binary Numbers (Binary Random-Access Lists, Zeroless Representations, Lazy Representations, Segmented Representations)
- Skew Binary Numbers (Skew Binary Random Access Lists, Skew Binomial Heaps)
- Trinary and Quaternary Numbers
Some of the best tricks, distilled:
- Distinguish between dense and sparse representations of numbers (usually you see this in matrices or graphs, but it’s applicable to numbers too!)
- Redundant number systems (systems that have more than one representation of a number) are useful.
- If you arrange the first digit to be non-zero or use a zeroless representation, retrieving the head of the data structure can be efficient.
- Avoid cascading borrows (from taking the tail of the list) and carries (from consing onto the list) by segmenting the data structure
Here is also the reference list for that chapter:
- Guibas, McCreight, Plass and Roberts: A new representation for linear lists.
- Myers: An applicative random-access stack
- Carlsson, Munro, Poblete: An implicit binomial queue with constant insertion time.
- Kaplan, Tarjan: Purely functional lists with catenation via recursive slow-down.