Ross, thanks a lot for the feedback. Sorry I'm late with the response. --- ross@soi.city.ac.uk 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.

Personally I prefer precise specifications of the behavior to examples (and think that examples leave less room on my screen for specs of other functions), but clearly tastes vary.

Agree that the description spec should be precise on its own and about differences in tastes.

But I think it's important that examples be an optional addition to the main description: one should be able to determine the behavior from the description alone. ... The examples are there to help, but if one has to use them guess what the function will do in some case then the description is faulty.

Completely agree. In a few cases I improved descriptions too. My goal was not to provide missing information in the examples, but have complete functions specification in both - examples and text descriptions, so whatever you just said would still hold true if you swapped "examples" with "description" ;-) I consider examples to be complimentary to a description, but in general of the same importance. Each of these forms of behavior specification has its own advantages depending on a situation. The very fact of having two forms of specifications can help in understanding. This is like having a description of a programming language and its formal grammar. One can be used to debug and understand another.

So I'd favour setting off the examples at the end of each function description,

What do you mean? Isn't this how it is already? http://hackage.haskell.org/trac/ghc/attachment/ticket/1611/Data-Map.html?for...

and making them more concise by presenting them as equations.

I considered this. 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"} Example - in my documentation we have this: let m = fromList [(5,"a"), (3,"b")] m {3:="b",5:="a"} map (++ "x") m {3:="bx",5:="ax"} The equation form would be (map (++ "x") (fromList [(5,"a"), (3,"b")])) == (fromList [(5,"ax"), (3,"bx")]) IMHO in the first case it is easier to understand.

My ideal would be if Haddock could present each examples part as initially hidden but expandable with a click.

My personal preference is to keep them together. What do you think? Andriy ____________________________________________________________________________________ Boardwalk for $500? In 2007? Ha! Play Monopoly Here and Now (it's updated for today's economy) at Yahoo! Games. http://get.games.yahoo.com/proddesc?gamekey=monopolyherenow

Thanks everybody for the feedback. I'm responding to all the comments at once. Please let me know if I missed something. The consensus is to have the complexity information in the beginning of descriptions. I'll return it back. --- Sebastian Sylvan wrote:

Examples take more real-estate than descriptions (most often) and are also less precise (most often). I'd also prefer to have it hidden if possible (e.g. some java script collapsible frame or something).

I like this suggestion, but such haddock improvements are out of scope for this change. I can, however, remove printing of the initial data to make the examples more compact, so instead of: let m = fromList [(5,'a'), (3,'b'), (7,'c')] m {3:='b',5:='a',7:='c'} ... it will be: let m = fromList [(5,'a'), (3,'b'), (7,'c')] ... The examples are too short to put them in separate sections at the end of the document, as I did with the Control.Monad examples. --- apfelmus wrote:

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). ...

Such formulas can definitely be part of the description. I'm relatively new to Haskell. While I trust that the way you described it are accurate, it takes much more effort to understand it (especially the parts with "homomorphisms", "mplus", etc) than to understand what function does. This is probably not because these topics are complex, but because I don't know terminology, not yet fluent with the concepts. Concrete examples are more useful for a person with "practical programming" background learning Haskell libraries, who just wants to start using them. --- apfelmus wrote:

...

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.

{3:="b",5:="a"} is actually the output of "show" function from the older GHC version I used when I started to work on the Data.Map documentation :-) In the middle of the changes I upgraded to the new version of Ubuntu, got a newer compiler, which just prints "fromList [(3,"b"),(5,"a")]". I want to collect feedback on your suggestion. Do you guys prefer this format: let m = fromList [(5,'a'), (3,'b')] insert 5 'x' m == fromList [(5,'x'), (3,'b')] insert 10 'x' m == fromList [(5,'a'), (3,'b'), (10,'x')] insert 5 'x' empty == fromList [(5,'x')] over this: let m = fromList [(5,'a'), (3,'b')] insert 5 'x' m {3:='b',5:='x'} insert 10 'x' m {3:='b',5:='a',10:='x'} insert 5 'x' empty {5:='x'} apfelmus, the first form is what you want? Can you suggest any other improvements? --- Adrian Hey wrote:

But I really think this discussion is somewhat moot as IMO the entire Data.Map module should be deprecated in favour of this..

http://darcs.haskell.org/packages/collections-ghc6.6/Data/Map/AVL.hs

