blob: 68d1e1fcaf96431140e5b713c36ac9e9933d9a38 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
module Data.Queue
( Queue(..)
, empty
, isEmpty
, push
, pop
) where
-- From Okasaki's Purely Functional Data Structures
data Queue a =
Queue { enqueue :: [a]
, dequeue :: [a]
} deriving (Eq, Show)
isEmpty :: Queue a -> Bool
isEmpty xs = length (enqueue xs) == 0
&& length (dequeue xs) == 0
empty :: Queue a
empty = Queue [] []
-- adds an item
push :: a -> Queue a -> Queue a
push x xs = Queue { enqueue = x : (enqueue xs)
, dequeue = dequeue xs }
pop :: Queue a -> Maybe (a, Queue a)
pop xs = popFromLists (enqueue xs) (dequeue xs)
where popFromLists [] [] = Nothing
popFromLists en (d:de) = Just (d, Queue en de)
popFromLists en [] = popFromLists [] (reverse en)
-- We’re going to give you less code this time, but your task is to
-- implement the above and write a benchmark comparing it against
-- performing alternating pushes and pops from a queue based on a
-- single list. Alternating so that you can’t take advantage of reversing
-- the list after a long series of pushes in order to perform a long series
-- of pops efficiently.
--
-- Don’t forget to handle the case where the dequeue is empty and
-- you need to shift items from the enqueue to the dequeue. You need
-- to do so without violating “first come, first served”.
-- Lastly, benchmark it against Sequence. Come up with a variety of
-- tests. Add additional operations for your Queue type if you want.
|
