6

FIFOキューを記述するHaskell型クラスを書いた人はいますか（または型クラスの組み合わせがありますか）。

Data.Collection.Sequenceは強すぎるように見えますが、一方でData.Collection.Unfoldableは弱すぎるようです（順序が定義されていないため）。

他人の仕事をやり直したくなかっただけです。

4

2 に答える 2

6

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 2）の時間がかかります。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（n）時間かかりますが、要素ごとに1回だけ実行する必要があるため、get操作の平均はO（1）時間になります。

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

関数型言語で償却されたO（1）FIFOキューがあります。

編集： Efieは、コ​​メントで償却されたO（1）のパフォーマンスについて質問しました。償却定数時間の議論は非常に単純です。

空のキューへのn回の挿入と、それに続くn回の取得のシーケンスについて考えてみます。挿入には時間nかかります。最初の取得では、キューの前部が空であるため、キューの後ろを逆にする必要があります。これにも、要素を取得するために時間nと1がかかります。最後に、次のn -1回の取得にはそれぞれ1回の時間がかかるため、合計時間は次のようになります。

n + n + 1 + n --1 = 3 n

合計で2n回の呼び出しを行ったため、償却時間は3 n / 2 n = 3/2、つまりO（1）になります。同じ引数は、呼び出しがどのようにインターリーブされinsても機能しますget。2つの呼び出しでは、各要素が1回consされ、1回移動され、1回de-consされます。

于 2012-07-12T08:37:44.927 に答える
2

実行したい操作によって異なります。queuelikeパッケージとdequeueパッケージには、キューの型クラスがあります。

于 2012-07-12T00:12:15.770 に答える