dequeue-0.1.7: A typeclass and an implementation for double-ended queues.

Copyright(c) Henry Bucklow 2009-2010
LicenseBSD3
Maintainer[email protected]
Stabilityprovisional
Portabilityportable
Safe HaskellSafe
LanguageHaskell98

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.

Synopsis

The Dequeue type class.

class Foldable q => Dequeue q where Source

A typeclass for double-ended queues.

Methods

empty :: q a Source

Generates an empty queue.

null :: q a -> Bool Source

Returns True if this queue is empty.

first :: q a -> Maybe a Source

Returns the item on the front of the queue.

last :: q a -> Maybe a Source

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.

fromList :: [a] -> q a Source

Converts a list into a queue.

Instances

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

Instances

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.