Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Using Data.Heap in Haskell, or reading Haskell docs for a beginner

I'm trying to use Haskells Data.Heap module, but I'm incapable of even using it with integers. The only heap I've been capable of using is "empty", which does not take any arguments.

Later on I'll figure out how to instance for my needs, but for now I'd be glad if I was even able to test it with numbers.

like image 858
Masse Avatar asked Apr 15 '10 06:04

Masse


1 Answers

Usually data structure libraries in Haskell provides fromList functions to convert from a list to that structure. Data.Heap is no exception. But you'll get some crazy errors when trying to use it:

Prelude Data.Heap> Data.Heap.fromList [1,2,5,7]

<interactive>:1:0:
    Ambiguous type variables `t', `pol' in the constraint:
      `HeapItem pol t'
        arising from a use of `fromList' at <interactive>:1:0-27
    Probable fix: add a type signature that fixes these type variable(s)

....

This main point here is Ambiguous type. There are several types of heaps, e.g. MaxHeap and MinHeap, which cannot be inferred from just calling fromList. You need to tell Haskell which kind of heap you're using with a type signature:

Prelude Data.Heap> Data.Heap.fromList [1,2,5,7] :: MinHeap Int
fromList [(1,()),(2,()),(5,()),(7,())]

Other constructors e.g. singleton, fromAscList, etc. operate similarly.

Once you've constructed the heap, the rest are easy, e.g. to insert an item to a heap

Prelude Data.Heap> let heap = Data.Heap.fromList [1,2,5,7] :: MinHeap Int
Prelude Data.Heap> heap
fromList [(1,()),(2,()),(5,()),(7,())]
Prelude Data.Heap> Data.Heap.insert 3 heap
fromList [(1,()),(3,()),(2,()),(5,()),(7,())]

To read the top of the heap

Prelude Data.Heap> heap
fromList [(1,()),(2,()),(5,()),(7,())]
Prelude Data.Heap> viewHead heap
Just 1

etc.

like image 115
kennytm Avatar answered Sep 19 '22 12:09

kennytm