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

[Stephan Friedrichs]

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