Copyright | (c) Henry Bucklow 2009-2010 |
---|---|

License | BSD3 |

Maintainer | henry@elsie.org.uk |

Stability | provisional |

Portability | portable |

Safe Haskell | Safe-Inferred |

Language | Haskell98 |

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

- class Foldable q => Dequeue q where
- showDequeue :: (Foldable q, Dequeue q, Show a) => q a -> String
- readDequeue :: (Dequeue q, Read a) => ReadS (Dequeue a) -> ReadS (q a)
- 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 -> Property
- prop_push_back_bq_balance :: BankersDequeue Int -> Int -> Property
- prop_pop_front_bq_balance :: BankersDequeue Int -> Int -> Property
- prop_pop_back_bq_balance :: BankersDequeue Int -> Int -> Property
- prop_read_show_bq :: BankersDequeue Int -> Bool

# The `Dequeue`

type class.

class Foldable q => Dequeue q where Source

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.

first :: q a -> Maybe a Source

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

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

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.

# Support for `Read`

and `Show`

instances

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

Support to make generating `Read`

instances for `Dequeue`

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

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

Validates that a `BankersDequeue`

remains balanced despite repeated
pushes to the front.

prop_push_back_bq_balance :: BankersDequeue Int -> Int -> Property Source

Validates that a `BankersDequeue`

remains balanced despite repeated
pushes to the back.

prop_pop_front_bq_balance :: BankersDequeue Int -> Int -> Property Source

Validates that a `BankersDequeue`

remains balanced despite repeated
pops from the front.

prop_pop_back_bq_balance :: BankersDequeue Int -> Int -> Property 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.