| Portability | portable |
|---|---|
| Stability | provisional |
| Maintainer | [email protected] |
Data.Dequeue
Contents
Description
A typeclass for double-ended queues, and an implementation of Banker's Dequeues, as described in Chris Okasaki's Purely Functional Data Structures.
- class Dequeue q where
- prop_pushpop_front :: (Dequeue q, Eq a, Eq (q a)) => q a -> a -> Bool
- prop_pushpop_back :: (Dequeue q, Eq a, Eq (q a)) => q a -> a -> Bool
- prop_push_front :: (Dequeue q, Eq a) => q a -> a -> Bool
- prop_push_back :: (Dequeue q, Eq a) => q a -> a -> Bool
- prop_takeFront :: (Dequeue q, Eq a) => q a -> [a] -> Bool
- prop_takeBack :: (Dequeue q, Eq a) => q a -> [a] -> Bool
- prop_length_toList :: (Dequeue q, Foldable q) => q a -> Bool
- prop_fromList_toList :: (Dequeue q, Foldable q, Eq (q a)) => q a -> Bool
- data BankersDequeue a
- prop_pushpop_front_bq :: BankersDequeue Int -> Int -> Bool
- prop_pushpop_back_bq :: BankersDequeue Int -> Int -> Bool
- prop_push_front_bq :: BankersDequeue Int -> Int -> Bool
- prop_push_back_bq :: BankersDequeue Int -> Int -> Bool
- prop_takeFront_bq :: BankersDequeue Int -> [Int] -> Bool
- prop_takeBack_bq :: BankersDequeue Int -> [Int] -> Bool
- prop_length_toList_bq :: BankersDequeue Int -> Bool
- prop_fromList_toList_bq :: BankersDequeue Int -> Bool
- prop_push_front_bq_balance :: BankersDequeue Int -> Int -> Bool
- prop_push_back_bq_balance :: BankersDequeue Int -> Int -> Bool
- prop_pop_front_bq_balance :: BankersDequeue Int -> Int -> Bool
- prop_pop_back_bq_balance :: BankersDequeue Int -> Int -> Bool
The Dequeue type class.
A typeclass for double-ended queues.
Methods
Generates an empty queue.
Returns True if this queue is empty.
Returns the number of elements in this queue.
Returns the item on the front of the queue.
Returns the item on the end of the queue.
takeFront :: Int -> q a -> [a]Source
Returns the first n items from the front of the queue, in the order they would be popped.
takeBack :: Int -> q a -> [a]Source
Returns the last n items from the end of the queue, in the order they would be popped.
pushFront :: q a -> a -> q aSource
Pushes an item onto the front of the queue.
popFront :: q a -> (Maybe a, q a)Source
Pops an item from the front of the queue.
pushBack :: q a -> a -> q aSource
Pushes an item onto the back of the queue.
popBack :: q a -> (Maybe a, q a)Source
Pops an item from the back of the queue.
Converts a list into a queue.
Instances
QuickCheck properties for Dequeue instances
prop_pushpop_front :: (Dequeue q, Eq a, Eq (q a)) => q a -> a -> BoolSource
Validates that if you push, then pop, the front of the queue, you get the same queue.
prop_pushpop_back :: (Dequeue q, Eq a, Eq (q a)) => q a -> a -> BoolSource
Validates that if you push, then pop, the back of the queue, you get the same queue.
prop_push_front :: (Dequeue q, Eq a) => q a -> a -> BoolSource
Validates that first returns the last pushFront'd element.
prop_push_back :: (Dequeue q, Eq a) => q a -> a -> BoolSource
Validates that last returns the last pushBack'd element.
prop_takeFront :: (Dequeue q, Eq a) => q a -> [a] -> BoolSource
Validates that the last n pushed elements are returned by takeFront.
prop_takeBack :: (Dequeue q, Eq a) => q a -> [a] -> BoolSource
Validates that the last n pushed elements are returned by takeBack.
prop_length_toList :: (Dequeue q, Foldable q) => q a -> BoolSource
Validates that the length of a queue is the same as the length of the list generated from the queue.
prop_fromList_toList :: (Dequeue q, Foldable q, Eq (q a)) => q a -> BoolSource
Validates that fromList . toList is the identity.
Banker's Dequeues
data BankersDequeue a Source
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):
Instances
| Functor BankersDequeue | |
| Foldable BankersDequeue | |
| Dequeue BankersDequeue | |
| Eq a => Eq (BankersDequeue a) | |
| Show a => Show (BankersDequeue a) | |
| Arbitrary a => Arbitrary (BankersDequeue a) |
QuickCheck properties for BankersDequeue
prop_pushpop_front_bq :: BankersDequeue Int -> Int -> BoolSource
Validates that if you push, then pop, the front of a BankersQueue,
you get the same queue.
prop_pushpop_back_bq :: BankersDequeue Int -> Int -> BoolSource
Validates that if you push, then pop, the back of a BankersDequeue,
you get the same queue.
prop_push_front_bq :: BankersDequeue Int -> Int -> BoolSource
Validates that first returns the last pushFront'd element.
prop_push_back_bq :: BankersDequeue Int -> Int -> BoolSource
Validates that last returns the last pushBack'd element.
prop_takeFront_bq :: BankersDequeue Int -> [Int] -> BoolSource
Validates that the last n pushed elements are returned by takeFront.
prop_takeBack_bq :: BankersDequeue Int -> [Int] -> BoolSource
Validates that the last n pushed elements are returned by takeBack.
prop_length_toList_bq :: BankersDequeue Int -> BoolSource
Validates that the length of a BankersDequeue is the same as the length
of the list generated from the queue.
prop_fromList_toList_bq :: BankersDequeue Int -> BoolSource
Validates that fromList . toList is the identity for a BankersDequeue.
prop_push_front_bq_balance :: BankersDequeue Int -> Int -> BoolSource
Validates that a BankersDequeue remains balanced despite repeated
pushes to the front.
prop_push_back_bq_balance :: BankersDequeue Int -> Int -> BoolSource
Validates that a BankersDequeue remains balanced despite repeated
pushes to the back.
prop_pop_front_bq_balance :: BankersDequeue Int -> Int -> BoolSource
Validates that a BankersDequeue remains balanced despite repeated
pops from the front.
prop_pop_back_bq_balance :: BankersDequeue Int -> Int -> BoolSource
Validates that a BankersDequeue remains balanced despite repeated
pops from the back.