1 -----------------------------------------------------------------------------
4 -- Copyright : (c) The University of Glasgow 2002
5 -- License : BSD-style (see the file libraries/base/LICENSE)
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : portable
11 -- Queues with constant time operations, from
12 -- /Simple and efficient purely functional queues and deques/,
13 -- by Chris Okasaki, /JFP/ 5(4):583-592, October 1995.
15 -----------------------------------------------------------------------------
19 -- * Primitive operations
20 -- | Each of these requires /O(1)/ time in the worst case.
21 emptyQueue, addToQueue, deQueue,
23 listToQueue, queueToList
30 -- | The type of FIFO queues.
31 data Queue a = Q [a] [a] [a]
33 -- Invariants for Q xs ys xs':
34 -- length xs = length ys + length xs'
35 -- xs' = drop (length ys) xs -- in fact, shared (except after fmap)
36 -- The queue then represents the list xs ++ reverse ys
38 instance Functor Queue where
39 fmap f (Q xs ys xs') = Q (map f xs) (map f ys) (map f xs')
40 -- The new xs' does not share the tail of the new xs, but it does
41 -- share the tail of the old xs, so it still forces the rotations.
42 -- Note that elements of xs' are ignored.
46 emptyQueue = Q [] [] []
48 -- | Add an element to the back of a queue.
49 addToQueue :: Queue a -> a -> Queue a
50 addToQueue (Q xs ys xs') y = makeQ xs (y:ys) xs'
52 -- | Attempt to extract the front element from a queue.
53 -- If the queue is empty, 'Nothing',
54 -- otherwise the first element paired with the remainder of the queue.
55 deQueue :: Queue a -> Maybe (a, Queue a)
56 deQueue (Q [] _ _) = Nothing
57 deQueue (Q (x:xs) ys xs') = Just (x, makeQ xs ys xs')
60 -- length ys <= length xs + 1
61 -- xs' = drop (length ys - 1) xs
62 -- construct a queue respecting the invariant.
63 makeQ :: [a] -> [a] -> [a] -> Queue a
64 makeQ xs ys [] = listToQueue (rotate xs ys [])
65 makeQ xs ys (_:xs') = Q xs ys xs'
67 -- Assuming length ys = length xs + 1,
68 -- rotate xs ys zs = xs ++ reverse ys ++ zs
69 rotate :: [a] -> [a] -> [a] -> [a]
70 rotate [] (y:_) zs = y : zs -- the _ here must be []
71 rotate (x:xs) (y:ys) zs = x : rotate xs ys (y:zs)
73 -- | A queue with the same elements as the list.
74 listToQueue :: [a] -> Queue a
75 listToQueue xs = Q xs [] xs
77 -- | The elements of a queue, front first.
78 queueToList :: Queue a -> [a]
79 queueToList (Q xs ys _) = xs ++ reverse ys