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(1)).

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.

For a deque with a limited size, see BoundedDeque.

Type

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.

append : Deque a -> Deque a -> Deque a

Concatenate two deques into one.

This function is written in pipeline style, so

firstDeque
    |> Deque.append secondDeque
    |> Deque.toList

is the same as

Deque.toList firstDeque
    |> List.append (Deque.toList secondDeque)

Lists

fromList : List a -> Deque a

Create a deque from a list.

toList : Deque a -> List a

Convert a deque to a list.

Query

isEmpty : Deque a -> Bool

Determine if a deque is empty.

member : a -> Deque a -> Bool

Figure out whether a deque contains a value.

length : Deque a -> Int

Determine the length of a list.

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

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.

Composition

map2 : (a -> b -> c) -> Deque a -> Deque b -> Deque c

Like List.map2; apply a function pairwise to two deques.

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

Handy function for constructing maps.

to extend to map3 and beyond:

map3 f a b c =
    map f a
        |> andMap b
        |> andMap c

folkertdev/elm-deque/3.0.1