Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Data.List

Singly-linked list operations.

The List(a) type and its Nil/Cons constructors are wired into the language (list literals, deriving); this module is the function surface over them. Base includes it, so these names are in scope unqualified everywhere; a project module reaches them with import Data.List. The container-generic queries (length, sum, all, find, and friends) live in Data.Foldable and work on any Foldable, this type included.

Functions and Values

singleton

singleton : forall a. (a) -> List(a)

The one-element list Cons(x, Nil).

is_nil

is_nil : forall a. (List(a)) -> Bool

True for the empty list.

head : forall a. (List(a)) -> Option(a)

The first element as Some, or None when the list is empty.

head([1, 2, 3])

Some(1)

tail

tail : forall a. (List(a)) -> List(a)

Everything after the first element (Nil for the empty list).

last

last : forall a. (List(a)) -> Option(a)

The final element as Some, or None when the list is empty.

last([1, 2, 3])

Some(3)

nth

nth : forall a. (Int, List(a)) -> Option(a)

The element at index n (zero-based) as Some, or None if out of range.

nth(1, [10, 20, 30])

Some(20)

take

take : forall a. (Int, List(a)) -> List(a)

The first n elements (fewer if the list is shorter).

take(2, [1, 2, 3, 4])

[1, 2]

drop

drop : forall a. (Int, List(a)) -> List(a)

The list with its first n elements removed.

drop(2, [1, 2, 3, 4])

[3, 4]

take_while

take_while : forall e0 a. ((a) -> Bool ! {e0}, List(a)) -> List(a) ! {e0}

The longest prefix of elements satisfying p.

take_while(\(x) -> x < 3, [1, 2, 3, 1])

[1, 2]

drop_while

drop_while : forall e0 a. ((a) -> Bool ! {e0}, List(a)) -> List(a) ! {e0}

The suffix remaining after take_while(p, xs).

drop_while(\(x) -> x < 3, [1, 2, 3, 1])

[3, 1]

split_at

split_at : forall a. (Int, List(a)) -> (List(a), List(a))

(take(n, xs), drop(n, xs)) in one pass of intent.

map

map : forall e0 a b. ((b) -> a ! {e0}, List(b)) -> List(a) ! {e0}

Apply f to every element, preserving order and length.

map(\(x) -> x + 1, [1, 2, 3])

[2, 3, 4]

filter

filter : forall e0 a. ((a) -> Bool ! {e0}, List(a)) -> List(a) ! {e0}

Keep the elements satisfying p.

filter(\(x) -> x > 1, [1, 2, 3])

[2, 3]

foldr

foldr : forall e0 a b. ((a, b) -> b ! {e0}, b, List(a)) -> b ! {e0}

Right fold: f(x0, f(x1, ... f(xn, z))).

foldr(\(x, acc) -> x + acc, 0, [1, 2, 3])

6

foldl

foldl : forall e0 a b. ((a, b) -> a ! {e0}, a, List(b)) -> a ! {e0}

Left fold: f(... f(f(z, x0), x1) ..., xn). Tail-recursive.

foldl(\(a, b) -> a + b, 0, [1, 2, 3])

6

append

append : forall a. (List(a), List(a)) -> List(a)

Concatenate two lists.

append([1, 2], [3, 4])

[1, 2, 3, 4]

reverse

reverse : forall a. (List(a)) -> List(a)

The list in reverse order.

reverse([1, 2, 3])

[3, 2, 1]

flatten

flatten : forall a. (List(List(a))) -> List(a)

Concatenate a list of lists.

flatten([[1, 2], [3], [4, 5]])

[1, 2, 3, 4, 5]

concat_map

concat_map : forall e0 a b. ((a) -> List(b) ! {e0}, List(a)) -> List(b) ! {e0}

Map f over the list and concatenate the resulting lists.

concat_map(\(x) -> [x, x], [1, 2])

[1, 1, 2, 2]

zip_with

zip_with : forall e0 a b c. ((b, c) -> a ! {e0}, List(b), List(c)) -> List(a) ! {e0}

Combine two lists elementwise with f, stopping at the shorter length.

zip_with(\(x, y) -> x + y, [1, 2, 3], [10, 20])

[11, 22]

zip

zip : forall a b. (List(a), List(b)) -> List((a, b))

Pair up two lists elementwise, stopping at the shorter length.

zip([1, 2], ["a", "b"])

[(1, a), (2, b)]

unzip

unzip : forall a b. (List((a, b))) -> (List(a), List(b))

Split a list of pairs into a pair of lists.

unzip([(1, "a"), (2, "b")])

([1, 2], [a, b])

count

count : forall e0 a. ((a) -> Bool ! {e0}, List(a)) -> Int ! {e0}

The number of elements satisfying p.

count(\(x) -> x > 1, [1, 2, 3])

2

position_go

position_go : forall e0 a. ((a) -> Bool ! {e0}, Int, List(a)) -> Option(Int) ! {e0}

Helper for position: search from index n.

position

position : forall e0 a. ((a) -> Bool ! {e0}, List(a)) -> Option(Int) ! {e0}

The index of the first element satisfying p as Some, or None.

position(\(x) -> x == 2, [1, 2, 3])

Some(1)

maximum

maximum : (List(Int)) -> Option(Int)

The greatest element as Some, or None for the empty list.

maximum([3, 1, 2])

Some(3)

minimum

minimum : (List(Int)) -> Option(Int)

The least element as Some, or None for the empty list.

minimum([3, 1, 2])

Some(1)

replicate

replicate : forall a. (Int, a) -> List(a)

A list of n copies of x.

replicate(3, 0)

[0, 0, 0]

range

range : (Int, Int) -> List(Int)

The ascending list [lo, lo+1, ..., hi-1] (empty when lo >= hi).

range(0, 5)

[0, 1, 2, 3, 4]

tabulate

tabulate : forall e0 a. (Int, (Int) -> a ! {e0}) -> List(a) ! {e0}

The list [f(0), f(1), ..., f(n-1)].

tabulate(3, \(i) -> i * i)

[0, 1, 4]

insert_sorted

insert_sorted : (Int, List(Int)) -> List(Int)

Insert x into an already-ascending list, keeping it sorted.

insert_sorted(3, [1, 2, 4])

[1, 2, 3, 4]

list_to_option

list_to_option : forall a. (List(a)) -> Option(a)

The first element as Some, or None (an Option view of the head).

partition

partition : forall e0 a. ((a) -> Bool ! {e0}, List(a)) -> (List(a), List(a)) ! {e0}

Split into (matching, non-matching) by predicate p.

partition(\(x) -> x > 1, [1, 2, 3])

([2, 3], [1])

chunks_of

chunks_of : forall a. (Int, List(a)) -> List(List(a))

Break the list into consecutive chunks of up to n elements.

chunks_of(2, [1, 2, 3, 4, 5])

[[1, 2], [3, 4], [5]]

scan_left

scan_left : forall e0 a b. ((a, b) -> a ! {e0}, a, List(b)) -> List(a) ! {e0}

Left scan: the running accumulators of foldl, starting from z.

scan_left(\(a, b) -> a + b, 0, [1, 2, 3])

[0, 1, 3, 6]

list_ap

list_ap : forall e0 a b. (List((b) -> a ! {e0}), List(b)) -> List(a) ! {e0}

Applicative apply for lists: every function in fs applied to every x.

list_ap([\(x) -> x + 1, \(x) -> x * 2], [10, 20])

[11, 21, 20, 40]