Data.Map, Data.IntMap documentation
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 ".
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
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
fold f z = foldr f z . elems
cannot be expressed with lookup. As an example for fold, the textual
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
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
The joy of Haskell is that the laws themselves can be expressed in
Haskell. So I prefer
fromList [(5,"a"), (3,"b")]
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.
More information about the Libraries