and ultimately this..

http://darcs.haskell.org/packages/collections-ghc6.6/Data.Trie.General/Data/...

not that I'm in any way biased :-)

I hope that the new Map implementation will at least have the same level of documentation ;-) --- Adrian Hey wrote:

I found hardest thing about writing the clone was figuring out precisely what many of the functions did. (In many cases either the documentation was ambiguous, or it was OK but the implementation was not consistent with the docs.)

When writing these docs we found and fixed a couple of bugs and documentation inconsistencies. Andriy ____________________________________________________________________________________ Luggage? GPS? Comic books? Check out fitting gifts for grads at Yahoo! Search http://search.yahoo.com/search?fr=oni_on_mail&p=graduation+gifts&cs=bz

Andriy Palamarchuk wrote:

apfelmus wrote:

...

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). ....

Such formulas can definitely be part of the description. I'm relatively new to Haskell. While I trust that the way you described it are accurate, it takes much more effort to understand it (especially the parts with "homomorphisms", "mplus", etc) than to understand what function does. This is probably not because these topics are complex, but because I don't know terminology, not yet fluent with the concepts. Concrete examples are more useful for a person with "practical programming" background learning Haskell libraries, who just wants to start using them. [...]

I want to collect feedback on your suggestion. Do you guys prefer this format:

let m = fromList [(5,'a'), (3,'b')] insert 5 'x' m == fromList [(5,'x'), (3,'b')] insert 10 'x' m == fromList [(5,'a'), (3,'b'), (10,'x')] insert 5 'x' empty == fromList [(5,'x')]

over this:

let m = fromList [(5,'a'), (3,'b')] insert 5 'x' m {3:='b',5:='x'} insert 10 'x' m {3:='b',5:='a',10:='x'} insert 5 'x' empty {5:='x'}

apfelmus, the first form is what you want?

Yes. Perhaps aligning the equality signs. And there's the question whether to use == or = to express equality. Strictly speaking, the latter would be wrong since the binary tree may be balanced differently (which bite us in functions like showTree ) but the former is not capable of expressing properties like fromList [(undefined, 'a')] = undefined that convey information about strictness. Personally, I think I'd use = since it feels "more equal" :) The ultra-correct way would be to only use toAscList to observe equality, i.e. to state toAscList (insert 5 'x' m) = [(3,'b'), (5,'x')] but not insert 5 'x' m = fromList [(3,'b'), (5,'x')] since we are not guaranteed that the latter trees on each side of the equation are balanced the same way. This is related to the question "now, but what _is_ a finite map from keys to values?" that I tried to hint at in my previous post. Your examples are based - whether intentionally or not - on the answer "such a map _is_ a list of (key,value) pairs." In other words, to explain what an operation like insert does with Map k a , you explain it in terms of the two functions fromList and toAscList. Here's a reformulation of your example: toAscList (insert 5 'x' (fromList [(3,'b'), (5,'a')])) = [(3,'b'), (5,'x')] We can go further and say that this is = insertList 5 'x' [(3,'b'), (5,'a')] where insertList k x [] = [(k,x)] insertList k x ((k',y):ms) = if k == k' then (k,x):ms else (k',y):insertList k x ms In other words, the description of insert is based on knowing how to insert a key-value pair into a list of key-value pairs. Removing the concrete example list, we get toAscList . insert 5 'x' . fromList = insertList 5 'x' or toAscList . insert k x = insertList k x . toAscList for all keys k and values x.

(especially the parts with "homomorphisms", "mplus", etc)

(Due to the equation above, mathematicians would call toAscList a "homomorphism", but you can safely ignore that word. In the last post, I tried to show that lookup can take the role of toAscList , so that a finite map may also seen as being a function k -> Maybe a instead of being a list [(k,a)] . The mplus would be an equivalent of unionList with a strange name.)

...

I prefer to know the laws that hold. Such formulas can definitely be part of the description.

