Hi, I'm sorry it took me so long to respond! apfelmus@quantentunnel.de wrote:
[newtype Ord a => Reverse a = Reverse { unReverse :: a }]
This solution should be used for all collections depending on Ord instances, including Data.Map, Data.Set and others. As long as I only include it in my tiny heap package, it is as 'non-standard' as my approach, isn't it?
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.
[...]
Note that the Heap class contains only three primitive operations (empty, insert, viewHead), all the others have default implementations in terms of those three. There is even an underappreciated unfold among them :)
toAscList = unfoldr viewHead
The structure becomes especially clear by noting that any Heap is defined by just two primitives
inject :: Ord a => Maybe (a, Heap a) -> Heap a view :: Ord a => Heap a -> Maybe (a, Heap a)
We have inject = maybe empty (uncurry insert) . This is just like lists, except that view . inject ≠ id since view returns the smallest element.
I stumbled over the similarity of heaps and lists when implementing take, takeWhile, span, break, etc. (btw, they are included in heap-0.2 which I uploaded yesterday); so a heap is really nothing but a packed representation of a sorted list :)
However, just that we managed to reduce the number of primitive operations doesn't mean that the policy approach isn't preferable. It needs 0 primitive operations, after all. But as foreshadowed in my reply, it's possible to do policies within Ord. Don't stop thinking about your good idea just because you can start coding :)
Here's one way to do it:
[...]
In conclusion: the ordering policy stuff should not be part of Data.Heap, this is a job for Data.Ord. As mentioned above: This sounds really useful. How about you propose this to the base-package maintainers? :)
What, me? :D
Where? :) Regards, Stephan -- Früher hieß es ja: Ich denke, also bin ich. Heute weiß man: Es geht auch so. - Dieter Nuhr