A queue of values. You can think about a Queue representation like about List, where left side is the input and right is output:

fromList   [ 2, 4, 6, 8 ]
-- indx -> [ 3, 2, 1, 0 ] ->

Create an empty queue:

empty == fromList []

Create a queue with only one element:

singleton 1234 == fromList [ 1234 ]


singleton "hi" == fromList [ "hi" ]

Create a queue from List.

It take time proportional to O(N).

Create a queue with n copies of a value:

repeat 3 "hi"
    == fromList [ "hi", "hi", "hi" ]

Create a queue of numbers, every element increasing one. You give the lowest and the highest number that should be in the queue.

range 3 6 == fromList [ 6, 5, 4, 3 ]


range 3 3 == fromList [ 3 ]


range 6 3 == fromList []


head (range 3 6) == Just 3

Extract the next element of a queue:

head empty == Nothing


head (singleton 0) == Just 0


head (fromList [ 1, 2, 3 ]) == Just 3

It takes constant time O(1).

Extract the rest of the list:

tail (fromList [ 1, 2, 3 ]) == Just [ 1, 2 ]


tail empty == Nothing

It takes constant time in average case θ(1) (Ω(1) and O(N)).

Take the first n members of a queue:

take 2 (fromList [ 1, 2, 3 ]) == formList [ 2, 3 ]

It takes constant time in case when n <= 0 || n >= N.

Drop the first n members of a queue:

drop 2 (fromList [ 1, 2, 3 ]) == formList [ 1 ]

It takes constant time in case when n <= 0 || n >= N.

Partition a queue based on some test. The first queue contains all values that satisfy the test, and the second queue contains all the value that do not.

[ 0, 1, 2, 3, 4, 5 ]
    |> fromList
    |> partition (\x -> x < 3)
    == ( fromList [ 0, 1, 2 ], fromList [ 3, 4, 5 ] )


[ 0, 1, 2, 3, 4, 5 ]
    |> fromList
    |> partition isEven
    == ( fromList [ 0, 2, 4 ], fromList [ 1, 3, 5 ] )

Decompose a queue of tuples into a tuple of queues.

[ ( 0, True )
, ( 17, False )
, ( 1337, True )
]
    |> fromList
    |> unzip
    == ( fromList [ 0, 17, 1337 ]
       , fromList [ True, False, True ]
       )

Convert a queue (FIFO) to list (LIFO):

toList (fromList [ 1, 2, 3 ]) == [ 1, 2, 3 ]


empty
    |> enqueue 3
    |> enqueue 2
    |> enqueue 1
    |> toList
    == [ 1, 2, 3 ]

It takes time proportional to O(N).

Add an element to the queue.

enqueue 1 empty == fromList [ 1 ]


enqueue 1 (fromList [ 2, 3, 4 ])
    == fromList [ 1, 2, 3, 4 ]


empty
    |> enqueue 1
    |> enqueue 2
    |> enqueue 3
    == fromList [ 3, 2, 1 ]

It takes constant time O(1).

Extract and remove the first element from the queue:

dequeue empty == Nothing


dequeue (singleton 1) == Just ( 1, empty )


dequeue (fromList [ 1, 2, 3 ])
    == Just ( 3, fromList [ 1, 2 ] )

It takes constant time in average case θ(1) (Ω(1) and O(N)).

Determine the length of a queue:

length empty == 0


length (fromList [ 3, 2, 1 ]) == 3

It takes constant time O(1).

Determine if a queue is empty.

isEmpty (fromList []) == True


isEmpty (fromList [ 1, 2, 3 ]) == False

Determine if two queues are equal. It takes constant time O(1) when lengths are different.

Determine if any elements satisfy some test:

any isEven (fromList [ 2, 3 ]) == True


any isEven (fromList [ 1, 3 ]) == False


any isEven (fromList []) == False

Determine if all elements satisfy some test.

all isEven (fromList [ 2, 4 ]) == True


all isEven (fromList [ 2, 3 ]) == False


all isEven (fromList []) == True

Figure out whether a queue contains a value.

member 9 (fromList []) == False


member 9 (fromList [ 1, 2, 3, 4 ]) == False


member 4 (fromList [ 1, 2, 3, 4 ]) == True

Find the maximum element in a non-empty queue:

maximum (fromList [ 1, 4, 2 ]) == Just 4


maximum (fromList []) == Nothing

Find the minimum element in a non-empty queue:

minimum (fromList [ 3, 2, 1 ]) == Just 1


minimum (fromList []) == Nothing

Get the sum of the queue elements:

