[Haskell-cafe] Re: [Haskell] Why functional programming matters

[apfelmus]

Stephan Friedrichs wrote:
> I just uploaded a generalised heap (min-, max- and custom-heaps) 
> implementation:
> 
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/heap-0.1
> 
> Feedback would be appreciated :)

Feedback: I think the HeapPolicy thing is too non-standard. The 
canonical way would be to use a MinHeap and let the Ord instance handle 
everything. A MaxHeap can then be obtained via a different Ord instance

    newtype Ord a => Reverse a = Reverse { unReverse :: a }

    instance Ord a => Ord (Reverse a) where
      compare = comparing unReverse

This newtype should be in Data.Ord, of course. Being 
minimum/maximum-agnostic seems like a noble goal but turns out not to be 
that good. To see why, I'd like to report the first documentation bug: 
will a custom heap's  head  be the minimum or the maximum with respect 
to a custom  heapCompare  ? (ok, the docs for  head  indicate  minimum, 
but the docs for  HeapPolicy  should say so, too.)


Simply setting

   type MaxHeap a = MinHeap (Reverse a)

is inferior to a "native" MaxHeap since we'd have to pack/unpack the 
Reverse  all the time. But a type class for heaps - which should be 
present anyway - can solve that problem:

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

      fromAscList :: Ord a => [a] -> h a
      toAscList   :: Ord a => h a -> [a]


      null    :: Ord a => h a -> Bool
      null = isNothing . viewHead

      singleton :: Ord a => a -> h a
      singleton = flip insert empty

      head      :: Ord a => h a -> a
      head = fst . fromJust . viewHead

      deleteHead :: Ord a => h a -> h a
      deleteHead = maybe empty snd . viewHead

      ... etc.

   instance Heap MinHeap where ...

   newtype MaxHeap a = M (MinHeap (Reverse a))
   instance Heap MaxHeap where ...

The  union  and  unions  functions are probably best not put in this 
class but implemented via separate  Monoid  instances.


In conclusion: the ordering policy stuff should not be part of 
Data.Heap, this is a job for Data.Ord.


In particular, Data.Ord might contain something like

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

    class OrdPolicy p a where ...

    instance OrdPolicy p a => Ord (OrdBy p a) where ...

which can then be used to implement heaps with such different orderings 
in one go:

    newtype OrdPolicy p a => HeapP p a = HeapP (MinHeap (OrdBy p a))

    instance Heap (HeapP p) where ...


Regards,
apfelmus