okasaki

commit a57701272ff8107d92464a4e5486d25b1afc385b
parent 39b0920358cd4049bc234bd28f69aff78e0432ac
Author: Jared Tobin <jared@jtobin.ca>
Date:   Sun, 23 Nov 2014 21:48:24 +1300

Queue work.

Diffstat:
A
Queue.hs
 | 
34
++++++++++++++++++++++++++++++++++

1 file changed, 34 insertions(+), 0 deletions(-)
diff --git a/Queue.hs b/Queue.hs
@@ -0,0 +1,34 @@
+{-# OPTIONS_GHC -Wall #-}
+
+module Queue where
+
+import Prelude hiding (head, tail, reverse)
+import qualified Prelude as Prelude (reverse)
+
+data Queue a = Queue {
+    forward :: [a]
+  , reverse :: [a]
+  } deriving Show
+
+head :: Queue a -> Maybe a
+head (Queue [] _)    = Nothing
+head (Queue (h:_) _) = Just h
+
+empty :: Queue a
+empty = Queue [] []
+
+isEmpty :: Queue a -> Bool
+isEmpty (Queue [] []) = True
+isEmpty _ = False
+
+checkf :: Queue a -> Queue a
+checkf (Queue [] r) = Queue (Prelude.reverse r) []
+checkf q = q
+
+snoc :: Queue a -> a -> Queue a
+snoc (Queue f r) e = checkf (Queue f (e : r))
+
+tail :: Queue a -> Queue a
+tail (Queue (_:t) r) = checkf (Queue t r)
+tail q = q
+