The discussion with lists of key-value pairs and insert may seem like nitpicking since to insert a key-value pair into a list, we humans can "look at it" and "just do it". Of course, we can only do so with a concrete examples. So, your examples are indeed best to show how the function "just does it". With examples only, we can't "do it in general" though. "Doing it in general" also means to be able to formally _prove_ that a program you write is correct. Only equational laws like toAscList . insert k x = insertList k x . toAscList or lookup k' (insert k x m) = Just x if k == k' lookup k' (insert k x m) = lookup k' m if k /= k' allow you to do that. With some training and an intuition about what the functions are supposed to do, succinctly formulated laws like that are almost easier to read than examples. In fact, it's a good idea to think up specifying laws before starting to code since in purely functional languages, you can systematically obtain and implementation from the laws. The classic paper on deriving implementations from their specification is Paul Hudak. The Design of a Pretty-printing Library. http://citeseer.ist.psu.edu/hughes95design.html with a follow-up Philip Wadler. A prettier printer. http://homepages.inf.ed.ac.uk/wadler/topics/ language-design.html#prettier The man who derives all his programs from specification is Richard Bird. You may want to have a look at his recent sudoku solver Richard Bird. A program to solve Sudoku Slides: http://icfp06.cs.uchicago.edu/bird-talk.pdf where he starts with an apparently correct but hopelessly slow specification and transforms it into a blazingly fast one. His introduction to Haskell Richard Bird. Introduction to Functional Programming using Haskel (2nd edition). http://www.amazon.com/ Introduction-Functional-Programming-using-Haskell/dp/0134843460 emphasizes this style, too.

Can you suggest any other improvements?

Maybe some examples are a bit arbitrary, for instance for the ..WithKey functions. I mean functionality like \k a -> Just ((show k) ++ ":" ++ a) probably won't show up in a real program. I wonder whether there are examples that are useful on their own. Regards, apfelmus

On 10/27/07, Andriy Palamarchuk wrote:

Thanks everybody for the corrections and suggestions. Finally I got back to this work. Sorry it took this long to respond.

Thanks for doing this! More documentation make me happy. -- Johan

And sounds like we need some QuickCheck properties too! apa3a:

I started to update documentation for Data.IntMap. I found a discrepancy between the modules' updateLookupWithKey behavior right in the area brought to my attention earlier:

--- Andriy Palamarchuk wrote:

...

* As per

http://www.haskell.org/pipermail/libraries/2007-March/007304.html

...

added following information to the description of updateLookupWithKey:

The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted.

The test case:

...

:m Data.Map let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")])

(Just "5:new a",fromList [(3,"b"),(5,"5:new a")])

...

:m Data.IntMap updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")])

(Just "a",fromList [(3,"b"),(5,"5:new a")])

The problem here is that Data.Map.updateLookupWithKey returns the *updated* value, but Data.IntMap.updateLookupWithKey returns the value *before* update.

Please agree on the behavior, fix the bug and let me know what to write in the docs. Thanks, Andriy

__________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Adrian Hey wrote:

There's special about AVL trees, Oops, insert the word "nothing" in the obvious place.

The original documentation only said "lookup and update". I think it makes more sense to return the old value (i.e. the lookup result in the original input map.), because the new value can be recomputed using the update function. The opposite (recomputation of the old value given the new one) is not possible. But I agree too, that deprecating this function is the right thing (in the future). Cheers Christian Andriy Palamarchuk wrote:

Don, I'll leave QuickCheck out of scope for the documentation change.

Adrian, question whether to deprecate updateLookupWithKey is worth discussing, but we need to fix the function anyway.

All my documentation changes are ready. I'm holding the patch only for this problem.

What if I leave the function description for IntMap the same as for Map and submit a bug report for the problem? Then the person resolving the bug will either fix the docs or the documentation.

Any thoughts? Andriy

__________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

Hi, I have always wondered about the usefulness of the "withKey" functions because the key is one of the arguments that the programmer is passing anyway, so they already know its value. The only situation that I can think of where that might not be the case is if the equality relation on the keys is actually an equivalence relation, so the key in the map might be different from the key that was passed by the programmer even though they are "equal", and the distinction between the two keys is important. I would be a bit suspect of code that relies on that though... Does anybody have other uses of the "withKey" functions? -Iavor PS: as for the bug, I would just fix it (i.e., send a patch) On 11/2/07, Adrian Hey wrote:

Andriy Palamarchuk wrote:

...

Adrian, question whether to deprecate updateLookupWithKey is worth discussing, but we need to fix the function anyway.

I would say just document the code as it is, warts and all. Don't change the functions because maybe someone is using them (though I suspect this is not the case).

But also add a DEPRECATE pragma to discourage further use.

