lens-3.8.7.3: Lenses, Folds and Traversals

Portability | non-portable
Stability | experimental
Maintainer | Edward Kmett <ekmett@gmail.com>
Safe Haskell | Trustworthy

Control.Lens.Internal.Deque

Description

This module is designed to be imported qualified.

Synopsis

- data Deque a = BD !Int [a] !Int [a]
- size :: Deque a -> Int
- fromList :: [a] -> Deque a
- null :: Deque a -> Bool
- singleton :: a -> Deque a

# Documentation

data Deque a

A Banker's deque based on Chris Okasaki's "Purely Functional Data Structures"

Constructors

BD !Int [a] !Int [a] |

Instances

Monad Deque |
Functor Deque |
MonadPlus Deque |
Applicative Deque |
Foldable Deque |
Traversable Deque |
Alternative Deque |
Plus Deque |
Alt Deque |
Apply Deque |
Bind Deque |
TraversableWithIndex Int Deque |
FoldableWithIndex Int Deque |
FunctorWithIndex Int Deque |
(Choice p, Applicative f) => Snoc p f (Deque a) (Deque b) a b |
(Choice p, Applicative f) => Cons p f (Deque a) (Deque b) a b |
Eq a => Eq (Deque a) |
Ord a => Ord (Deque a) |
Show a => Show (Deque a) |
Monoid (Deque a) |
Semigroup (Deque a) |

size :: Deque a -> Int

O(1). Calculate the size of a `Deque`

    >>> size (fromList [1,4,6])
    3

fromList :: [a] -> Deque a

O(n) amortized. Construct a `Deque` from a list of values.

    >>> fromList [1,2]
    BD 1 [1] 1 [2]

null :: Deque a -> Bool

O(1). Determine of a `Deque` is `empty`.

    >>> null empty
    True

    >>> null (singleton 1)
    False

singleton :: a -> Deque a

O(1). Generate a singleton `Deque`

    >>> singleton 1
    BD 1 [1] 0 []