Deque

A Deque (double-ended queue) in Elm.

A deque is a data type for which elements can be efficiently added or removed from either the front or the back.

Internally, this is a head-tail linked list, modeled after this deque in Haskell which in turn is based on Chris Okasaki's Purely Functional Data Structures. A head-tail linked list is based on two lists: one for the head and one for the tail. This means that pop and push on either side are operations on the front portion of an elm list, which is very efficient (O(n)).

The deque rebalances (moves elements from the front to the rear or vice versa) when either one is 4 times as large as the other. This is a costly operation and therefore used as little as possible.

It is possible to set a maximum number of elements for the deque. The default is an unlimited size. When an item is pushed onto a full deque, an item is popped (and discarded) at the other end.

#Type and Constructors

type Deque a

The deque datatype

Deque equality with (==) is unreliable (equivalent deques can have a different distribution of elements between the back and the front) and should not be used.

#Build

empty : Deque a

Create an empty deque.

singleton : a -> Deque a

Create a deque with one element.

pushFront : a -> Deque a -> Deque a

Add an element to the front of the deque.

pushBack : a -> Deque a -> Deque a

Add an element to the back of the deque.

#Lists

fromList : List a -> Deque a

Create a deque from a list.

toList : Deque a -> List a

Convert a deque to a list.

#Bound

getMaxSize : Deque a -> Maybe Int

Get the maximum number of elements this deque can hold. A value of Nothing means the deque can hold an unlimited number of items (which is the default).

setMaxSize : Maybe Int -> Deque a -> Deque a

Sets a bound to the number of elements the deque can hold. a maxSize of Nothing means the deque's size is unbound, Just a value bounds the deque's size at that value.

If the deque is larger than the bound, items are dropped from the back.

Deque.fromList [0..9]
    |> setMaxSize (Just 5)
    -- toList would give [ 0, 1, 2, 3, 4 ]
    |> pushFront 42
    -- toList would give [ 42, 0, 1, 2, 3 ]
    |> pushBack -1
    -- toList would give [ 0, 1, 2, 3, -1 ]
    |> setMaxSize Nothing
    |> pushFront 73
    -- toList would give [ 73, 0, 1, 2, 3 -1 ]

#Query

isEmpty : Deque a -> Bool

Determine if a deque is empty.

member : a -> Deque a -> Bool

Figure out whether a deque contains a value.

first : Deque a -> Maybe a

Extract the first element of a deque

last : Deque a -> Maybe a

Extract the last element of a deque.

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

Gives Maybe the first element, and the deque without the first element. If there are no elements, the empty deque is returned.

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

Gives Maybe the last element, and the deque without the last element. If there are no elements, the empty deque is returned.

takeFront : Int -> Deque a -> List a

Take the first n members of a deque.

Deque.fromList [2..10]
    |> Deque.takeBack 3
    -- == [ 2, 3, 4 ]

takeBack : Int -> Deque a -> List a

Take the last n members of a deque.

Deque.fromList [2..10]
    |> Deque.takeBack 3
    -- == [ 10, 9, 8 ]

#Transform

Simple transform functions. To use more complex functions, like map2 or concat, just convert the deque to a list, apply the operation and convert back.

map : (a -> b) -> Deque a -> Deque b

Apply a function to all elements in a deque.

filter : (a -> Bool) -> Deque a -> Deque a

Keep an element when it satisfies a predicate.

foldl : (a -> b -> b) -> b -> Deque a -> b

Fold over the deque from left to right (highest priority to lowest priority).

foldr : (a -> b -> b) -> b -> Deque a -> b

Fold over the deque from right to left (lowest priority to highest priority).

partition : (a -> Bool) -> Deque a -> ( Deque a, Deque a )

Partition a deque according to a predicate. The first deque contains all elements that satisfy the predicate, and the second contains the rest.

Modules

Deque

folkertdev/elm-deque/1.0.0

Deque

Modules