ContentsIndex
Queue
Portability portable
Stability provisional
Maintainer daan@cs.uu.nl
Contents
Queue type
Operators
Query
Construction
Filter
Fold
Conversion
List
Description

An efficient implementation of queues (FIFO buffers). Based on:

  • Chris Okasaki, "Simple and Efficient Purely Functional Queues and Deques", Journal of Functional Programming 5(4):583-592, October 1995.

Synopsis
data Queue a
(<>) :: Queue a -> Queue a -> Queue a
isEmpty :: Queue a -> Bool
length :: Queue a -> Int
head :: Queue a -> a
tail :: Queue a -> Queue a
front :: Queue a -> Maybe (a, Queue a)
empty :: Queue a
single :: a -> Queue a
insert :: a -> Queue a -> Queue a
append :: Queue a -> Queue a -> Queue a
filter :: (a -> Bool) -> Queue a -> Queue a
partition :: (a -> Bool) -> Queue a -> (Queue a, Queue a)
foldL :: (b -> a -> b) -> b -> Queue a -> b
foldR :: (a -> b -> b) -> b -> Queue a -> b
elems :: Queue a -> [a]
toList :: Queue a -> [a]
fromList :: [a] -> Queue a
Queue type
data Queue a
Instances
(Eq a) => Eq (Queue a)
(Show a) => Show (Queue a)
Operators
(<>) :: Queue a -> Queue a -> Queue a
O(n). Append two queues, see append.
Query
isEmpty :: Queue a -> Bool
O(1). Is the queue empty?
length :: Queue a -> Int
O(n). The number of elements in the queue.
head :: Queue a -> a
O(1). The element in front of the queue. Raises an error when the queue is empty.
tail :: Queue a -> Queue a
O(1). The tail of the queue. Raises an error when the queue is empty.
front :: Queue a -> Maybe (a, Queue a)
O(1). The head and tail of the queue.
Construction
empty :: Queue a
O(1). The empty queue.
single :: a -> Queue a
O(1). A queue of one element.
insert :: a -> Queue a -> Queue a
O(1). Insert an element at the back of a queue.
append :: Queue a -> Queue a -> Queue a
O(n). Append two queues.
Filter
filter :: (a -> Bool) -> Queue a -> Queue a
O(n). Filter elements according to some predicate.
partition :: (a -> Bool) -> Queue a -> (Queue a, Queue a)
O(n). Partition the elements according to some predicate.
Fold
foldL :: (b -> a -> b) -> b -> Queue a -> b
O(n). Fold over the elements from left to right (ie. head to tail).
foldR :: (a -> b -> b) -> b -> Queue a -> b
O(n). Fold over the elements from right to left (ie. tail to head).
Conversion
elems :: Queue a -> [a]
O(n). The elements of a queue.
List
toList :: Queue a -> [a]
O(n). Convert to a list.
fromList :: [a] -> Queue a
O(n). Convert from a list.
Produced by Haddock version 0.4