sum (fromList [ 1, 2, 3 ]) == 6


sum (fromList [ 1, 1, 1 ]) == 3


sum (fromList []) == 0

Get the product of the queue elements:

product (from List [ 2, 2, 2 ]) == 8


product (from List [ 3, 3, 3 ]) == 27


product (from List []) == 1

Apply a function to every element of a queue:

map sqrt (fromList [ 1, 4, 9 ])
    == fromList [ 1, 2, 3 ]

Same as map but the function is also applied to the index of each element (starting at zero):

indexedMap Tuple.pair (fromList [ "A", "B", "C" ])
    == fromList [ ( 2, "A" ), ( 1, "B" ), ( 0, "C" ) ]

Reduce queue from left to right (or from the oldest to newest):

empty
    |> enqueue 3
    |> enqueue 2
    |> enqueue 1
    |> foldr (+) 0
    === 6


empty
    |> enqueue 3
    |> enqueue 2
    |> enqueue 1
    |> foldr (::) []
    == [ 1, 2, 3 ]

So foldr step state (fromList [ 1, 2, 3 ]) is like saying:

state
    |> step 3
    |> step 2
    |> step 1

Reduce queue from right to left (or from the newest to oldest):

empty
    |> enqueue 3
    |> enqueue 2
    |> enqueue 1
    |> foldl (+) 0
    === 6


empty
    |> enqueue 3
    |> enqueue 2
    |> enqueue 1
    |> foldl (::) []
    == [ 3, 2, 1 ]

So foldl step state (fromList [ 1, 2, 3 ]) is like saying:

state
    |> step 1
    |> step 2
    |> step 3

Keep elements that satisfy the test:

filter isEven (fromList [ 1, 2, 3, 4, 5, 6 ])
    == fromList [ 2, 4, 6 ]

Filter out certain values. For example, maybe you have a bunch of strings from an untrusted source and you want to turn them into numbers:

[ "3", "hi", "12", "4th", "May" ]
    |> fromList
    |> filterMap String.toInt
    == fromList [ 3, 12 ]

Reverse the queue:

reverse (fromList [ 1, 2, 3, 4 ])
    == fromList [ 4, 3, 2, 1 ]

Put two queues together:

append (fromList [ 1, 1, 2 ]) (fromList [ 3, 5, 8 ])
    == fromList [ 1, 1, 2, 3, 5, 8 ]


append (fromList [ 'a', 'b' ]) (fromList [ 'c' ])
    == fromList [ 'a', 'b', 'c' ]

Concatenate a bunch of queues into a single queue:

[ fromList [ 1, 2 ]
, fromList [ 3 ]
, fromList [ 4, 5 ]
]
    |> fromList
    |> concat
    == fromList [ 1, 2, 3, 4, 5 ]

Map a given function onto a queue and flatten the resulting queues:

concatMap f xs == concat (map f xs)

Places the given value between all members of the given queue.

intersperse ">" (fromList [ "third", "second", "first" ])
    == fromList [ "third", ">", "second", ">", "first" ]

Combine two queues, combining them with the given function. If one queue is longer, the extra elements are dropped.

map2 (+)
    (fromList [ 1, 2, 3 ])
    (fromList [ 4, 5, 6 ])
    == fromList [ 5, 7, 9 ]


map2 Tuple.pair
    (fromList [ "alice", "bob", "chuck" ])
    (fromList [ 2, 5, 7, 8 ])
    == fromList
        [ ( "alice", 5 )
        , ( "bob", 7 )
        , ( "chuck", 8 )
        ]

Sort values from lowest to highest:

sort (fromList [ 3, 1, 5 ]) == fromList [ 5, 3, 1 ]

Sort values by a derived property:

alice =
    { name = "Alice", height = 1.62 }


bob =
    { name = "Bob", height = 1.85 }


chuck =
    { name = "Chuck", height = 1.76 }


[ chuck, alice, bob ]
    |> fromList
    |> sortBy .name
    == fromList [ chuck, bob, alice ]


[ chuck, alice, bob ]
    |> fromList
    |> sortBy .height
    == fromList [ bob, chuck, alice ]


[ "cat", "mouse" ]
    |> fromList
    |> sortBy String.length
    == fromList [ "mouse", "cat" ]

Sort values with a custom comparison function:

flippedComparison a b =
    case compare a b of
        LT -> GT
        EQ -> EQ
        GT -> LT


[ 5, 4, 3, 2, 1 ]
    |> fromList
    |> sortWith flippedComparison
    == fromList [ 1, 2, 3, 4, 5 ]