Maybe do this for both IntMap and Map, because even if they were consistent, I don't think they're very useful. An API that clearly separates the process of searching for the key from whatever you want to do when it's found (or not) is so much more flexible and easy to understand IMHO.

BTW, the way I did this should also work for IntMap tries too AFAICT, but I'm not sure it would offer any performance advantage over a repeated lookup in this case. So maybe keep them for IntMap?

My 2p..

Regards -- Adrian Hey

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

--- Christian Maeder wrote:

Which implementation do you consider buggy? IntMap or Map?

(or may just document it as inconsistent)

Map is used much wider, so a change to its behavior would be more disruptive. We should take into account what other Map implementations do. See, e.g. this message mentioned earlier when discussing the documentation change: http://www.haskell.org/pipermail/libraries/2007-March/007304.html Andriy __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

Thanks everybody for the comment. Because there was no consensus about how to resolve the problem I ended up leaving Data.IntMap.updateLookupWithKey implementation as is and adding a documentation that its behavior differs from Data.Map.updateLookupWithKey. Also, this is the least disruptive alternative. Andriy ____________________________________________________________________________________ Get easy, one-click access to your favorites. Make Yahoo! your homepage. http://www.yahoo.com/r/hs

Iavor Diatchki wrote:

On Nov 21, 2007 7:34 PM, Andriy Palamarchuk wrote:

...

Because there was no consensus about how to resolve the problem I ended up leaving Data.IntMap.updateLookupWithKey implementation as is and adding a documentation that its behavior differs from Data.Map.updateLookupWithKey. Also, this is the least disruptive alternative.

I think that we should fix this: Data.IntMap should be a more efficient implementation of Data.Map, for the special case when the keys are Ints. The methods should not behave differently. No one seemed to disagree with the behavior that Christian (and also I) suggested, namely, to return the old value, so why don't we jsut make both implementations do that?

It seems, nobody wants to take the responsibility for changing the implementation (or overtake maintainership for any collection types). (Another suggestion was deprecation, but correcting it as we suggested would be more in the spirit of Daan, who initially designed DData.) Just a further note to: "Data.IntMap should be a more efficient implementation of Data.Map" This is currently not the case (at least) for the "size" function. Christian

Could somebody please commit the patch attached to this ticket? Sorry about a long delay before I finalized the patch. Thanks, Andriy --- Andriy Palamarchuk wrote:

Thanks everybody for the corrections and suggestions. Finally I got back to this work. Sorry it took this long to respond.

Log comment: Improved, fixed documentation for Data.Map, Data.IntMap. Added examples.

Changes since the first submission: * Moved time complexity Big-O values back to the beginning of function descriptions. * Converted examples from interpreter session-like format to more compact equation-like format. * As per

http://www.haskell.org/pipermail/libraries/2007-March/007304.html

added following information to the description of updateLookupWithKey:

The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted.

Ticket: http://hackage.haskell.org/trac/ghc/ticket/1611

Haddock output:

http://hackage.haskell.org/trac/ghc/attachment/ticket/1611/Data-Map.html?for...

Comments, suggestions, critique? Did I miss anything? I'll update IntMap for the final review. Andriy

__________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

____________________________________________________________________________________ Looking for last minute shopping deals? Find them fast with Yahoo! Search. http://tools.search.yahoo.com/newsearch/category.php?category=shopping

Andriy Palamarchuk wrote:

Ross, thanks a lot for the feedback. Sorry I'm late with the response.

--- ross@soi.city.ac.uk 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.

On the contrary, I have gone looking through entries solely to see their complexity (since I already know about what the functions _do_), especially when comparing two different collections or just looking. They are very short and I like them being the most introductory thing, myself. If you know anything about what complexities the data structure gives for various operations, it can actually suggest quite a bit about what the operation does! (e.g., an O(log(n)) operation CANNOT be a map...) Maybe it's because I have general data structures experience already from other languages, but... complexity is very important to me, it is often the first thing I want to see (it comes after the operation's name anyway!), O(n) lookup is almost as bad as no lookup, O(n^2) behavior, say, with (++)s is generally fatal, worthy of being called a bug in my program. (Practical speed observations like "IntMaps are fast even with not so large sizes" are very important too) Isaac

apfelmus wrote:

An example:

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

