design - Type signatures for a mutable Haskell Heap -

i want make in haskell mutable array based heap (the basic kind found everywhere else). there things don't initial approach, however:

• i use tuples represent heaps instead of proper data type
• i don't know how declare types using (too many type variables around), relying on type inference (and copying examples haskell wiki)
• my heap isn't polymorphic
• when using heap in f example function, have thread ns around.

what best way abstract heap nice data type? feel solve of problems.

buildheap max_n =       arr <- newarray (1, max_n) 0 :: st s (starray s int int)     return (0, arr)   -- heap needs know array elements stored   -- , how many elements has  f n =  --example use       (n1, arr) <- buildheap n     (n2, _) <- addheap (n1, arr) 1     (n3, _) <- addheap (n2, arr) 2     getelems arr main = print $ runst (f 3) 

you should wrap underlying representation in abstract data type, , provide smart constructors building , taking apart heap data structure.

mutable structures tend have simpler apis immutable ones (as support fewer nice behaviors). sense reasonable api mutable container type looks like, including how abstract representation, perhaps @ the judy package.

in particular,

• the abstract data type, polymorphic in elements

and api:

new :: je => io (judyl a)     -- allocate new empty judyl array.  null :: judyl -> io bool      -- o(1), null. map empty?  size :: judyl -> io int          -- o(1), size. number of elements in map.  lookup :: je => key -> judyl -> io (maybe a)    -- lookup value associated key in judyl array.  insert :: je => key -> -> judyl -> io ()    -- insert key , value pair judyl array. existing key overwritten.  delete :: key -> judyl -> io ()     -- delete index/value pair judyl array. 

you'll need support many of same operations, similar type signatures.

the actual, underlying representation of judyl given by:

newtype judyl =             judyl { unjudyl :: mvar (foreignptr judyl_) }  type judyl_ = ptr judylarray  data judylarray 

notice how provide thread safety locking underlying resource (in case, c pointer data structure). separately, representation abstract, , not visible user, keeping api simple.