dense representation, on the other hand, is simply a list (or some other kind of sequence) of digits, including those digits that happen to be 0.

For example, this shows two different representations of binary numbers in Standard ML- one dense and one sparse— along with several representative functions on each.

structure Dens =

struct

datatype Digit = Zero ? One

type Natural = Digit list (* increasing order of significance, no trailing Zeros*)

func increment = One

? increment (Zero :: ds) = One :: ds

?increment (One :: ds) = Zero :: increment ds (* carry*)

func decrement One =

? decrement (One :: ds) = Zero :: ds

? decrement (Zero :: ds) = One :: decrement ds (* borrow*)

func add (ds, ) = ds

? add ( , ds) = ds

? add (d :: ds1, Zero :: ds2) = d :: add (ds1, ds2)

? add (Zero :: ds1, d :: ds2) = d :: add (ds1, ds2)

? add (One :: ds1, One :: ds2) = Zero :: increment (add (ds1, ds2)) (*

carry*)

end

structure SparseByWeight =

struct

type Natural = int list (* increasing list of weights, each a power of two*) (* add a new weight to a list, recurse if weight is already present*)