Shouldn't that be.. lookup k (union m m') = lookup k m `mplus` lookup k m' But I get confused by this, which is why I think it might be a good idea to deprecate union for Data.Map altogether. A related problem.. http://hackage.haskell.org/trac/ghc/ticket/1460 http://www.haskell.org/pipermail/libraries/2007-May/007491.html But I really think this discussion is somewhat moot as IMO the entire Data.Map module should be deprecated in favour of this.. http://darcs.haskell.org/packages/collections-ghc6.6/Data/Map/AVL.hs and ultimately this.. http://darcs.haskell.org/packages/collections-ghc6.6/Data.Trie.General/Data/... not that I'm in any way biased :-) But if we must stick with Data.Map for some reason then what Andriy is doing is worth while, the documentation does need improving. I found hardest thing about writing the clone was figuring out precisely what many of the functions did. (In many cases either the documentation was ambiguous, or it was OK but the implementation was not consistent with the docs.) Regards -- Adrian Hey

Johannes Waldmann wrote:

It feels strange reading "Data.Map should be replaced" because it had replaced Data.FiniteMap only recently.

Unfortunately AFAIK both the old Data.FiniteMap and the new Data.Map are based on the same underlying tree structure, which seems to do a not particularly good job of balancing rather expensively. Also, the efficient hedge algorithm seems to be a problem (not at all efficient in reality).

Are we going to play this game again soon?

Well I don't see any problem as the clone is intended to be just that. For most users it should be a case of just changing imports to use it. There are some API changes though, lots of stuff added and other stuff which probably should never have been in there in the first place deprecated or removed (like the indexing operations).

This is definitely the case for an interface (erm, type class) that will allow the programmer to choose between implementations.

Not sure what it is you're talking about that's "definitely the case". Ideally we should have just one class based API for multiple implementations of maps, which is what the collections package Map class aims to be. But there are a few contenders here. There are also the Edison classes. What is currently called the GT class in the collections package is another (it has some weird methods in the API that typical users wouldn't need but which are needed to implement other instances of GT). Regards -- Adrian Hey

apfelmus wrote:

The Ord-constraint is too limiting for tries.

Well it isn't going to disappear while I'm in charge of GT class :-) Why do you object to it? Ultimately we must be able to test keys for equality at least. Is there a type that is an instance of Eq, but not Ord (or could not reasonably be made an instance of Ord)? It's extremely useful to be able to give meaningful orderings when converting between tries and lists. In the case of constructing tries from ordered association lists there's a significant performance advantage too.

Also, the map type does not necessarily fix the key type,

For instances of GT it does. The point is that eventually the Trie type (and corresponding GT instance) will be designed optimally and specifically for one particular key type (using DrIFT, Derive, template Haskell or something..)

we can use one map with different key types.

Not with GT. If (say) Data.Map was an instance then we would have something like.. instance Ord k => GT (Map k) k where .. I.E. The map type constructor in question is (Map k), not Map. (Map k does fix the key type as k) Regards -- Adrian Hey

Benjamin Franksen wrote:

Adrian Hey wrote:

...

apfelmus wrote:

...

The Ord-constraint is too limiting for tries. Well it isn't going to disappear while I'm in charge of GT class :-) Why do you object to it? Ultimately we must be able to test keys for equality at least. Is there a type that is an instance of Eq, but not Ord (or could not reasonably be made an instance of Ord)?

Data.Typeable.TypeRep

Interesting problem, but I don't see any reason why this could not be an instance of Ord. Because of the weird Key hack that's there I guess you'd have to hand write this instance, not derive it. Then for GT you'd have to either hand write a matching GT instance or fall back on the less efficient but general purpose OrdGT.. http://darcs.haskell.org/packages/collections-ghc6.6/Data.Trie.General/Data/... Regards -- Adrian Hey

On Sat, Aug 18, 2007 at 03:33:19AM +0200, Benjamin Franksen wrote:

Adrian Hey wrote:

...

Benjamin Franksen wrote:

...

Adrian Hey wrote:

...

Is there a type that is an instance of Eq, but not Ord (or could not reasonably be made an instance of Ord)?

Data.Typeable.TypeRep

Interesting problem, but I don't see any reason why this could not be an instance of Ord.

I asked this question once and got as answer (from one of the Simons, IIRC) that exposing the obvious Ord instance would break referential transparency: there is no guarantee that the integer keys and therefore the order among TypeReps is the same for different runs, even of the same program.

