2

これは、FIFO キューでの私の試みです。

type Queue a = [a] -> [a]

empty :: Queue a
empty = id

remove :: Int -> Queue a -> ([a], Queue a)
remove n queue = (take n (queue []), (\x -> drop n (queue x)));

add :: [a] -> Queue a -> Queue a
add elems queue = (\x -> queue (elems ++ x))

empty空のキューを作成し、キューremoveの最初のn要素を取り、キューの残りをタプルの 2 番目の要素として返し、addリストをキューに追加しelemsます。

O(1)これにより、時間内に 1 要素、時間内に n 要素が追加/削除されO(n)ますか?

4

2 に答える 2

6

あなたが効果的に実装したものは、差分リストに相当します。(見てください: dlist。)

差分リストを使用すると安価に追加できますが、残念ながら削除には直線的な時間がかかります。コードを少し書き直すと、より明確になります。

type Queue a = [a] -> [a]

empty :: Queue a
empty = id

toList :: Queue a -> [a]
toList q = q []

fromList :: [a] -> Queue a
fromList = (++)

remove :: Int -> Queue a -> ([a], Queue a)
remove n q = (xs, fromList ys)
  where
    (xs, ys) = splitAt n (toList q)

add :: [a] -> Queue a -> Queue a
add xs q = (++ xs) . q

リストとの間の変換を、コードよりも少し明示的に行ったことに注意してください。削除コードのコアが と で囲まれていることがはっきりとわかりtoListますfromList。

于 2012-07-13T13:49:03.167 に答える
4

さて、あなたの質問を多少回避しますが、FIFO キューの古典的な純粋に機能的な実装は、「前」用と「後」用のリストのペアです。要素をバック リストのヘッドとして追加してキューに入れ、フロント リストのヘッドを取得してデキューします。フロント リストが空の場合は、バック リストを逆にして、それを空のフロント リストと交換することにより、キューを「ローテーション」します。コード内:

import Control.Monad
import Data.List
import Data.Maybe

data FIFO a = FIFO [a] [a]
              deriving Show

empty :: FIFO a
empty = FIFO [] []

isEmpty :: FIFO a -> Bool
isEmpty (FIFO [] []) = True
isEmpty _ = False

enqueue :: a -> FIFO a -> FIFO a
enqueue x (FIFO front back) = FIFO front (x:back)

-- | Remove the head off the queue.  My type's different from yours
-- because I use Maybe to handle the case where somebody tries to
-- dequeue off an empty FIFO.
dequeue :: FIFO a -> Maybe (a, FIFO a)
dequeue queue = case queue of
                  FIFO [] [] -> Nothing
                  FIFO (x:f) b -> Just (x, FIFO f b)
                  otherwise -> dequeue (rotate queue)
    where rotate (FIFO [] back) = FIFO (reverse back) []


-- | Elements exit the queue in the order they appear in the list.
fromList :: [a] -> FIFO a
fromList xs = FIFO xs []

-- | Elements appear in the result list in the order they exit the queue.
toList :: FIFO a -> [a]
toList = unfoldr dequeue

それが古典的な実装です。これで、操作は次のように記述できます。

-- | Enqueue multiple elements.  Elements exit the queue in the order
-- they appear in xs.
add :: [a] -> FIFO a -> FIFO a
add xs q = foldl' (flip enqueue) q xs

で記述するremoveには、 の結果dequeueからこれらの中間 FIFO をすべて処理する必要があります。これを行う 1 つの方法は、モナドを使用することです。(a, FIFO a)dequeueState

import Control.Monad.State

-- | Remove n elements from the queue.  My result type is different
-- from yours, again, because I handle the empty FIFO case.  If you
-- try to remove too many elements, you get a bunch of Nothings at
-- the end of your list.
remove :: Int -> FIFO a -> ([Maybe a], FIFO a)
remove n q = runState (removeM n) q

-- | State monad action to dequeue n elements from the state queue.
removeM :: Int -> State (FIFO a) [Maybe a]
removeM n = replicateM n dequeueM

-- | State monad action to dequeue an element from the state queue.
dequeueM :: State (FIFO a) (Maybe a)
dequeueM = do q <- get
              case dequeue q of
                Just (x, q') -> put q' >> return (Just x)
                Nothing -> return Nothing
于 2012-07-14T07:50:40.693 に答える