可变Haskell堆的类型签名

我想在Haskell中创建一个基于可变数组的堆（在其他地方找到的基本类型）。有些事我不喜欢我的初步做法，但是：可变Haskell堆的类型签名

我用元组来表示我的堆而不是正确的数据类型的
我不知道如何申报我的类型使用（约太多类型变量），依靠类型推断（从哈斯克尔维基和复制的例子）
我的堆是不是多态
当f例如函数中使用我的堆，我已经将线穿入n周围。

将我的堆抽象成一个很好的数据类型的最佳方式是什么？我觉得这会解决我的大部分问题。

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)

来源

2011-05-11 hugomg

你一定要在包装一个抽象数据类型的底层表示，为建设和拆开你的堆数据结构只提供智能构造。

可变结构往往比不可变结构的API更简单（因为它们支持更少的好行为）。为了了解可变容器类型的合理API的样子，包括如何抽象表示，可以看看the Judy package。

尤其

The abstract data type，这是多态的元素

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

你需要支持许多相同的操作，具有类似的签名。

实际中，JudyL的基本表示由下式给出：

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

type JudyL_ = Ptr JudyLArray 

data JudyLArray

注意我们是如何通过锁定底层资源提供线程安全（在这种情况下，C指针的数据结构）。另外，该表示是抽象的，对用户不可见，保持API简单。

来源

2011-05-11 17:45:53

初学者一般的忠告 - 开始IOArrays而不是STArrays，所以你不必担心高kinded类型和附带ST的其他技巧。然后，当你得到满意的东西后，你可以考虑如何将它移动到ST。

除此之外，你应该做自己的ADT而不是元组。

data MutHeap a = MutHeap Int (IOArray Int a) 

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

等

来源

2011-05-11 17:30:04 sclv

可变Haskell堆的类型签名

回答

相关问题