Annoyances of the Feature Kind

Yesterday, I finally sat down and wrote a priority queue (a heap to those in the know) to store the formulae on a branch that still need to be processed. Chris Okasaki (in his book Purely Functional Data Structures) defines the interface of a heap as follows:

class Heap h where empty :: (Ord a) => h a
isEmpty :: (Ord a) => h a -> Bool

insert :: (Ord a) => a -> h a -> h a
merge :: (Ord a) => h a -> h a -> h a

findMin :: (Ord a) => h a -> a
deleteMin :: (Ord a) => h a -> h a


This is a problem (in my opinion) in that it requires that heaps (all heaps) be over ordered data-types. The entire reason that I am attempting to extend the heap is to remove the ordering from the contained type, and use a priority type instead. Thus we are no longer saying that, for example, α < β but that (priority α) < (priority β)

I'll be the first to admit that this isn't much of a distinction to make (especially from a pragmatic "programmer" point of view), but it is a nicer approach.

I got around this problem, such as it is, by modifying my Prioritised class to have a function to inject values into my Priority type and one to extract them. The heap then is a type synonym:type PriorityHeap t = LeftistHeap (Priority t) with the restriction that you need to explicitly wrap values you insert into a heap:let h' = insert (priority v) h in ... and unwrap those you get out: let v = value $ findMin h' in ...

Not terribly inconvenient, but not ideal. I'm fairly sure that this could be solved with some functional dependancies magic, but the current state of affairs is good enough to be getting on with.