Add remaining haskell book exercises

2 files changed, 84 insertions, 0 deletions

diff --git a/Haskell-book/28/DifferenceList/src/Data/DList.hs b/Haskell-book/28/DifferenceList/src/Data/DList.hs
new file mode 100644
index 0000000..12d3a53
--- /dev/null
+++ b/Haskell-book/28/DifferenceList/src/Data/DList.hs
@@ -0,0 +1,40 @@
+module Data.DList
+    ( DList(..)
+    , empty
+    , singleton
+    , toList
+    , cons
+    , snoc
+    , append
+    ) where
+
+newtype DList a = DL { unDL :: [a] -> [a] }
+
+empty :: DList a
+empty = DL ([] ++)
+{-# INLINE empty #-}
+
+singleton :: a -> DList a
+singleton x = DL ([x] ++)
+{-# INLINE singleton #-}
+
+toList :: DList a -> [a]
+toList xsf = unDL xsf []
+{-# INLINE toList #-}
+
+-- Prepend a single element to a dlist.
+infixr `cons`
+cons :: a -> DList a -> DList a
+cons x xs = DL ((x:) . unDL xs)
+{-# INLINE cons #-}
+
+-- Append a single element to a dlist.
+infixl `snoc`
+snoc :: DList a -> a -> DList a
+snoc xs x = append xs $ singleton x
+{-# INLINE snoc #-}
+
+-- Append dlists.
+append :: DList a -> DList a -> DList a
+append xsf ysf = DL $ (unDL xsf) . (unDL ysf)
+{-# INLINE append #-}
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.