lens-4.13: Lenses, Folds and Traversals

Copyright | (C) 2012-15 Edward Kmett
License | BSD-style (see the file LICENSE)
Maintainer | Edward Kmett <ekmett@gmail.com>
Stability | experimental
Portability | non-portable
Safe Haskell | None
Language | Haskell98

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 Source

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

Constructors

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

Instances

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

size :: Deque a -> Int Source

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

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

fromList :: [a] -> Deque a Source

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

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

null :: Deque a -> Bool Source

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

    >>> null empty
    True

    >>> null (singleton 1)
    False

singleton :: a -> Deque a Source

O(1). Generate a singleton `Deque`

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