This (counter-)example may be irrelevant for the discussion at hand or not. Anyway, you asked for one...

There's nothing stoping you from writing instance Ord TypeRep where compare = comparing show STRef could also be cheaply made Ord, but at the cost of a bit more work; the idea is to notice that GHC's compacting garbage collector never reorders "abstract heap addreses", a concept I just made up which starts at 0 and increases as new blocks are added to the heap; so one must create an inverse map from physical blocks (which are aligned, so finding metadata is just a bitmask) to abstract block numbers, and then use that information to implement a compareAddress# primop suitable for {ST,IO}Reff, TVar, and {ST,IO}{U,}Array (in the latter case, you would do address comparison for pinned arrays and arbitrarily declare all pinned arrays larger than all unpinned arrays). Stefan

Twan van Laarhoven wrote:

Now the Data.Map functions can be based on PrimOrd, because we don't actually care about the ordering. Except for to/fromAscList, which should check the ordering is actually an Ord.

and toList and fold, even for associative-commutative operations, because it can't know. Also it might be fair to lift the nondeterminism to IO, e.g. you could define your program's semantics to output these elements in an arbitrary unpredictable order. Maybe there should be a separate FloatOrd class if you want the fourth possibility of "false due to NaN" in your comparisons of floating-point numbers, so that Float/Double can be made proper members of PrimOrd. Isaac

What I want to say is that a very general Map class can itself be useful as abstraction, i.e. the programmer can build his own map types when they capture the essence of his problem. David House and I once stumbled upon this. The task was to write a polymorphic delete/insert for a web-forum. I mean, you can delete individual posts or whole forums type Site = Data.Map ForumID Forum type Forum = Data.Map ForumID Post type Post = String but you'd have to write different delete functions for that. The insight was that the Site is a map of forums instance Map Site ForumID where type Elem Site ForumID = Forum while also being a map of Posts instance Map Site (ForumID, PostID) where type Elem Site (ForumID, PostID) = Post So, insert and delete work for both the forums and the posts. The path from the root of the hierarchy to the object in question says whether it's a forum or a post to operate on. Adrian Hey wrote:

apfelmus wrote:

...

The Ord-constraint is too limiting for tries.

Well it isn't going to disappear while I'm in charge of GT class :-) Why do you object to it? Ultimately we must be able to test keys for equality at least. Is there a type that is an instance of Eq, but not Ord (or could not reasonably be made an instance of Ord)?

It's extremely useful to be able to give meaningful orderings when converting between tries and lists. In the case of constructing tries from ordered association lists there's a significant performance advantage too.

Well of course, every algebraic type can be made an instance of Ord and Eq. But neither is necessary for implementing Ralf Hinze. Generalizing generalized tries. http://www.informatik.uni-bonn.de/~ralf/publications/GGTries.ps.gz Those instances that want an Ord requirement can impose it but those that don't want it won't need to impose it.

...

Also, the map type does not necessarily fix the key type,

For instances of GT it does. The point is that eventually the Trie type (and corresponding GT instance) will be designed optimally and specifically for one particular key type (using DrIFT, Derive, template Haskell or something..)

...

we can use one map with different key types.

Not with GT. If (say) Data.Map was an instance then we would have something like..

instance Ord k => GT (Map k) k where ..

I.E. The map type constructor in question is (Map k), not Map. (Map k does fix the key type as k)

I don't see why a map should work for a single key type only, except that maps as type constructors support only one key type of course, since the element type is fixed then. Different key types may yield different element types. Regards, apfelmus

Adrian Hey wrote:

...

I don't see why a map should work for a single key type only, except that maps as type constructors support only one key type of course, since the element type is fixed then. Different key types may yield different element types.

I'm not sure I understand what you mean by single key type only. AFAICS you can only implement an *efficient* trie if it has been designed specifically for the key type in question, so of course it should come as no surprise that it will only work for the key type in question.

What I want to say is that the functional dependency map -> k is too restrictive. A single map type can serve as map for different types of keys and values. So, the type Foo k1 k2 a = Data.Map k1 (Data.Map k2 a) can be seen as a map from keys (k1,k2) to values a instance Map (Foo k1 k2 a) (k1,k2) where type Elem .. .. = a but also as a map from keys k1 to values (Data.Map k2 a) instance Map (Data.Map k1 (Data.Map k2 a)) k1 where type Elem .. .. = Data.Map k2 a Regards, apfelmus

