CODEWITHSUNDEEP
haskellfunctional-programmingheapmutable
Anton
Anton

Reputation: 2585

Haskell mutable Heap structure

I want to make my heap data structure. Also i want to make operations with it in STM monad in multi-threaded application. The heap have size of 10 millions of elements. There are many operations on heap.

I have looked on this packages

  1. http://hackage.haskell.org/package/heap
  2. http://hackage.haskell.org/package/heaps

As i mean both of them are persistent. If we modify this data structure we get two versions. It is memory ineffective for heap with big size.

As i guess i need to implement mutable heap.

I want to hear your opinion and advice to get what i want.

Thanks.

Upvotes: 2

Views: 605

Answers (2)

luqui
luqui

Reputation: 60463

As Ankur points out, you may be outside the bounds of the pure functional side of Haskell. At least I have never seen a pure extract-min data structure with good memory performance -- don't take that to mean there isn't one. Have you profiled the existing libraries to make sure that they are not adequate for your needs? (Remember that a persistent data structure does not mean that the entire data structure is copied whenever a mutation is made, there can be lots of sharing between different "versions").

However, Haskell also has an imperative side, and you could implement a heap on that side. The performance characteristics of imperative Haskell are close to those of any other imperative language, so you will probably want to base your heap off of a mutable array of some type.

It might be tricky to implement it in a way that works nicely with STM, whose core concept is the TVar. You could base it off of a (even non-mutable) array of TVars, but since every operation touches the root of the heap there will be lots of contention and the STM overhead will hurt you. I would be more inclined to serialize access to the heap to one thread at a time using locks / MVars.

I know Data.Vector.Mutable is a popular mutable array library. Others will be more informed than I in recommending a good mutable array library for your purposes.

Upvotes: 2

Ankur
Ankur

Reputation: 33637

Them moment you start to think in terms of "mutable memory area" and "operations that modify this memory area", you are going out of the boundaries of Pure FP languages like Haskell and stuff which goes out of this boundary will require some special techniques in haskell like Monads. In your case of Mutable data structure you are crossing the fundamental boundary which I am not sure if even a Monad can help you to cross (a Monad may help you to simulate it like a mutable data structure ex: state monad - but that wont be what you are looking for as you want it to be "mutable" and not just a simulation.

Upvotes: 0

Related Questions