module Fifo where

-- A not-too inefficient implementation of queues in Haskell
--  using two "back-to-back" lists

newtype Fifo a = Fifo ([a],[a]) deriving (Show,Eq)

new :: Fifo a
new = Fifo ([],[])

enqueue :: a -> Fifo a -> Fifo a
enqueue a (Fifo (front , back)) = Fifo (front , a : back)

dequeue :: Fifo a -> Maybe (a, Fifo a)
dequeue (Fifo ([] ,[]))  = Nothing
dequeue (Fifo (f : fs,bs)) = Just (f, Fifo (fs,bs))
dequeue (Fifo ([], bs))  = dequeue (Fifo (reverse bs , []))

isEmpty :: Fifo a -> Bool
isEmpty (Fifo (fs,bs)) = null fs && null bs