Arie Peterson wrote:

Adrian Hey wrote:

...

...

The Ord-constraint is too limiting for tries. Well it isn't going to disappear while I'm in charge of GT class :-) Why do you object to it? Ultimately we must be able to test keys for equality at least. Is there a type that is an instance of Eq, but not Ord (or could not reasonably be made an instance of Ord)?

Complex numbers, and trees, and probably many more. Some types do not have a natural total ordering. Sure, you can pick some arbitrary one, but that can be confusing, and it decreases the ability of the type system to catch semantic errors.

True, but in practice it's hard to think of any Ordering that isn't completely arbitrary, other than reals perhaps. It isn't obvious to me that 'A' is less than 'B', or (1,2) is less than (2,1). But I don't see this as a big problem. It seems to me that there's no getting away from arbitraryness. Say the GT class abandoned the Ord constraint and just provided.. assocs :: map a -> [(k,a)] which returned the list of associations in some *arbitrary* (unspecified but still deterministic) order of keys. Is that any better? I would prefer to have some universal default ordering for any key type that was used consistently by various APIs, even if the ordering is arbitrary. Regards -- Adrian Hey

Adrian Hey wrote:

True, but in practice it's hard to think of any Ordering that isn't completely arbitrary, other than reals perhaps. It isn't obvious to me that 'A' is less than 'B', or (1,2) is less than (2,1). But I don't see this as a big problem.

Well, we could debate the naturality of these orderings, but that is beside my point, because these instances are in the standard libraries. Some data types (both in libraries and "user defined") *deliberately* do not have Ord instances, and currently Data.Map does not play nice with this choice. For example, when I write 'someTree < otherTree' the compiler shouts at me and helps me realise that I actually meant 'height someTree < height otherTree'. This mechanism fails once I need trees to be keys in a map. My current solution (newtypes) is far from ideal.

It seems to me that there's no getting away from arbitraryness. Say the GT class abandoned the Ord constraint and just provided..

assocs :: map a -> [(k,a)]

which returned the list of associations in some *arbitrary* (unspecified but still deterministic) order of keys. Is that any better? I would prefer to have some universal default ordering for any key type that was used consistently by various APIs, even if the ordering is arbitrary.

I'm all for arbitrary orderings, as long as they don't "pollute" the Ord class :-). Greetings, Arie

On 2007-08-18, Adrian Hey wrote:

Arie Peterson wrote:

...

Adrian Hey wrote:

...

...

The Ord-constraint is too limiting for tries. Well it isn't going to disappear while I'm in charge of GT class :-) Why do you object to it? Ultimately we must be able to test keys for equality at least. Is there a type that is an instance of Eq, but not Ord (or could not reasonably be made an instance of Ord)?

Complex numbers, and trees, and probably many more. Some types do not have a natural total ordering. Sure, you can pick some arbitrary one, but that can be confusing, and it decreases the ability of the type system to catch semantic errors.

True, but in practice it's hard to think of any Ordering that isn't completely arbitrary, other than reals perhaps.

No? These are usually somewhat arbitrary, but not completely arbitrary.

It isn't obvious to me that 'A' is less than 'B', or (1,2) is less than (2,1).

Both depend on convention. For pairs, either convention make sense, so we pick one arbitrarily. For something like complex numbers, there are many things one could do, but none of them make sense, essentially because of the /topology/. There are degrees of arbitrariness. We can work with small amounts just fine. Large amounts are more troublesome. -- Aaron Denney -><-

Isaac Dupree wrote:

Adrian Hey wrote:

...

apfelmus wrote:

...

The Ord-constraint is too limiting for tries.

Well it isn't going to disappear while I'm in charge of GT class :-) Why do you object to it? Ultimately we must be able to test keys for equality at least. Is there a type that is an instance of Eq, but not Ord (or could not reasonably be made an instance of Ord)?

STRef and similar, I think are in Eq but would need performance penalties to be in Ord, since they essentially only contain a pointer to their contents, and garbage collection can move and re-order them and their contents.

I guess anyone who wants an STRefMap will just have to suffer the performance penalty of O(n) lookup and make STRefMap an instance of some other map class (there are plenty to choose from :-) Regards -- Adrian Hey