Programming Praxis

In computer science, a map is a data type that associates a value with a key; all keys are unique, and the only comparison allowed is equality (are these two keys equal?). An ordered map extends the rule from equality to order (is one of these keys less than the other?), and if the ordered map also admits ranking the elements of the map (this item is first, that item is second, and so on), it is said to provide order statistics. A basic map is usually implemented with a hash table, and the two ordered variants are usually implemented with some kind of balanced tree (treap, avl, red-black). Maps are sometimes called dictionaries, though which type of map is intended is frequently unspecified, and the word dictionary can refer to either ordered or unordered maps.

Today’s exercise describes an abstract data type that provides an ordered map with order statistics. We provide the basic operations lookup, insert, and delete, and also an update function that either updates an existing value or inserts a new key/value pair in the map. For order statistics we provide the size, nth and rank operators. We also provide the higher-order functions map, fold and for-each, and conversions to and from lists. And finally, we provide an iterator to generate the key/value pairs in the map, one by one, in ascending order.

We use avl trees to implement our map; the code was given in two previous exercises. We also steal the generator code from a previous exercise. The new data type has recently been added to the Standard Prelude.

Your task is to implement an abstract data type of ordered maps with order statistics as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2