Data.Map, Data.IntMap documentation

[apfelmus]

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 
Haskell. So I prefer

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

over

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

since the latter is not a Haskell expression. Besides, the haddock 
neither defines it nor is there at least a  show  function or similar 
that outputs this string representation.

Regards,
apfelmus