親愛的（est）堆疊交換器，
我目前正在實作一些需要訪問“佇列”（FIFO）資料結構的演算法。我正在使用 ST monad ，因此我正在尋找與 ST monad 的“記憶體可變性”相輔相成的佇列實作。此時，我只是想newSTRef在串列上使用（但同樣，訪問最后一個元素是 O (n) 復雜性，我想盡可能避免這種情況。我也想使用 Data.Sequence，但我不確定如果在沒有newSTRef初始化的情況下在 ST monad 中使用它是否真的會“可變” 。
Stack Exchange 的友好成員能否指導 Haskell 的初學者在上述背景關系中什么是最好的資料結構（或模塊）？
uj5u.com熱心網友回復：
選項包括在 之上實作傳統的環形緩沖區STArray，或使用由STRefs構建的可變單鏈表，如下所示：
type CellRef s a = STRef s (Cell s a)
data Cell s a = End | Cell a (CellRef s a)
data Q s a = Q { readHead, writeHead :: CellRef s a }
如果您想要輕松增長Q但就像環形緩沖區的低指標開銷一樣，您可以通過讓每個單元格都有一個STArray緩慢填滿的單元格來獲得中間立場。當它已滿時，分配一個新的單元格；當讀取它清空它時，前進到下一個單元格。你明白了。
uj5u.com熱心網友回復：
FIFO 佇列的標準實作是兩個 LIFO 堆疊，一個包含從佇列前面開始的專案（下一個要洗掉的專案在頂部），另一個包含從后面開始的專案（最近將專案推到頂部）。從佇列中彈出時，如果前堆疊為空，則將其替換為后堆疊的反轉。
如果兩個堆疊都實作為 Haskell 串列，那么向佇列添加一個值是 O(1)，如果以單執行緒方式使用資料結構，則洗掉一個值將攤銷 O(1)。常數因子還不錯。您可以將整個資料結構放在 STRef 中（保證單執行緒使用）。實作只是幾行代碼。您絕對應該優先于您的 O(n) 單串列想法來執行此操作。
您也可以使用Data.Sequence. 和二堆疊佇列一樣，它是一種純函式式資料結構，即對它的操作回傳一個新的資料結構，舊的保持不變。但是，就像兩堆疊佇列一樣，您可以通過簡單地將新資料結構寫入保存舊資料結構的 STRef 來使其可變。for 的常數因子Data.Sequence可能比兩堆疊佇列差一點，但作為交換，你得到了一組更大的高效操作。
David Wagner 的答案中的可變串列可能效率較低，因為佇列中的每個專案需要兩個堆物件。您可以通過撰寫在 GHC 中避免這種情況
Cell a {-# UNPACK #-} !(CellRef s a)
代替Cell a (CellRef s a). 不過，我不確定這會奏效。如果是這樣，這可能比其他基于串列的方法要快一些。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/316854.html