-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A typeclass and an implementation for double-ended queues.
--
@package dequeue
@version 0.1.12
-- | A newtype used entirely for its derived Read and Show
-- instances. These are then used by showDequeue and
-- readDequeue to make writing Read and Show
-- instances for Dequeues easier.
module Data.Dequeue.Show
newtype Dequeue a
Dequeue :: [a] -> Dequeue a
instance Read a => Read (Dequeue a)
instance Show a => Show (Dequeue a)
-- | A typeclass for double-ended queues, and an implementation of Banker's
-- Dequeues, as described in Chris Okasaki's Purely Functional Data
-- Structures.
module Data.Dequeue
-- | A typeclass for double-ended queues.
class Foldable q => Dequeue q
empty :: Dequeue q => q a
null :: Dequeue q => q a -> Bool
length :: Dequeue q => q a -> Int
first :: Dequeue q => q a -> Maybe a
last :: Dequeue q => q a -> Maybe a
takeFront :: Dequeue q => Int -> q a -> [a]
takeBack :: Dequeue q => Int -> q a -> [a]
pushFront :: Dequeue q => q a -> a -> q a
popFront :: Dequeue q => q a -> Maybe (a, q a)
pushBack :: Dequeue q => q a -> a -> q a
popBack :: Dequeue q => q a -> Maybe (a, q a)
fromList :: Dequeue q => [a] -> q a
-- | Support to make generating Show instances for Dequeues
-- easier. Use as follows:
--
--
-- instance Show a => Show (MyDequeue a) where
-- show q = showDequeue q
--
--
--
-- The resulting Show instance will be portable between
-- Deqeue instances, and will not expose the details of how your
-- Dequeue instance is constructed.
showDequeue :: (Foldable q, Dequeue q, Show a) => q a -> String
-- | Support to make generating Read instances for Dequeues
-- easier. Use as follows:
--
--
-- instance Read a => Read (MyDequeue a) where
-- readsPrec i = readDequeue $ readsPrec i
--
--
--
-- The resulting Read instance will be portable between
-- Deqeue instances, and will not expose the details of how your
-- Dequeue instance is constructed.
readDequeue :: (Dequeue q, Read a) => ReadS (Dequeue a) -> ReadS (q a)
-- | Validates that if you push, then pop, the front of the queue, you get
-- the same queue.
prop_pushpop_front :: (Dequeue q, Eq a, Eq (q a)) => q a -> a -> Bool
-- | Validates that if you push, then pop, the back of the queue, you get
-- the same queue.
prop_pushpop_back :: (Dequeue q, Eq a, Eq (q a)) => q a -> a -> Bool
-- | Validates that first returns the last pushFront'd
-- element.
prop_push_front :: (Dequeue q, Eq a) => q a -> a -> Bool
-- | Validates that last returns the last pushBack'd
-- element.
prop_push_back :: (Dequeue q, Eq a) => q a -> a -> Bool
-- | Validates that the last n pushed elements are returned by
-- takeFront.
prop_takeFront :: (Dequeue q, Eq a) => q a -> [a] -> Bool
-- | Validates that the last n pushed elements are returned by
-- takeBack.
prop_takeBack :: (Dequeue q, Eq a) => q a -> [a] -> Bool
-- | Validates that the length of a queue is the same as the length of the
-- list generated from the queue.
prop_length_toList :: (Dequeue q, Foldable q) => q a -> Bool
-- | Validates that fromList . toList is the identity.
prop_fromList_toList :: (Dequeue q, Foldable q, Eq (q a)) => q a -> Bool
-- | An implementation of Banker's Dequeues, as described in Chris
-- Okasaki's Purely Functional Data Structures. The functions for the
-- Dequeue instance have the following complexities (where n is
-- the length of the queue):
--
--
data BankersDequeue a
-- | Validates that if you push, then pop, the front of a
-- BankersQueue, you get the same queue.
prop_pushpop_front_bq :: BankersDequeue Int -> Int -> Bool
-- | Validates that if you push, then pop, the back of a
-- BankersDequeue, you get the same queue.
prop_pushpop_back_bq :: BankersDequeue Int -> Int -> Bool
-- | Validates that first returns the last pushFront'd
-- element.
prop_push_front_bq :: BankersDequeue Int -> Int -> Bool
-- | Validates that last returns the last pushBack'd
-- element.
prop_push_back_bq :: BankersDequeue Int -> Int -> Bool
-- | Validates that the last n pushed elements are returned by
-- takeFront.
prop_takeFront_bq :: BankersDequeue Int -> [Int] -> Bool
-- | Validates that the last n pushed elements are returned by
-- takeBack.
prop_takeBack_bq :: BankersDequeue Int -> [Int] -> Bool
-- | Validates that the length of a BankersDequeue is the same as
-- the length of the list generated from the queue.
prop_length_toList_bq :: BankersDequeue Int -> Bool
-- | Validates that fromList . toList is the identity for a
-- BankersDequeue.
prop_fromList_toList_bq :: BankersDequeue Int -> Bool
-- | Validates that a BankersDequeue remains balanced despite
-- repeated pushes to the front.
prop_push_front_bq_balance :: BankersDequeue Int -> Int -> Property
-- | Validates that a BankersDequeue remains balanced despite
-- repeated pushes to the back.
prop_push_back_bq_balance :: BankersDequeue Int -> Int -> Property
-- | Validates that a BankersDequeue remains balanced despite
-- repeated pops from the front.
prop_pop_front_bq_balance :: BankersDequeue Int -> Int -> Property
-- | Validates that a BankersDequeue remains balanced despite
-- repeated pops from the back.
prop_pop_back_bq_balance :: BankersDequeue Int -> Int -> Property
-- | Validates that a BankersDequeue has read and show instances
-- that are the inverse of each other.
prop_read_show_bq :: BankersDequeue Int -> Bool
instance Read a => Read (BankersDequeue a)
instance Show a => Show (BankersDequeue a)
instance Eq a => Eq (BankersDequeue a)
instance Arbitrary a => Arbitrary (BankersDequeue a)
instance Dequeue BankersDequeue
instance Foldable BankersDequeue
instance Functor BankersDequeue