1 files changed, 44 insertions, 0 deletions
diff --git a/Haskell-book/28/DifferenceList/src/Data/Queue.hs b/Haskell-book/28/DifferenceList/src/Data/Queue.hs
new file mode 100644
index 0000000..68d1e1f
--- /dev/null
+++ b/Haskell-book/28/DifferenceList/src/Data/Queue.hs
@@ -0,0 +1,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.