Re: Unordered map

Andrew Wagner wrote:

Ah, good call. I don't have an interpreter handy, but I'm sure you're right. What about the other method of making the library more consistent? One that assumes some default (non-)ordering?

Any such built-in ordering would have to be provided by the compiler, and I bet would be hard to implement in a referentially transparent way. Remember that the only thing that's common to all types in Haskell is _|_, so there's nothing a polymorphic function could use for ordering. Pete

On Tue, Jul 29, 2008 at 2:05 PM, Neil Mitchell wrote:

...

Hi

...

The other way to make the library more consistent, perhaps, would be to simply move the Ord requirement up to that data structure: that is, make it Ord k => Map k a, and then have a new data structure like UnorderedMap (or, to use a more standard term, Dictionary). Have you tried to do this? You get errors all over the place, the monomorphism restriction kicks in, and it goes really wrong. Consider Data.Map.empty, you'd have to pass an Ord dictionary for the key, which often isn't known at that point. Suddenly the code:

newMap = Data.Map.empty

Stops working! Having too much polymorphism at random places breaks it.

In essence, putting a context on a data type is a really bad idea. Haskell's solution with Data.Map is perfectly fine, and seems logical once you realise that its just the Haskell encoding of Ord k => Map k a

Thanks

Neil