-- Builtin syntax, but would be defined like that
data [a] -- [a] = »List of items of type `a`«
= [] -- Pronounced »Nil«: empty list
| a : List a -- Pronounced »Cons«: Prepends an element to a ListSyntactical sugar:
[1,2,3] ≡ 1 : (2 : (3 : []))
[1..10] ≡ 1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : []
Pattern Matching (list deconstruction):
case list of
[] -> ...
x : xs -> ... x : [] x : y : z : []
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ x ├───[] │ x ├─│ y ├─│ z ├───[]
└───┘ └───┘ └───┘ └───┘
Each Cons cell contains an element, and a pointer to the next element.
... if the list is evaluated at all, because:
Haskell is lazy:
- Expressions are only evaluated when the result is needed
- ... and only as far as needed!
- Results are memoized, i.e. only computed once.
- To be precise: Evaluation is driven by Pattern Matching.
This allows for infinite constructs like repeat:
replicate 0 x = []
replicate n x = x : replicate (n - 1) xThe function creates a so-called »Thunk«, a reference to a computation to be executed:
╭───────────────╮
│ replicate 2 x │
╰───────────────╯
After matching on the first Cons cell, the memory is updated (memoization):
┌───┐ ╭───────────────╮
│ x ├─│ replicate 1 x │
└───┘ ╰───────────────╯
... and the second Cons cell:
┌───┐ ┌───┐ ╭───────────────╮
│ x ├─│ x ├─│ replicate 0 x │
└───┘ └───┘ ╰───────────────╯
The next pattern-match finds the final Nil cell:
┌───┐ ┌───┐
│ x ├─│ x ├───[]
└───┘ └───┘
Lists are quite inefficient when compiled naively.
But laziness allows Stream Fusion, which basically allows the compiler to rearrange and group list operations, so that often a list is never even written to memory, but produces and transform elements as they are consumed.
fac :: Int -> Int
fac n = product [1..n]Q: How many memory allocations does fac 100 perform?
A: None at all: The numbers are produced incrementally, as they are consumed by
product. No memory allocation required.
Assume the Java equivalent of the head function:
// public static <A> A head(List<A> list) { … }
head(asList(f(100), f(200), f(300)))In what order are the calls evaluated?
- Evaluate
f(100),f(200),f(300) - Pass the result to
asList(•,•,•), evaluate - Pass the result to
head(•), evaluate
head :: [a] -> a
head (a : as) = a
head [f 100, f 200, f 300]In what order are the calls evaluated?
- Enter head function, pass
[f 100, f 200, f 300]as thunk - Encounter pattern
(a : as) - Evaluate thunk to Weak Head Normal Form (WHNF:
• : •) - Return
f 100as thunk
We didn't even once call f!
(Now think what would happen for f n = f (n-1) + f(n-2) ...)
For algorithms with varying cost per step, worst-case bounds can be too pessimistic, and the average case may not be an upper bound.
Goal: Find a better upper bound by balancing between different cost centers.
An Array List of fixed size n has O(1) insert.
7
↓
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
But if the list is too small, the n+1st element takes O(n) to insert,
because the entire list is copied to double the array size.
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │
└───┴───┴───┴───┴───┴───┴───┴───┘ 9
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ │ │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
- Worst-case time for insert:
O(n) - Amortized time for insert:
O(1)!
- Place credits at each location in the data structure.
- Cheap operations may add credits (making them slightly more expensive).
- Expensive operations may consume credits (making them possibly cheaper).
- Credits can only be consumed after they have been placed, not in advance.
The goal is to find an accounting scheme where each expensive operation is already paid for in credits.
- Define a potential
Φbased on a property of each location. - The total potential is an upper bound for the accumulated savings, it must never be negative.
- The amortized cost of an operation is the actual cost plus the change in
potential:
- Expensive operations can be made cheaper by drawing from the potential,
- cheap operations can add to the potential.
The goal is to find a good definition for the potential, so that it will never become negative, and so that expensive operations may draw from it.
Both methods are equivalent:
- Proofs using the Physicist's method are easier to write, because we can ignore the locations of the credits.
- Proofs using the Banker's method are easier to understand, because we known when and where the credits are placed and consumed.
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1*│ 2*│ 3 │ 4 │ 5*│ 6*│ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1*│ 2*│ 3*│ 4 │ 5*│ 6*│ 7*│ │
└───┴───┴───┴───┴───┴───┴───┴───┘
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1*│ 2*│ 3*│ 4*│ 5*│ 6*│ 7*│ 8*│
└───┴───┴───┴───┴───┴───┴───┴───┘ 9
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ │ │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 1*│ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9*│ │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Account three credits for inserting element m into a list of length N:
- One paid directly for actually storing the element
- One saved for copying it to the next larger array
- One saved for copying element
m - 2^(N-1)to the next larger array
When reaching the size limit, we have exactly one credit per cell to be copied. In other words, the resizing operation has already been paid for!
With a constant three credits per insert operation, we have constant-time insert.
data Queue a = Queue [a] [a]
check :: Queue a -> Queue a
check (Queue write []) = Queue [] (reverse write)
check queue = queue
empty :: Queue a
empty = Queue [] []
insert :: a -> Queue a -> Queue a
insert a (Queue write read) = check (Queue (a : write) read)
view :: Queue a -> (a, Queue a)
view (Queue write (a : read')) = (a, check (Queue write read'))Inserting an element always takes O(1), but reversing the front end of the
queue takes O(n)!
=> The worst-case complexity for view is O(n).
Can we do better?
Use the Banker's method:
┌───┐
insert 1: [] │ 1 ├───[]
└───┘
┌───┐ ┌───┐
insert 2: │ 2*├───[] │ 1 ├───[]
└───┘ └───┘
┌───┐ ┌───┐ ┌───┐
insert 3: │ 3*├─│ 2*├───[] │ 1 ├───[]
└───┘ └───┘ └───┘
┌───┐ ┌───┐
view: [] │ 2 ├─│ 3 ├───[]
└───┘ └───┘
┌───┐ ┌───┐ ┌───┐
insert 4: │ 4*├───[] │ 2 ├─│ 3 ├───[]
└───┘ └───┘ └───┘
┌───┐ ┌───┐
view: │ 4*├───[] │ 3 ├───[]
└───┘ └───┘
- On
insert, account one credit to each inserted item, to a total cost of 2. viewwithout reversing does not consume any credits, so the total cost is 1.viewwith reversing costsn+1steps, consumesncredits, so the net total cost is 1.
=> Batched Queue has O(1) amortized view and insert.
Does it really?
Immutable data structures are persistent, they can be reused. This breaks our accounting balance:
peek :: Queue a -> a
peek q = case view q of (a, _) -> a
enqueueHead queue = insert (peek queue) queueIn order to view the first element, peek potentially reverses the list,
spending all the saved credits, but immediately throws away the updated queue.
Then enqueueHead continues with the old queue and inserts the result.
If anyone views the result of enqueueHead, the queue will be reversed
again - but the credits have already been spent!
Idea: Use lazy evaluation, in particular memoization, to guarantee credits are only spent once.
Lazy amortization using the Banker's method is a layaway plan:
- Each time a thunk is created, we assign it a number of credits proportional to the time it takes to evaluate it.
- We commit to save credits on each subsequent operation to pay for the evaluation.
- Goal is to prove that in each possible future, there are enough saved credits to pay for the thunk when it is evaluated.
data Queue a = Queue
{ lenWrite :: !Int
, write :: [a]
, lenRead :: !Int
, read :: [a] }
check :: Queue a -> Queue a
check queue@(Queue {..})
| lenWrite > lenRead = Queue 0 [] (lenRead + lenWrite) (read ++ reverse write))
| otherwise = queue
empty :: Queue a
empty = Queue 0 [] 0 []
insert :: a -> Queue a -> Queue a
insert a (Queue {..}) = check (Queue (lenWrite + 1) (a : write) lenRead read)
view :: Queue a -> (a, Queue a)
view (Queue {..}) = case read of
[] -> error "Empty queue"
a : read' -> (a, check (Queue lenWrite write (lenRead - 1) read')) ┌───┐
insert 1: [] │ 1 ├───[]
└───┘
┌───┐ ┌───┐
insert 2: │ 2 ├───[] │ 1 ├───[]
└───┘ └───┘
┌───┐ ╭───────────────────╮
insert 3: [] │ 1 ├─│ ** reverse [3, 2] │
└───┘ ╰───────────────────╯
╭──────────────────╮
view: [] │ * reverse [3, 2] │
╰──────────────────╯
┌───┐ ╭──────────────────╮
insert 4: │ 4 ├───[] │ * reverse [3, 2] │
└───┘ ╰──────────────────╯
┌───┐ ┌───┐
view: │ 4 ├───[] │ 3 ├───[]
└───┘ └───┘
- Trivial
inserttakes one credit insertwithreversetakes one credit, and creates a thunk withlenWritecredits
=> insert runs in O(1)
viewcosts one credit, and we save one credit to pay for the next thunk.- Condition for rotating the queue:
lenWrite > lenRead. => When reaching the thunk of areverseoperation, we have saved at leastlenReadcredits to pay for the thunk.
=> view runs in amortized O(1)
The Banker's Queue is slightly slower than the Batched Queue because of the additional book-keeping. Hence, in reality the Batched Queue is preferred where possible.
Example: Control.Concurrent.STM.TQueue from stm uses a Batched Queue, since
the queue is not used persistently, but ephemerally.
Used in: Data.Sequence
FingerTree a • 1..8 items
┌─┬─┬─┬───┼───┬─┬─┐
a b c d │ X Y Z
│
FingerTree (Node a) │ 2..24 items
┌───────┬───────┬─────┼─────┬──────┐
┌─┼─┐ ┌─┼─┐ ┌─┼─┐ │ ┌─┼─┐ ┌┴┐
e f g h i j k l m │ S T U V W
│
FingerTree (Node (Node a)) │ 4..72 items
┌───────────────┬───────┼─────────┐
┌──────┼──────┐ ┌──┴──┐ │ ┌───┴───┐
┌─┼─┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ │ ┌─┼─┐ ┌─┼─┐
n o p q r s t u v w x │ M N O P Q R
│
FingerTree (Node (Node (Node a))) │ 8..216 items
┌────────────┼────────────┐
┌──┴──┐ ┌───┴──┐ ┌──┴───┐
┌┴┐ ┌┴┐ ┌┴┐ ┌─┼─┐ ┌┴┐ ┌─┼─┐
y z A B C D E F G H I J K L
data FingerTree a
= Empty
| Single a
| Deep !Int !(Digit a) (FingerTree (Node a)) !(Digit a)
data Digit a = One a | Two a a | Three a a a | Four a a a a
data Node a = Node2 a a | Node3 a a a
class Sized a where
size :: Int
instance Sized a => Sized (FingerTree a)
instance Sized a => Sized (Digit a)
instance Sized a => Sized (Node a)(<|) -- `cons`
:: Sized a => a -> FingerTree a -> FingerTree a
(|>) -- `snoc` (`cons` backwards)
:: Sized a => FingerTree a -> a -> FingerTree a
a <| Single b = Deep (One a) Empty (One b)
a <| Deep s l t r = case l of
One b -> Deep s' (Two a b) t r
Two b c -> Deep s' (Three a b c) t r
Three b c d -> Deep s' (Four a b c d) t r
Four b c d e -> t `seq` -- Push a node down the spine
Deep s' (Two a b) (Node3 c d e <| t) r
where s' = s + size a1 <| 2 <| 3 <| 4 <| 5 <| 6 <| 7 <| 8 <| 9 <| Empty
1 <| 2 <| 3 <| 4 <| 5 <| 6 <| 7 <| 8 <| Single 9
•
|
9
1 <| 2 <| 3 <| 4 <| 5 <| 6 <| 7 <| Deep (One 8) Empty (One 9)
•
┌───┴───┐
8 9
Single is split into a Deep tree with One on each side and Empty spine.
1 <| 2 <| 3 <| 4 <| 5 <| 6 <| Deep (Two 7 8) Empty (One 9)
•
┌─┬───┴───┐
7 8 9
1 <| 2 <| 3 <| 4 <| 5 <| Deep (Three 6 7 8) Empty (One 9)
•
┌─┬─┬───┴───┐
6 7 8 9
1 <| 2 <| 3 <| 4 <| Deep (Four 5 6 7 8) Empty (One 9)
•
┌─┬─┬─┬───┴───┐
5 6 7 8 9
Elements are inserted into the left Digit until it reaches Four.
1 <| 2 <| 3 <| Deep (Two 4 5) (Single (Node3 6 7 8)) (One 9)
•
┌─┬───┼───┐
4 5 │ 9
┌─┼─┐
6 7 8
When the left Digit is full, three elements are pushed down the spine as a
Single Node3, leaving Two on the left Digit.
1 <| 2 <| Deep (Three 3 4 5) (Single (Node3 6 7 8)) (One 9)
•
┌─┬─┬───┼───┐
3 4 5 │ 9
┌─┼─┐
6 7 8
Now we can insert two more elements into the left Digit.
1 <| Deep (Four 2 3 4 5) (Single (Node3 6 7 8)) (One 9)
•
┌─┬─┬─┬───┼───┐
2 3 4 5 │ 9
┌─┼─┐
6 7 8
Deep (Two 1 2) (Deep (One (Node3 3 4 5)) Empty (One (Node3 6 7 8))) (One 9)
•
┌─┬───┼───┐
1 2 │ 9
┌───┴───┐
┌─┼─┐ ┌─┼─┐
3 4 5 6 7 8
One more Node3 is pushed down the spine, recursively splitting the Single
into a Deep with two Ones of Node3s.
<|tries to pack as tighly as possible (always createsNode3)- Always keeps two elements on either side, if possible (for fast
view) |>works exactly the same
viewL :: Sized a => FingerTree a -> Maybe (a, FingerTree a)
viewR :: Sized a => FingerTree a -> Maybe (FingerTree a, a)
viewL Empty = Nothing
viewL (Single a) = Just (a, Empty)
viewL (Deep s l t r) = Just $ case l of
Four a b c d -> (a, Deep (s - size a) (Three b c d) t r)
Three a b c -> (a, Deep (s - size a) (Two b c) t r)
Two a b -> (a, Deep (s - size a) (One b) t r)
One a -> case viewL t of -- Pull a node up from the spine
Just (Node3 b c d, t') -> (a, Deep (s - size a) (Three b c d) t' r)
Just (Node2 b c, t') -> (a, Deep (s - size a) (Two b c) t' r)
Nothing -> case r of -- If the spine is empty, balance with the right digit
Four b c d e -> (a, Deep (s - size a) (Two b c) Empty (Two d e))
Three b c d -> (a, Deep (s - size a) (Two b c) Empty (One d))
Two b c -> (a, Deep (s - size a) (One b) Empty (One c))
One b -> (a, Single b)Deep (Two 1 2) (Deep (One (Node3 3 4 5)) Empty (One (Node3 6 7 8))) (Two 9 10)
•
┌─┬───┼───┬─┐
1 2 │ 9 10
┌───┴───┐
┌─┼─┐ ┌─┼─┐
3 4 5 6 7 8
Deep (One 2) (Deep (One (Node3 3 4 5)) Empty (One (Node3 6 7 8))) (Two 9 10)
•
┌───┼───┬─┐
2 │ 9 10
┌───┴───┐
┌─┼─┐ ┌─┼─┐
3 4 5 6 7 8
Deep (Three 3 4 5) (Single (Node3 6 7 8)) (Two 9 10)
•
┌─┬─┬───┼───┬─┐
3 4 5 │ 9 10
┌─┼─┐
6 7 8
If the left Digit would become empty, recursively fetch a Node from the spine.
Deep (Two 4 5) (Single (Node3 6 7 8)) (Two 9 10)
•
┌─┬───┼───┬─┐
4 5 │ 9 10
┌─┼─┐
6 7 8
Deep (One 5) (Single (Node3 6 7 8)) (Two 9 10)
•
┌───┼───┬─┐
5 │ 9 10
┌─┼─┐
6 7 8
Deep (Three 6 7 8) Empty (Two 9 10)
•
┌─┬─┬───┴───┬─┐
6 7 8 9 10
Fetch one more Node from the sping, leaving the spine Empty.
Deep (Two 7 8) Empty (Two 9 10)
•
┌─┬───┴───┬─┐
7 8 9 10
Deep (One 8) Empty (Two 9 10)
•
┌───┴───┬─┐
8 9 10
Deep (One 9) Empty (One 10)
•
┌───┴───┐
9 10
If the spine is empty, try to fetch nodes from the right.
Single 10
•
│
10
- Never leaves four elements on either side, for fast subsequent
<|. viewRworks exactly the same.
viewL performs in amortized O(1).
- Rewriting a
Deepwith its (strict)Digits costs one credit. - Every access to the spine (push down/pull up) costs one credit.
Access to the spine only happens for One and Four. Those Digits are called
dangerous, the others are safe.
Note that every access to a dangerous digit makes it safe:
- Adding/removing elements:
One->Two,Four->Three - Accessing the spine:
One->Three/Two,Four->Two
- Costs one credit for writing the
Two. - Each recursion creates a thunk that will eventually cost one credit.
- Each recursion turns a dangerous digit into a safe one.
- Accessing the
Digitcosts one credit. - Each recursion forces a thunk in the spine, which must already be paid for.
- Each recursion turns a dangerous digit into a safe one.
Charge two credits per cons and viewL: One to rewrite the Digit, and one
to pay the debt of a spine thunk.
Invariant: Every time a digit becomes dangerous, the debt for the spine thunk is resolved.
Inductive proof:
- Step: When recursing down the spine, assuming its debt has been paid, we
use our extra credit to pay for the spine of the first safe
Digitwe encounter. All theDigits on the way are now safe. - Initial: When creating a spine, we immediately use the extra credit to resolve its debt.
=> Spines of dangerous Digits are guaranteed to be paid for, spines of safe
Digits may have open debt.
=> Each time we access the spine, the debt has already been paid!
split :: Sized a => Int -> FingerTree a -> (FingerTree a, FingerTree a) uses
the size annotation to decide which subtree/digit/node to split.
O(log n): On each level, we create two digits and two lazy spines.
merge :: FingerTree a -> FingerTree a -> FingerTree a creates Nodes from
adjacent Digits and pushes them up the spine.
O(log n): On each level, we merge two digits, and push at most four nodes up
the spine.
lookup :: Sized a => Int -> FingerTree a -> Maybe a looks up the i-th
element by splitting the tree at i and returning the minimum element of the
right tree.
O(log n): It's just a split plus a constant time operation.
-
Sequences (
Data.Sequence), Queues:O(log n)random access,O(1)access to both ends, O(log n)append. -
(Fair) Priority Queues: Replace the Size annotation by a Priority annotation.
O(1)insert andO(log n)access to the minimum element.
Used in Data.Set and Data.Map in containers.
Maps (Sets) use theOrdinstance of the keys (elements) to maintain ordering forO(log n)worst-case insert and lookup.- To prevent degeneration to
O(n)in pathological cases, two subtrees are rebalanced if their sizes differ by a factor greater than 3.
data Map k v
= Bin { size :: !Int
, key :: !k
, root :: v
, left :: !(Map k v)
, right :: !(Map k v) }
| TipUsed in Data.Heap in Edward Kmett's heaps.
- A variant of Binomaial Heaps with worst-case instead of amortized bounds.
- Used as Priority Queues
- Same asymptotic bounds as Finger Trees, slightly faster, but not stable (fair).
data Heap a
= Empty
| Tree { rank :: !Int
, root :: a
, forest :: [Heap a]
-- ^ Zero or one tree of each rank smaller than this tree's rank,
-- ordered by increasing rank. First two trees may have the same rank,
-- to limit number of carries per operation.
}- Immutability does not prevent efficient data structures.
- Smart compilers make stupid programs run fast.
- Being lazy can save you a lot of work.