# Data.Map, Data.IntMap documentation

apfelmus apfelmus at quantentunnel.de
Thu Aug 16 04:17:04 EDT 2007

Andriy Palamarchuk wrote:
>> I rather liked having the complexity at the start of
>> the description:
>> it allows one to find this important information at
>> a glance.
>
> My rationale was that the complexity information,
> while  important, is probably one of the last things
> most of the people are looking for.
> I doubt anybody would e.g. search for all the O(log n)
> operations ;-)
>
> I'll keep the complexity information at the end of
> description unless there are more votes against this.

I too think that the complexity should be at the beginning since that's
what I'm interested in when choosing a finite map implementation.

>> So I'd favour setting off
>> the examples at the end of each function
>> description, and making them more
>> concise by presenting them as equations.

Actually, while you did good work added the large amount of examples, I
don't like examples at all, I prefer to know the laws that hold. In
other words, I want an infinite amount of examples at once.  For
instance, the laws

lookup k' (insert k x m) = Just x        if  k == k'
lookup k' (insert k x m) = lookup k' m   if  k /= k'

uniquely define insert, they are everything you _can_ know about insert
(from the denotational point of view). And they are even shorter than
concrete examples (= their special cases).

In fact, a large group of operation on  Data.Map k a  can be specified
with corresponding operations on  k -> Maybe a . Put differently, the
introductory sentence really is: "finite maps are an efficient
implementation of maps from keys k to values a, i.e. of  k -> Maybe a ".
An example:

lookup k (union m m') = lookup k m' `mplus` lookup k m

In a sense, `mplus` is the union for the finite map type  Maybe a . In
other words, the specifications says that  lookup  is a homomorphism of
maps, or rather that the type  Data.Map k a  is a map thanks to that
homomorphism.
Another example:

lookup k (map f m) = f `fmap` (lookup k m)

Again,  fmap  is the  map  for  Maybe a .

Note that not every operation can be expressed in terms of  lookup . For
example,

fold f z = foldr f z . elems

cannot be expressed with lookup. As an example for fold, the textual
description gives

elems = fold (:) []

With this, I think that the textual description for  fold  is superior
to the description by examples, so that I even prefer them not to be
present at all.

It's not necessary to specify everything with external types like lists
or  k -> May a , combined functions can be expressed with the
components, like

updateLookupWithKey f k m = (lookup k m, updateWithKey f k m)

This is much clearer than examples and doesn't need interpretation like
the description "Lookup and update". Also, the link of the more general
functions their less general cousins is very useful description

insert k x m = insertWith (\new old -> new) k x m

> I did not make the examples in form
> of equations because in this particular case a map
> programmatic specification
>
>    fromList [(5,"a"), (3,"b")]
>
> is more noisy and less readable than its string
> presentation
>
>    {3:="b",5:="a"}

The joy of Haskell is that the laws themselves can be expressed in

fromList [(5,"a"), (3,"b")]

over

{3:="b",5:="a"}