[Haskell-cafe] Re: Data.Ord and Heaps (Was: Why functional
programming matters)
Stephan Friedrichs
stephan.friedrichs at tu-bs.de
Mon Feb 4 07:09:00 EST 2008
Hi,
I'm sorry it took me so long to respond!
apfelmus at 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 252 bytes
Desc: OpenPGP digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080204/128cf147/signature.bin
More information about the Haskell-Cafe
mailing list