Unordered map

[Peter Gavin]

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 <ndmitchell at gmail.com> 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