Data.Ord and Heaps

[apfelmus]

Ross Paterson wrote:
> Stephan Friedrichs wrote:
>> apfelmus wrote:
>>> [newtype Ord a => Reverse a = Reverse { unReverse :: a }]
>>>
>>> Yes. I mean "non-standard" in the software-reuse sense, i.e. Ord is for 
>>> user-defined orderings and should be the only such mechanism in order 
>>> to enable reuse. In fact, Data.Heap clearly shows that Data.Ord is  
>>> currently missing functionality.
>> Ah, now I see. The entire ordering policy mechanism - no matter how it  
>> is going to be solved - belongs into Data.Ord and not in Data.Heap. As  
>> soon as Data.Ord provides a solution, I'll use it in Data.Heap.
> 
> Unfortunately the Data.Ord module is constrained to use only Haskell
> 98 features, because it is used by all implementations.  So it could
> include the above Reverse (also mentioned in the group-by HW paper),
> but not the various OrdPolicy proposals.

The advantage of policies is that the Heap interface is implemented 
exactly once. Using  Reverse  is no problem, but you'd have to implement 
  one normal version (MinHeap a) and one boilerplate version (MinHeap 
(Reverse a)). Implementing  Heap p a  for both  p = Identity  and  p = 
Reverse  at once can eliminate this boilerplate.

Fortunately, the "polymorphic policies"  Identity  and  Reverse  can be 
implemented in Haskell98!

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

  class OrdPolicy p where
      compare' :: Ord a => OrdBy p a -> OrdBy p a -> Ordering

  instance (Ord a, OrdPolicy p) => Ord (OrdBy p a) where
      compare = compare'


  class Heap h where
      empty    :: Ord a => h a
      insert   :: Ord a => a -> h a -> h a
      viewHead :: Ord a => h a -> Maybe (a, h a)

  data HeapP p a = ... -- MinHeap (OrdBy p a)

  instance OrdPolicy p => Heap (HeapP p) where
      ...


What probably can't be done in Haskell98 are policies  p  that only work 
for specific types, i.e. such that  OrdBy p a  is not always an instance 
of  Ord . Of course, there is the question whether they are needed or 
whether they are just overengineering. I hope that Stephan Friedrichs 
has a compelling example for the former? :)

That being said, I think there might be a Haskell98 way to implement 
even them. The trick here is that while class contexts like  Ord (OrdBy 
p a)  are not H98, contexts like  Ord (p a)  with type variables only are.

   class Identity f where
      to   :: a -> f a
      from :: f a -> a
      -- subject to  to . from = id  and  from . to = id
      -- the latter holds automatically thanks to parametricity

   data Heap p a = ... -- MinHeap (p a)

   empty    :: (Identity p, Ord (p a)) => Heap p a
   insert   :: (Identity p, Ord (p a)) => a -> Heap p a -> Heap p a
   viewHead :: (Identity p, Ord (p a)) => Heap p a -> Maybe (a, Heap p a)

In other words, the context (Identity p, Ord (p a)) expresses what a 
multi-parameter type class  OrdPolicy p a  would do, too. I wonder 
whether this trick can be used to encode arbitrary multi-parameter type 
classes in plain Haskell98. I guess not, because interestingly,  Ord (p 
a)  is not a valid context for class or instance declarations, it's only 
ok for function definitions. So, defining stuff like

   instance Show (p a) => Show (Heap p a) where ...

is not possible, which limits this approach somewhat. Another limit of 
non-polymorphic policies is that the  Heap  class would have to be 
multi-parameter (which it should be anyway of course, but that's not H98).


Regards,
apfelmus