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元素并将队列的其余部分作为元组的第二个元素返回，add并将列表添加elems到队列中。

这会及时添加/删除 1 个元素O(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，您需要(a, FIFO a)从dequeue. 一种方法是使用Statemonad：

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 回答