可變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堆的類型簽名

回答

相關問題