Dequeue.hs (1630B)
1 {-# OPTIONS_GHC -Wall #-} 2 3 module Dequeue where 4 5 import Queue (Queue(..)) 6 import qualified Queue 7 import Prelude hiding (head, tail, reverse, last, init) 8 import qualified Prelude (reverse) 9 10 -- exercise 5.1a (double-ended queue) 11 newtype Dequeue a = Dequeue { dequeue :: Queue a } deriving Show 12 13 head :: Dequeue a -> Maybe a 14 head (Dequeue q) = Queue.head q 15 16 empty :: Dequeue a 17 empty = Dequeue Queue.empty 18 19 isEmpty :: Dequeue a -> Bool 20 isEmpty (Dequeue q) = Queue.isEmpty q 21 22 checkSym :: Dequeue a -> Dequeue a 23 checkSym (Dequeue q) = Dequeue (checkSymQ q) 24 25 checkSymQ :: Queue a -> Queue a 26 checkSymQ (Queue [] [r]) = Queue [r] [] 27 checkSymQ (Queue [] r) = let (a, b) = splitter r in Queue (Prelude.reverse a) b 28 checkSymQ (Queue f []) = let (a, b) = splitter f in Queue b (Prelude.reverse a) 29 checkSymQ e = e 30 31 splitter :: [a] -> ([a], [a]) 32 splitter r = 33 let m = length r 34 n = let l = m `quot` 2 in if even m then l else succ l 35 in (drop n r, take n r) 36 37 snoc :: Dequeue a -> a -> Dequeue a 38 snoc (Dequeue (Queue f r)) e = Dequeue $ checkSymQ (Queue f (e : r)) 39 40 cons :: Dequeue a -> a -> Dequeue a 41 cons (Dequeue (Queue f r)) e = Dequeue $ checkSymQ (Queue (e : f) r) 42 43 tail :: Dequeue a -> Dequeue a 44 tail (Dequeue (Queue (_:t) r)) = Dequeue $ checkSymQ (Queue t r) 45 tail deq = deq 46 47 last :: Dequeue a -> Maybe a 48 last (Dequeue (Queue _ (l:_))) = Just l 49 last (Dequeue (Queue (l:_) [])) = Just l 50 last (Dequeue (Queue [] [])) = Nothing 51 52 init :: Dequeue a -> Dequeue a 53 init (Dequeue (Queue f (_:t))) = Dequeue $ checkSymQ (Queue f t) 54 init (Dequeue (Queue [_] [])) = empty 55 init deq = deq 56 57 test :: Dequeue Int 58 test = Dequeue Queue.test 59