Type signatures for a mutable Haskell Heap

Question

I want to make in Haskell a mutable array based heap (the basic kind found everywhere else). There are some things I don't like about my initial approach, however:

• I use tuples to represent my heaps instead of a proper data type
• I don't know how to declare the types I am using (too many type variables around), relying on type inference (and copying examples from the Haskell Wiki)
• My heap isn't polymorphic
• When using my heap in the f example function, I have to thread the ns around.

What would be the best way to abstract my heap into a nice data type? I feel this would solve most of my problems.

buildHeap max_n =
  do
    arr <- newArray (1, max_n) 0 :: ST s (STArray s Int Int)
    return (0, arr)
  -- My heap needs to know the array where the elements are stored
  -- and how many elements it has

f n =  --example use
  do
    (n1, arr) <- buildHeap n
    (n2, _) <- addHeap (n1, arr) 1
    (n3, _) <- addHeap (n2, arr) 2
    getElems arr
main = print $ runST (f 3)

Answer 1

You should definitely wrap the underlying representation in an abstract data type, and provide only smart constructors for building and taking apart your heap data structure.

Mutable structures tend to have simpler APIs than immutable ones (as they support fewer nice behaviors). To get a sense for what a reasonable API for a mutable container type looks like, including how to abstract the representation, perhaps look at the Judy package.

In particular,

• The abstract data type, which is polymorphic in the elements

And the API:

new :: JE a => IO (JudyL a)  
  -- Allocate a new empty JudyL array.

null :: JudyL a -> IO Bool   
  -- O(1), null. Is the map empty?

size :: JudyL a -> IO Int       
  -- O(1), size. The number of elements in the map.

lookup :: JE a => Key -> JudyL a -> IO (Maybe a) 
  -- Lookup a value associated with a key in the JudyL array.

insert :: JE a => Key -> a -> JudyL a -> IO () 
  -- Insert a key and value pair into the JudyL array. Any existing key will be overwritten.

delete :: Key -> JudyL a -> IO ()  
  -- Delete the Index/Value pair from the JudyL array.

You'll need to support many of the same operations, with similar type signatures.

The actual, underlying representation of a JudyL is given by:

newtype JudyL a =
            JudyL { unJudyL :: MVar (ForeignPtr JudyL_) }

type JudyL_ = Ptr JudyLArray

data JudyLArray

Notice how we provide thread safety by locking the underlying resource (in this case, a C pointer to a data structure). Separately, the representation is abstract, and not visible to the user, keeping the API simple.

Answer 2

A general piece of advice for a beginner -- start with IOArrays rather than STArrays so you don't have to worry about higher-kinded types and the other tricks that come with ST. Then, after you've gotten something you're happy with, you can think about how to move it, if you desire, to ST.

Along with that, you should make your own ADT instead of tuples.

data MutHeap a = MutHeap Int (IOArray Int a)

buildHeap max_n = do
  arr <- newArray_ (1, max_n) 
  return (MutHeap 0 arr)

etc.