Portability	portable
Stability	provisional
Maintainer	henry@elsie.org.uk

Data.Dequeue

Contents

The Dequeue type class.
Support for Read and Show instances
QuickCheck properties for Dequeue instances
Banker's Dequeues
QuickCheck properties for BankersDequeue

Description

A typeclass for double-ended queues, and an implementation of Banker's Dequeues, as described in Chris Okasaki's Purely Functional Data Structures.

Synopsis

The `Dequeue` type class.

class Dequeue q whereSource

A typeclass for double-ended queues.

Methods

empty :: q aSource

Generates an empty queue.

null :: q a -> Bool Source

Returns True if this queue is empty.

length :: q a -> Int Source

Returns the number of elements in this queue.

first :: q a -> Maybe aSource

Returns the item on the front of the queue.

last :: q a -> Maybe aSource

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.

fromList :: [a] -> q aSource

Converts a list into a queue.

Instances

Dequeue BankersDequeue

Support for `Read` and `Show` instances

showDequeue :: (Foldable q, Dequeue q, Show a) => q a -> String Source

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.

readDequeue :: (Dequeue q, Read a) => ReadS (Dequeue a) -> ReadS (q a)Source

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.

QuickCheck properties for `Dequeue` instances

prop_pushpop_front :: (Dequeue q, Eq a, Eq (q a)) => q a -> a -> Bool Source

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 -> Bool Source

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 -> Bool Source

Validates that first returns the last pushFront'd element.

prop_push_back :: (Dequeue q, Eq a) => q a -> a -> Bool Source

Validates that last returns the last pushBack'd element.

prop_takeFront :: (Dequeue q, Eq a) => q a -> [a] -> Bool Source

Validates that the last n pushed elements are returned by takeFront.

prop_takeBack :: (Dequeue q, Eq a) => q a -> [a] -> Bool Source

Validates that the last n pushed elements are returned by takeBack.

prop_length_toList :: (Dequeue q, Foldable q) => q a -> Bool Source

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 -> Bool Source

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):

length: O(1)
first: O(1)
last: O(1)
takeFront: O(n)
takeBack: O(n)
pushFront: O(1) amortised
popFront: O(1) amortised
pushBack: O(1) amortised
popBack: O(1) amortised
fromList: O(n)

Instances

Functor BankersDequeue
Foldable BankersDequeue
Dequeue BankersDequeue
Eq a => Eq (BankersDequeue a)
Read a => Read (BankersDequeue a)
Show a => Show (BankersDequeue a)
Arbitrary a => Arbitrary (BankersDequeue a)

QuickCheck properties for `BankersDequeue`

prop_pushpop_front_bq :: BankersDequeue Int -> Int -> Bool Source

Validates that if you push, then pop, the front of a BankersQueue, you get the same queue.

prop_pushpop_back_bq :: BankersDequeue Int -> Int -> Bool Source

Validates that if you push, then pop, the back of a BankersDequeue, you get the same queue.

prop_push_front_bq :: BankersDequeue Int -> Int -> Bool Source

Validates that first returns the last pushFront'd element.

prop_push_back_bq :: BankersDequeue Int -> Int -> Bool Source

Validates that last returns the last pushBack'd element.

prop_takeFront_bq :: BankersDequeue Int -> [Int] -> Bool Source

Validates that the last n pushed elements are returned by takeFront.

prop_takeBack_bq :: BankersDequeue Int -> [Int] -> Bool Source

Validates that the last n pushed elements are returned by takeBack.

prop_length_toList_bq :: BankersDequeue Int -> Bool Source

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 -> Bool Source

Validates that fromList . toList is the identity for a BankersDequeue.

prop_push_front_bq_balance :: BankersDequeue Int -> Int -> Bool Source

Validates that a BankersDequeue remains balanced despite repeated pushes to the front.

prop_push_back_bq_balance :: BankersDequeue Int -> Int -> Bool Source

Validates that a BankersDequeue remains balanced despite repeated pushes to the back.

prop_pop_front_bq_balance :: BankersDequeue Int -> Int -> Bool Source

Validates that a BankersDequeue remains balanced despite repeated pops from the front.

prop_pop_back_bq_balance :: BankersDequeue Int -> Int -> Bool Source

Validates that a BankersDequeue remains balanced despite repeated pops from the back.

prop_read_show_bq :: BankersDequeue Int -> Bool Source

Validates that a BankersDequeue has read and show instances that are the inverse of each other.

The Dequeue type class.

Support for Read and Show instances

QuickCheck properties for Dequeue instances

Banker's Dequeues

QuickCheck properties for BankersDequeue

The `Dequeue` type class.

Support for `Read` and `Show` instances

QuickCheck properties for `Dequeue` instances

QuickCheck properties for `BankersDequeue`