Unordered map

[Andrew Wagner]

Well, it wouldn't need to literally implement Ord. It would just need
to do the same operations as Data.Map does, except without the
efficiency you get from Data.Map because you can assume an Ord
instance. One way to do it is to simply internally store the data as
an ordered [(a,k)], for example. Not efficient, but you get the same
interface as Map.

On Tue, Jul 29, 2008 at 4:26 PM, Peter Gavin <pgavin at gmail.com> wrote:
> 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
>