输入可变Haskell堆的签名

Question

我想在Haskell中创建一个基于可变数组的堆(在其他地方找到的基本类).但是,有些事情我不喜欢我最初的方法:

• 我使用元组来表示我的堆而不是正确的数据类型
• 我不知道如何声明我正在使用的类型(周围的类型变量太多),依赖于类型推断(以及从Haskell Wiki复制示例)
• 我的堆不是多态的
• 在f示例函数中使用我的堆时,我必须n绕过s.

将我的堆抽象为一个漂亮的数据类型的最佳方法是什么？我觉得这可以解决我的大部分问题.

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

您绝对应该将基础表示包装在抽象数据类型中,并且仅提供用于构建和拆分堆数据结构的智能构造函数.

可变结构往往比不可变结构具有更简单的API(因为它们支持较少的好行为).要了解可变容器类型的合理API是什么样的,包括如何抽象表示,也许请查看Judy包.

特别是,

• 抽象数据类型,在元素中是多态的

和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.

您需要支持许多相同的操作,具有类似的类型签名.

a的实际底层表示由JudyL下式给出:

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

type JudyL_ = Ptr JudyLArray

data JudyLArray

请注意我们如何通过锁定底层资源(在这种情况下,指向数据结构的C指针)来提供线程安全性.另外,表示是抽象的,并且对用户不可见,使API保持简单.