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