Data.Dequeue

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

The Dequeue type class.

class Foldable q => Dequeue q where

A typeclass for double-ended queues.

Methods

empty :: q a

Generates an empty queue.

null :: q a -> Bool

Returns True if this queue is empty.

length :: q a -> Int

Returns the number of elements in this queue.

first :: q a -> Maybe a

Returns the item on the front of the queue.

last :: q a -> Maybe a

Returns the item on the end of the queue.

takeFront :: Int -> q a -> [a]

Returns the first n items from the front of the queue, in the order they would be popped.

takeBack :: Int -> q a -> [a]

Returns the last n items from the end of the queue, in the order they would be popped.

pushFront :: q a -> a -> q a

Pushes an item onto the front of the queue.

popFront :: q a -> Maybe (a, q a)

Pops an item from the front of the queue.

pushBack :: q a -> a -> q a

Pushes an item onto the back of the queue.

popBack :: q a -> Maybe (a, q a)

Pops an item from the back of the queue.

fromList :: [a] -> q a

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

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)

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

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

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

Validates that first returns the last pushFront'd element.

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

Validates that last returns the last pushBack'd element.

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

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

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

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

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

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

Validates that fromList . toList is the identity.

Banker's Dequeues

data BankersDequeue a

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

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

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

Validates that first returns the last pushFront'd element.

prop_push_back_bq :: BankersDequeue Int -> Int -> Bool

Validates that last returns the last pushBack'd element.

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

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

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

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

prop_length_toList_bq :: BankersDequeue Int -> Bool

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

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

prop_push_front_bq_balance :: BankersDequeue Int -> Int -> Property

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

prop_push_back_bq_balance :: BankersDequeue Int -> Int -> Property

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

prop_pop_front_bq_balance :: BankersDequeue Int -> Int -> Property

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

prop_pop_back_bq_balance :: BankersDequeue Int -> Int -> Property

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

prop_read_show_bq :: BankersDequeue Int -> Bool

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