(This document is generated by GPT for me to find interesting stuffs to learn at)
This document is about learning routes, not just a catalogue of named structures.
The point is not merely to know that some data structure exists. The point is to learn a few strong design principles so that, when a new workload appears, you can design a representation that fits it.
A good way to think about a data structure is:
A functional data structure is often a carefully chosen compromise between these axes.
Before the specific routes, here is the general habit that turns reading into design skill.
For each data structure you meet, ask:
That is the habit that turns “I know some structures” into “I can invent one.”
This route teaches you how to build structures that are purely functional and persistent, while still being efficient.
The magic is that expensive work does not need to happen all at once. You can:
This is the route where one learns that in functional programming, time can be managed structurally.
A queue is the canonical example. A naive purely functional queue using one list for the front and one for the rear needs occasional reversal of the rear list. That reversal looks expensive, but if handled correctly, the average cost per operation is still small.
A persistent structure preserves old versions after updates.
s0 = empty
s1 = insert 3 s0
s2 = insert 5 s1All of s0, s1, and s2 are still usable.
The cost model is different from imperative mutation. Instead of overwriting memory, one usually shares unchanged substructure.
In an imperative structure, one can pay a rare large cost and average it across operations. In the persistent setting, this is more delicate: if the “same expensive debt” can be forced many times through sharing, a naive amortized argument can fail.
So one must be careful:
Instead of rebuilding everything at once, perform a little maintenance each time.
This is like rotating responsibilities among future operations.
A standard queue representation is:
data Queue a = Q [a] [a]
-- front rearReversedIf the front is empty, reverse the rear.
normalize :: Queue a -> Queue a
normalize (Q [] r) = Q (reverse r) []
normalize q = q
snoc :: a -> Queue a -> Queue a
snoc x (Q f r) = normalize (Q f (x:r))
uncons :: Queue a -> Maybe (a, Queue a)
uncons (Q [] []) = Nothing
uncons (Q (x:xs) r) = Just (x, normalize (Q xs r))
uncons (Q [] r) = uncons (normalize (Q [] r))The core idea is not the exact code. The core idea is:
That pattern appears everywhere.
When reading this route, do not just learn queues and deques. Learn these moves:
If you internalize this, you will start to see many structures as “a representation plus a maintenance schedule.”
Chris Okasaki, Purely Functional Data Structures
Chris Okasaki, “Simple and Efficient Purely Functional Queues and Deques”
Chris Okasaki, “The Role of Lazy Evaluation in Amortized Data Structures”
This is one of the most beautiful and reusable directions.
It is especially worth extra study because it trains the “invent your own representation” muscle.
This route teaches you that the structure of a sequence can come from the structure of a number representation.
This gives several kinds of magic:
The key insight is:
a sequence can be represented by a decomposition of its size.
Instead of saying “I have a list” or “I have a tree”, you say:
This is deeply reusable.
Suppose we store the sequence as a list of complete binary trees. Each tree has size a power of two. A digit says whether a tree of that size is present.
For example, if the length is 13, then
[ 13 = 8 + 4 + 1 ]
so the sequence can be represented by trees of sizes 8, 4, and 1.
This is like binary expansion, but now each digit carries actual data.
When you insert an element at the front, you create a size-1 tree. If there is already a size-1 tree, combine them into a size-2 tree. If that collides, combine again. This is just binary carrying.
So insertion becomes like incrementing a number.
To find the ith element, inspect the leading digits to determine which tree contains it, then descend into that tree.
Thus indexing becomes logarithmic because the representation decomposes size hierarchically.
Ordinary binary gives one style of structure. Skew binary changes the rules so that some one-end operations become worst-case constant time rather than merely amortized.
This is the real lesson:
performance comes partly from the algebra of the digits.
A classic simplified representation looks like this:
data Tree a
= Leaf a
| Node Int (Tree a) (Tree a)
-- Int caches size
data Digit a
= Zero
| One (Tree a)
type RAList a = [Digit a]A One t at position k means there is a tree of size 2^k.
We need a way to combine two equal-sized trees.
size :: Tree a -> Int
size (Leaf _) = 1
size (Node n _ _) = n
link :: Tree a -> Tree a -> Tree a
link t1 t2 = Node (size t1 + size t2) t1 t2Insertion at the front works like binary increment.
consTree :: Tree a -> RAList a -> RAList a
consTree t [] = [One t]
consTree t (Zero : ds) = One t : ds
consTree t (One t' : ds) = Zero : consTree (link t t') ds
cons :: a -> RAList a -> RAList a
cons x = consTree (Leaf x)The structure is almost shouting its meaning:
Leaf x is the new low-order digit,A simplified lookup sketch:
lookupTree :: Int -> Tree a -> a
lookupTree 0 (Leaf x) = x
lookupTree i (Node _ l r)
| i < size l = lookupTree i l
| otherwise = lookupTree (i - size l) r
lookupTree _ _ = error "bad index"
lookupRA :: Int -> RAList a -> a
lookupRA _ [] = error "bad index"
lookupRA i (Zero:ds) = lookupRA i ds
lookupRA i (One t:ds)
| i < size t = lookupTree i t
| otherwise = lookupRA (i - size t) dsThe exact details vary across presentations, but the principle is stable.
Because it teaches you to derive a data structure from a representation theorem:
This suggests many design questions:
Suddenly you are designing, not just memorizing.
A random-access list can be seen as a forest of complete trees with digit constraints.
That is already a pattern:
This separates concerns nicely.
It is often useful to say:
the performance is determined by the digit algebra, while the element operations are determined by the tree annotations.
That sentence is worth remembering.
updateRA :: Int -> (a -> a) -> RAList a -> RAList a.Int size caches with a type-indexed size if you want stronger invariants.Pay special attention to these questions:
That is the core magic of this route.
Chris Okasaki, Purely Functional Data Structures
Chris Okasaki, “Purely Functional Random-Access Lists”
Ralf Hinze, “Bootstrapping One-Sided Flexible Arrays”
lookup and update.This route is especially worth slow study because it trains the habit of deriving a structure from a representation of size rather than from an already-familiar container shape.
This is the other route especially worth extra study.
It is a very important abstraction because it shows how an algebraic summary can drive search, split, and indexing.
This route gives you the ability to turn a generic tree into many specialized data structures by changing the annotation algebra.
The magic is:
This is one of the clearest examples of a data structure being built from an algebra of summaries.
A finger tree stores at each node a summary value, often called a measure. The measure lives in a monoid.
So you choose:
class Monoid v => Measured a v where
measure :: a -> vThen internal nodes cache the monoidal combination of their subtree summaries.
If the monoid operation is written (<>), then the summary of a concatenation is the concatenation of summaries:
[ (x y) = (x) (y). ]
This means you can search by reading summaries rather than inspecting every element.
Suppose your measure is size:
newtype Size = Size Int
deriving (Eq, Ord, Show)
instance Semigroup Size where
Size a <> Size b = Size (a + b)
instance Monoid Size where
mempty = Size 0Then you can split by position.
Suppose instead your measure is minimum priority:
newtype MinP = MinP (Maybe Int)Then the same structure can guide access by priority information.
Suppose your measure stores both size and max endpoint. Then you can support interval-like or segment-like queries.
The representation stays mostly the same. The algebra changes.
This is why finger trees are so conceptually rich.
A simplified finger tree shape looks like:
data Digit a = One a | Two a a | Three a a a | Four a a a a
data Node v a
= Node2 v a a
| Node3 v a a a
data FingerTree v a
= Empty
| Single a
| Deep v (Digit a) (FingerTree v (Node v a)) (Digit a)Ignore the exact constructors at first. What matters is the pattern:
The digits are the “fingers”: they give quick access near the ends. The recursive middle preserves structure for deeper operations.
A finger tree is not just “a sequence tree with nice bounds.” It is a method for combining three ideas:
That combination is what makes it so reusable.
Let us sketch the flavor rather than a full correct implementation.
newtype Size = Size { getSize :: Int }
deriving (Eq, Ord, Show)
instance Semigroup Size where
Size a <> Size b = Size (a + b)
instance Monoid Size where
mempty = Size 0
class Monoid v => Measured a v where
measure :: a -> v
instance Measured a Size where
measure _ = Size 1Now the summary of a subtree tells us how many elements are under it. An index-based split can be driven by prefix sizes.
Conceptually, if you want to split at position k, you descend while maintaining the measure of everything to the left. At each step, you ask whether the left summary already crosses k.
Pseudo-Haskell:
splitAtFT :: Int -> FingerTree Size a -> (FingerTree Size a, FingerTree Size a)
splitAtFT k t = split (
(Size n) -> n > k
) tThe real implementation is more subtle, but the conceptual content is this:
That is an extremely general pattern.
Use Size to obtain sequence-like indexing and splitting.
Suppose elements have priorities. Store at each node the minimum priority in the subtree. Then you can quickly know the global minimum or guide certain searches.
newtype MinP = MinP { getMinP :: Maybe Int }
instance Semigroup MinP where
MinP Nothing <> y = y
x <> MinP Nothing = x
MinP (Just a) <> MinP (Just b) = MinP (Just (min a b))
instance Monoid MinP where
mempty = MinP NothingA common trick is to use a product monoid.
data Summary = Summary
{ sSize :: Size
, sMin :: MinP
}
instance Semigroup Summary where
Summary a1 b1 <> Summary a2 b2 = Summary (a1 <> a2) (b1 <> b2)
instance Monoid Summary where
mempty = Summary mempty memptyNow one structure supports multiple kinds of reasoning.
This is another general design lesson:
if one cached field helps one query and another cached field helps another query, they can often be combined by a product monoid.
Because it teaches a generic recipe:
That recipe appears far beyond finger trees themselves.
You can use the same idea in:
When faced with a new problem, ask:
If the answer is yes, there is a good chance that a measured tree will work.
Suppose you are designing a text buffer. You might want:
Then a measure might store:
Now the cursor movement operations become guided by prefix summaries.
This is an example of turning “editor operations” into “algebra over summaries.”
Focus on these ideas:
This is perhaps the most algebraically elegant route in the subject.
Ralf Hinze and Ross Paterson, “Finger Trees: A Simple General-Purpose Data Structure”
Practical Data.Sequence-style implementations
Data.Sequence.(size, lineCount), or (size, accumulatedCost).This route is especially important because it teaches how to turn an application query into an algebra of cached summaries.
This route teaches you how to obtain stronger guarantees by layering structures inside structures.
The magic is:
A functional priority queue is a standard place to see this.
Use a data structure recursively inside itself, or use one data structure to manage the deferred work of another.
Take an amortized structure and schedule its expensive steps so that no single operation becomes too costly.
Strong worst-case bounds typically require tighter invariants than amortized structures do.
Suppose you have a heap-like structure where merging is easy but rebuilding after repeated inserts is not. One idea is:
That sketch is vague as implementation, but very concrete as a design principle.
Chris Okasaki, Purely Functional Data Structures
Gerth Stølting Brodal and Chris Okasaki, “Optimal Purely Functional Priority Queues”
This route teaches you how to build structures that behave well in practical workloads, especially for sequences supporting:
The magic is that the tree need not be perfectly balanced everywhere. Controlled imbalance can buy better practical performance and richer operations.
Instead of enforcing exact balance, allow local variation within safe bounds.
To make relaxed balance workable, cache more structural information.
The tree is repaired when a local threshold is violated, not on every operation.
A persistent vector based on a wide branching tree often gives fast lookup and update, but naive concatenation is poor. Relaxed variants allow subtree sizes to vary within bounds so that concatenation and split become feasible without destroying performance.
Phil Bagwell and Tiark Rompf, “RRB-Trees: Efficient Immutable Vectors”
Nicolas Stucki et al., “RRB Vector: A Practical General Purpose Immutable Sequence”
This is an important route if you care about structures that survive real application workloads.
This route teaches you maturity.
The magic is that you can preserve a clean functional API and functional reasoning style even when the implementation uses mutation internally for efficiency.
This is useful when a purely persistent tree formulation is possible but awkward or slow.
The user-facing semantics may be immutable and persistent even if the implementation uses arrays, refs, or path compression internally.
Some structures are fully persistent, some only semipersistent. You must understand exactly what past versions are allowed to do.
The real question is not “is there mutation?” but “what laws does the interface satisfy?”
Union-find is easy imperatively because path compression mutates parents. Persistent variants force you to ask:
This route is useful if you want to build efficient real-world structures without becoming dogmatic.
Sylvain Conchon and Jean-Christophe Filliâtre, “A Persistent Union-Find Data Structure”
Background material on persistent arrays / rerooting techniques.
ST-based internal representation with a pure outward API.This route gives you the ability to reason about your structures as mathematical objects rather than piles of code.
The magic is:
For example:
Sometimes a GADT or indexed type can encode shape invariants. Sometimes this is too heavy. The art is deciding where the proof burden pays off.
Trying to prove correctness often reveals the right abstraction and the right decomposition of operations.
A node that caches size can be validated by a smart constructor.
data Tree a
= Leaf a
| Node Int (Tree a) (Tree a)
mkNode :: Tree a -> Tree a -> Tree a
mkNode l r = Node (treeSize l + treeSize r) l r
trueSize :: Tree a -> Int
trueSize (Leaf _) = 1
trueSize (Node _ l r) = trueSize l + trueSize r
treeSize :: Tree a -> Int
treeSize (Leaf _) = 1
treeSize (Node n _ _) = n
valid :: Tree a -> Bool
valid (Leaf _) = True
valid (Node n l r) = n == treeSize l + treeSize r && valid l && valid rThis is a tiny example, but it teaches a habit: node metadata should have a precise contract.
Tobias Nipkow (ed.), Functional Data Structures and Algorithms: A Proof Assistant Approach
Formal developments of specific structures such as finger trees, heaps, or balanced trees.
valid :: T a -> Bool invariants.valid.If your goal is to invent data structures when needed, rather than merely consume existing ones, here is a good order:
Persistence + amortization
Numeral systems as representation
Measured trees / finger trees
Bootstrapping / deamortization
Relaxed balance
Encapsulated mutation
Proof-oriented design
For your goals, the two most fertile routes are:
Because it teaches representation design from first principles.
It encourages questions like:
This route helps you invent structures.
Because it teaches how algebraic summaries can drive an entire API.
It encourages questions like:
This route helps you turn application needs into algebra.
These two routes complement each other beautifully:
One is about how the shape is encoded. The other is about how information flows through the shape.
Together they are an extremely strong basis for creating custom functional data structures.
If you want these ideas to become native, build small structures yourself.
Implement:
empty :: RAList a
cons :: a -> RAList a -> RAList a
headRA :: RAList a -> Maybe a
tailRA :: RAList a -> Maybe (RAList a)
lookupRA :: Int -> RAList a -> Maybe a
updateRA :: Int -> a -> RAList a -> Maybe (RAList a)Then ask:
Build a simplified measured tree supporting:
pushL :: a -> T a -> T a
pushR :: a -> T a -> T a
splitAt :: Int -> T a -> (T a, T a)
index :: Int -> T a -> Maybe awith a size measure.
Then generalize the measure to:
data Summary = Summary
{ totalSize :: Sum Int
, totalCost :: Sum Int
}or some application-specific summary.
Then ask:
Define a sequence of text chunks whose measure stores:
Implement splitting by character offset and by line number.
This project makes the finger-tree-style route feel concrete.
A large portion of advanced functional data structure design comes from a handful of moves:
When you read papers or implementations, try to classify them by these moves.
That makes the field much smaller and much more reusable.
Instead of seeing a zoo of clever objects, you start to see a small family of principles appearing in different disguises.
When a new workload appears, ask:
If you can answer those clearly, you are already doing real data structure design.
A compact list of the main titles integrated into the route sections above:
For each paper or chapter, a useful note template is:
This keeps the literature organized as a family of reusable design moves rather than a pile of isolated clever tricks.