[Haskell-cafe] Re: Data.Ord and Heaps (Was: Why functional programming matters)

apfelmus apfelmus at quantentunnel.de
Wed Feb 6 10:51:27 EST 2008

Stephan Friedrichs wrote:
> I'm sorry it took me so long to respond!

No worries :)

>>>> In conclusion: the ordering policy stuff should not be part of 
>>>> Data.Heap, this is a job for Data.Ord.
>>> This sounds really useful. How about you propose 
>>> this to the base-package maintainers? :)
>> What, me? :D
> Where? :)

Proposals for the base package go to  libraries at haskell.org  . A 
proposal is a darcs patch + a deadline. Unfortunately, ghc 6.8.* isn't 
yet available on Macports, I'd have to install 6.6.1 again on my wiped 
disk to get a haskell compiler and darcs.

I'm currently leaning towards code like

    data OrdBy p a = OrdBy { unOrdBy :: a }

    instance Eq a => Eq (OrdBy p a) where
       (==) = (==) `on` unOrdBy

    data Reverse
    type Reversed a = OrdBy Reverse a

    instance Ord a => Ord (OrdBy Reverse a) where
       compare = flip $ comparing unOrdBy

and probably another example for custom orderings. Do you now a good one?

I'm not so happy about the names. In particular, I don't like  unOrdBy , 
too much cAmelCase. Any other ideas? Maybe

    data Rearrange p a = Rearrange { unRearrange :: a }
    data ReOrd p a   = ReOrd   { unReOrd :: a }

But I guess it can't be helped and it's not too bad either.

The class constraint

   Ord (OrdBy p a) =>

will be common in user code, but it's a bit bulky for my taste. However, 
its main problem is that it's not Haskell98 :( A multi-parameter class 
(just like in the original heap-0.1)

   class OrdPolicy p a where ...
   instance OrdPolicy p a => Ord (OrdBy p a) where ...

is shorter but not H98 either. The name could be a mot juste, too.

   class Rearranged p a where ...
   class Ord' p a where ...
   class OrdBy p a where ... -- clashes with the name of the type


More information about the Haskell-Cafe mailing list