NUMERICAL REPRESENTATIONS

Consider the ordinary representations of lists and natural numbers, along with several typical functions on each data type.

datatype µList = datatype Natural = Nil Zero

?Cons of µxµ List ?Succ of Natural

func tail (Cons (x , xs)) = xs func pred (Succ n) = n

func appnd (Nil, ys) = ys func plus (Zero, n) = n

?appnd (Cons (x , xs), ys) = ?plus (Succ m, n) =

Cons (x, appnd (xs, ys)) Succ (plus (m, n))

The two implementations are virtually identical Other than the fact that lists contain elements and natural numbers do not.This propose a strong similarity between representations of the number n and representations of container objects of size n.Functions on the container strongly similar to arithmetic functions on the number.Such as,deleting an element resembles decrementing a number, inserting an element resembles incrementing a number and combining two containers resembles adding two numbers.To design new implementations of container abstractions this similarity can be used.Select a representation of natural numbers with certain desired properties and define the functions on the container objects accordingly.An implementation designed in this pattern is known as a numerical representation.

The usual representation of lists can be viewed as a numerical representation based on unary numbers.However, numerical representations based on binary numbers are also common; the best known of these is the binomial queues of Vuillemin.Inserting an element into a unary representation usually takes O(1) time,because Incrementing a unary number takes O(1) time. However,combining two containers in a unary representation takes O(n) time,because adding two unary numbers takes O(n) time.Binary numbers improve the time required for addition (and hence the time required to combine two containers) to O(log n), but also slow the time required to increment a number or insert an element to O(log n). In this chapter, we acknowledge several