FIFO QUEUES

> class Queue q where
>   empty :: q a
>   isEmpty :: q a -> Bool
>   snoc :: q a -> a -> q a
>   head :: q a -> a
>   tail :: q a -> q a

We implement a queue by a pair of lists:
  one containing the elements in the front of the queue;
  the other containing the elements at the rear of the queue
  in reverse order.
  
> data BQueue a = BQueue [a] [a]

The front part of the queue should always be non-empty
unless the whole queue is empty.

> checkf :: BQueue a -> BQueue a
> checkf (BQueue [] r) = BQueue (reverse r) []
> checkf q = q

> instance Queue BQueue where
>   empty = BQueue [] []
>   isEmpty (BQueue f r) = null f  -- if f is empty, so is r
  
>   snoc (BQueue f r) x = checkf (BQueue f (x:r))
  
>   head (BQueue (x:f) r) = x
>   tail (BQueue (x:f) r) = checkf (BQueue f r)
  
Amortized analysis using the potential method.
Define a potential for every queue:

  phi :: BQueue a -> Int
  phi (BQueue f r) = length r

The amortized cost of any operation is the actual cost plus
the change in the potential function.
If an operation turns a queue q into q', then the amortized cost is:

   amortizedCost = actualCost + phi(q') - phi(q)
                            
It's easy to verify that the amortized cost of all operations is O(1). 
Therefore a sequence of n operations has cost O(n).


BINARY COUNTERS

> type Counter = [Bool]

A binary counter is simply a number in binary notation
with a function to increase it by one.
The Boolean values False and True are used for the binary
digits 0 and 1.
The number is written in inverse order: the head of the list
is the least significant digit.

Functions to traslate between integers and counters.
Just to show the interpretation of the counter: we do not use
them in code, but only use the increment operation.

> intCounter :: Integer -> Counter
> intCounter 0 = []
> intCounter x = odd x : intCounter (x `div` 2)
               
> countInteger :: Counter -> Integer
> countInteger [] = 0
> countInteger (b:bs) = if b then 1+2*countInteger bs else 2*countInteger bs

> increment :: Counter -> Counter
> increment [] = [True]
> increment (False:bs) = True : bs
> increment (True:bs) = False : increment bs

The worst case cost of an increment operation is equal to the length
of the binary counter. The worst case is when all values in the counter
are 1 (True).
So the worst case cost of n increment operations is O(n . log n),
since the length of the counter is logaritmic in the number of increments.

We can get a much better estimate of the cost of n increment operations
by using amortized analysis with the potential method.

We define the potential to be the number of unit digits:

  phi :: Counter -> Nat
  phi bs = number of True values in bs

phi is always positive and is 0 on the empty counter.
The actual cost of an increment operation is t+1,
where t is the number of leading True values in the counter:
all the leading True values are reset to False and the next False is
changed to True (or we add a True if we reached the end of the list).

The change of potential is -t+1 because we changed t True values to False
and added a new True value.

  phi(increment bs) - phi(bs) = -t+1

So the amortized cost is:

  amortizedCost = actualCost + phi(increment bs) - phi(bs)
                = t+1 -t+1 = 2

BINOMIAL HEAPS

In the file on binomial heaps we prove that all heap operations
cost O(log n) time, where n is the number of elements in the heap.
In particular, the insert operation has worst case complexity O(log n).
Therefore the cost of m operations is O(m.log n).

We can now prove that insert has amortized complexity O(1).

Define the potential as

  phi :: BHeap a -> Nat
  phi (h) = length h

Remember that a binomial heap is a list of binomial trees,
the potential is the number of trees in the heap.
If the heap contains n elements, then the number of trees is
equal to the number of ones in the binary expansion of n.
The situation is similar to that of a binary counter.
First of all, "insert" creates a new tree with the element
to be inserted and puts it into the heap by using insTree.
This increases the number of trees by 1.
Let k be the number of calls to "link" in the execution of the "insert"
operation. Every link step turns two trees into one, therefore
decreases the potential by one:

  phi (insert a h) - phi h = 1-k

The actual cost of "insert" is k+1, since every link takes O(1).
The amortized cost is then:

  amortizedCost = actualCost + phi(insert a h) - phi(h)
                = k+1+1-k = 2

Be careful: this shows that a sequence of n "insert" operations costs
O(n) time. This assumes that we are only using "insert" to modify the heap.
The other operations that modify the heap (deleteMin and merge)
don't have constant amortized complexity, but they still have logarithmic
amortized complexity.