Portability | portable |
---|---|

Stability | provisional |

Maintainer | henry@elsie.org.uk |

- The
`Dequeue`

type class. - QuickCheck properties for
`Dequeue`

instances - Banker's Dequeues
- QuickCheck properties for
`BankersDequeue`

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.

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.

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

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.