隊列的Haskell類型

Question

是否有人編寫了描述FIFO隊列的Haskell類型類（或者是否有類型類的組合）。

Data.Collection.Sequence似乎太強大，但另一方面Data.Collection.Unfoldable似乎太弱（順序未定義）。

我只是想不重做別人的工作。

Answer 1

實際上，在Haskell中推出自己的FIFO隊列並不難（也是一個有趣的練習）。我可以欣賞你希望爲此使用標準類型類，這幾乎可以肯定你應該做的。但是我剛剛在上週瞭解到了這一點，我很興奮不寫這些。

下面是一個簡單的隊列類，它允許您檢查隊列是否爲空，從隊列的頭部獲取第一個元素（並返回隊列的其餘部分）並將新元素插入到隊列中。

class Queue q where 
    empty :: q a -> Bool 
    get :: q a -> (a, q a) 
    ins :: a -> q a -> q a 

做出FIFO隊列的最簡單方法是使用一個列表：

instance Queue [] where 
    empty = null 

    get []  = error "Can't retrieve elements from an empty list" 
    get (x:xs) = (x, xs) 

    ins x xs = xs ++ [x] 

然而，這是可怕的效率低下。如果隊列當前有n元素，則插入一個新元素需要O（n）時間。如果要將m元素插入空隊列，則需要花費O（m ）時間。我們可以創建一個隊列來插入和檢索O（1）時間內的元素（或者至少，O（1）攤銷時間）？

訣竅是存儲的前部和在單獨的列表的隊列的後面，與隊列的後面被存儲在反向：

data Fifo a = F [a] [a] 

instance Queue Fifo where 

隊列是空的，如果正面和背面是空：

empty (F xs ys) = null xs && null ys 

要插入一個新的元素到列表中，我們只是把它放在後面的隊列中，這需要O（1）次。

ins y (F xs ys) = F xs (y:ys) 

獲取元素從隊列的前部很容易當有等待在那裏元件（以及我們拋出一個錯誤，如果隊列爲空）

get (F []  []) = error "Can't retrieve elements from an empty queue" 
    get (F (x:xs) ys) = (x, F xs ys) 

最後，如果沒有元件在隊列的前面等待，然後我們將隊列的後面顛倒放在前面。雖然這需要O（ñ）的時候，我們只需要爲每個元素做一次，所以我們get操作平均到O（1）時間：

get (F [] ys) = get (F (reverse ys) []) 

你有它 - 攤銷O（ 1）以功能語言的FIFO隊列。

---

編輯： EFIE問及攤銷Ø在評論（1）性能。分攤恆定時間的論點非常簡單。

考慮的Ñ插入到一個空隊列的順序，接着Ñ檢索。插入花費時間n。在第一次檢索時，隊列的前面是空的，所以我們必須倒轉隊列的後面，這也需要時間n，再加上1來檢索元素。最後，下Ñ - 1檢索需要時間1中的每個，所以總時間是

Ñ + Ñ + 1 + Ñ - 1 = 3 Ñ

我們做了2 n電話總數，所以攤銷時間是3 n/2 n = 3/2，這是O（1）。無論對ins和get的調用是如何交錯的 - 在兩個調用中，每個元素都被調用一次，移動一次並且被拒絕一次，相同的論證仍然有效。

Answer 2

取決於你想要的操作。 queuelike和dequeue包具有隊列的類型類。