← Playground The Medaka Standard Library
☰

#list

Operations on List a.

A list is an immutable singly linked sequence. Every operation here returns a new list and leaves its argument unchanged. Functions that could fail on an empty list or an out-of-range index return an Option instead of panicking.

The generic container operations (map, filter, fold, length, elem, sum, maximum, any, all, and the rest of the Foldable and Traversable interfaces) are defined in the prelude and work on lists without an import. This module holds what is specific to lists.

#Re-exports

#Filterable

Filterable : re-export of core.Filterable

Re-exported from the prelude so that list.filter and list.filterMap resolve when the module is imported qualified.

#filter

filter : (a -> <b> Bool) -> c a -> <b> c a

Re-exported from the prelude so that list.filter and list.filterMap resolve when the module is imported qualified.

#filterMap

filterMap : (a -> <b> Option c) -> d a -> <b> d c

Re-exported from the prelude so that list.filter and list.filterMap resolve when the module is imported qualified.

#Construction

#singleton

singleton : a -> List a
singleton a

A list holding one element.

> singleton 5
[5]

#range

range : Int -> Int -> List Int
range lo hi

The integers from lo up to, but not including, hi.

Empty when lo >= hi. [lo..hi] is the literal form.

> range 2 5
[2, 3, 4]

#rangeStep

rangeStep : Int -> Int -> Int -> List Int
rangeStep lo hi step

The integers from lo towards hi in steps of step, stopping before hi.

A negative step counts down. Empty when step is 0 or points away from hi.

> rangeStep 0 10 3
[0, 3, 6, 9]
> rangeStep 5 0 (-2)
[5, 3, 1]

#replicate

replicate : Int -> a -> List a
replicate n x

A list of n copies of x.

Empty when n <= 0. Safe for large n: the call depth grows with log n, not n.

> replicate 3 0
[0, 0, 0]

#iterate

iterate : Int -> (a -> <e> a) -> a -> <e> List a
iterate n f x

The first n results of applying f repeatedly, starting from x: [x, f x, f (f x), ...].

Empty when n <= 0.

> iterate 4 (n => n * 2) 1
[1, 2, 4, 8]

#unfold

unfold : (b -> <e> Option (a, b)) -> b -> <e> List a
unfold gen seed

Builds a list from a seed.

gen is called with the current seed. It returns Some of the element to emit and the seed to continue from, or None to stop.

> unfold (n => if n > 5 then None else Some (n, n + 1)) 1
[1, 2, 3, 4, 5]

#Accessing elements

head : List a -> Option a

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

> head [1, 2, 3]
Some 1
> head ([] : List Int)
None

#tail

tail : List a -> Option (List a)

Everything after the first element, or None when the list is empty.

> tail [1, 2, 3]
Some [2, 3]
> tail [1]
Some []

#uncons

uncons : List a -> Option (a, List a)

The first element and the rest, or None when the list is empty.

> uncons [1, 2, 3]
Some (1, [2, 3])

#last

last : List a -> Option a

The last element, or None when the list is empty.

> last [1, 2, 3]
Some 3

#init

init : List a -> Option (List a)

Everything except the last element, or None when the list is empty.

> init [1, 2, 3]
Some [1, 2]
> init [1]
Some []

#get

get : Int -> List a -> Option a
get i _

The element at index i, counting from 0, or None when i is out of range.

Walks the list from the front, so the cost grows with i.

> get 1 ["a", "b", "c"]
Some "b"
> get 5 ["a", "b", "c"]
None

#Transformation

#reverse

reverse : List a -> List a
reverse xs

The list in reverse order.

Safe on long lists.

> reverse [1, 2, 3]
[3, 2, 1]

#intersperse

intersperse : a -> List a -> List a
intersperse sep _

The list with sep placed between each pair of adjacent elements.

> intersperse 0 [1, 2, 3]
[1, 0, 2, 0, 3]

#intercalate

intercalate : List a -> List (List a) -> List a
intercalate sep xss

The inner lists joined into one, with sep between each pair.

> intercalate [0] [[1], [2, 3], [4]]
[1, 0, 2, 3, 0, 4]

#transpose

transpose : List (List a) -> List (List a)

The rows of a list of lists turned into columns.

Rows may have different lengths. A short row contributes nothing to the columns beyond its end.

> transpose [[1, 2, 3], [4, 5, 6]]
[[1, 4], [2, 5], [3, 6]]
> transpose [[1, 2], [3], [4, 5, 6]]
[[1, 3, 4], [2, 5], [6]]

#subsequences

subsequences : List a -> List (List a)

Every subsequence of the list: each subset of its elements, in their original order.

A list of n elements has 2^n subsequences.

> subsequences [1, 2, 3]
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

#permutations

permutations : List a -> List (List a)
permutations xs

Every ordering of the list's elements.

A list of n elements has n! permutations. They are produced in lexicographic order of the original positions.

> permutations [1, 2, 3]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

#Folds and scans

#scanLeft

scanLeft : (b -> a -> <e> b) -> b -> List a -> <e> List b
scanLeft f z _

Every intermediate value of a left fold, starting with the seed.

The result is one element longer than the input.

> scanLeft (acc x => acc + x) 0 [1, 2, 3]
[0, 1, 3, 6]

#scanRight

scanRight : (a -> b -> <e> b) -> b -> List a -> <e> List b
scanRight f z _

Every intermediate value of a right fold, ending with the seed.

> scanRight (x acc => x + acc) 0 [1, 2, 3]
[6, 5, 3, 0]

#reduce

reduce : (a -> a -> <e> a) -> List a -> <e> Option a
reduce f _

A left fold that uses the first element as the seed.

None when the list is empty. fold is the form that takes a seed.

> reduce (x y => x + y) [1, 2, 3, 4]
Some 10

#maximumBy

maximumBy : (a -> a -> <e> Ordering) -> List a -> <e> Option a
maximumBy cmp xs

The largest element according to cmp, or None when the list is empty.

When several elements compare equal, the first one wins. maximum is the form that uses the Ord instance.

> maximumBy (x y => compare (x % 10) (y % 10)) [23, 47, 15]
Some 47

#minimumBy

minimumBy : (a -> a -> <e> Ordering) -> List a -> <e> Option a
minimumBy cmp xs

The smallest element according to cmp, or None when the list is empty.

When several elements compare equal, the first one wins. minimum is the form that uses the Ord instance.

> minimumBy (x y => compare (x % 10) (y % 10)) [23, 47, 15]
Some 23

#findIndex

findIndex : (a -> <e> Bool) -> List a -> <e> Option Int
findIndex p xs

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

> findIndex (x => x > 2) [1, 2, 3, 4]
Some 2

#findIndices

findIndices : (a -> <e> Bool) -> List a -> <e> List Int
findIndices p xs

The indices of every element satisfying p.

> findIndices (x => x > 2) [1, 3, 2, 4]
[1, 3]

#elemIndex

elemIndex : Eq a => a -> List a -> Option Int
elemIndex x xs

The index of the first element equal to x, or None.

> elemIndex 3 [1, 2, 3, 2]
Some 2

#elemIndices

elemIndices : Eq a => a -> List a -> List Int
elemIndices x xs

The indices of every element equal to x.

> elemIndices 2 [1, 2, 3, 2]
[1, 3]

#lookup

lookup : Eq k => k -> List (k, v) -> Option v
lookup key _

The value paired with key in an association list, or None.

The first matching pair wins. Each lookup scans the list, so for a large or long-lived table use map.Map or hash_map.HashMap.

> lookup 2 [(1, "a"), (2, "b")]
Some "b"
> lookup 9 [(1, "a"), (2, "b")]
None

#findMap

findMap : (a -> <e> Option b) -> List a -> <e> Option b
findMap f _

The first Some produced by applying f to the elements in order, or None.

Stops at the first hit, so f is not applied to the remaining elements.

> findMap (x => if x > 2 then Some (x * 10) else None) [1, 2, 3, 4]
Some 30

#Indexed

#mapWithIndex

mapWithIndex : (Int -> a -> <e> b) -> List a -> <e> List b
mapWithIndex f xs

Like map, with f also receiving each element's index, counting from 0.

> mapWithIndex (i x => i * x) [1, 2, 3]
[0, 2, 6]

#indexed

indexed : List a -> List (Int, a)
indexed xs

Each element paired with its index, counting from 0.

> indexed ["a", "b", "c"]
[(0, "a"), (1, "b"), (2, "c")]

#mapAccumL

mapAccumL : (s -> a -> <e> (s, b)) -> s -> List a -> <e> (s, List b)
mapAccumL f s _

A map that threads a state value from left to right.

f receives the state and an element, and returns the new state and the mapped element. The result is the final state and the mapped list.

> mapAccumL (s x => (s + x, s)) 0 [1, 2, 3]
(6, [0, 1, 3])

#mapAccumR

mapAccumR : (s -> a -> <e> (s, b)) -> s -> List a -> <e> (s, List b)
mapAccumR f s _

Like mapAccumL, but threads the state from right to left.

The mapped list keeps the input's order.

> mapAccumR (s x => (s + x, s)) 0 [1, 2, 3]
(6, [5, 3, 0])

#Positional edits

#insertAt

insertAt : Int -> a -> List a -> List a
insertAt i x _

The list with x inserted at index i, shifting the following elements right.

An index at or below 0 prepends; an index at or beyond the length appends.

> insertAt 1 9 [1, 2, 3]
[1, 9, 2, 3]

#updateAt

updateAt : Int -> a -> List a -> List a
updateAt i x _

The list with the element at index i replaced by x.

Unchanged when i is out of range.

> updateAt 1 9 [1, 2, 3]
[1, 9, 3]

#removeAt

removeAt : Int -> List a -> List a
removeAt i _

The list without the element at index i.

Unchanged when i is out of range.

> removeAt 1 [1, 2, 3]
[1, 3]

#Sublists

#take

take : Int -> List a -> List a
take n _

The first n elements, or the whole list when it has fewer.

> take 2 [1, 2, 3, 4]
[1, 2]

#drop

drop : Int -> List a -> List a
drop n xs

Everything after the first n elements.

> drop 2 [1, 2, 3, 4]
[3, 4]

#takeWhile

takeWhile : (a -> <e> Bool) -> List a -> <e> List a
takeWhile p _

The longest prefix whose elements all satisfy p.

> takeWhile (x => x < 3) [1, 2, 3, 1]
[1, 2]

#dropWhile

dropWhile : (a -> <e> Bool) -> List a -> <e> List a
dropWhile p xs

The list without its longest prefix of elements satisfying p.

> dropWhile (x => x < 3) [1, 2, 3, 1]
[3, 1]

#span

span : (a -> <e> Bool) -> List a -> <e> (List a, List a)
span p xs

The longest prefix satisfying p, and the rest of the list.

Equivalent to (takeWhile p xs, dropWhile p xs) in one pass.

> span (x => x < 3) [1, 2, 3, 1]
([1, 2], [3, 1])

#break

break : (a -> <e> Bool) -> List a -> <e> (List a, List a)
break p xs

The prefix before the first element satisfying p, and the rest of the list.

The same as span with the predicate negated.

> break (x => x > 2) [1, 2, 3, 1]
([1, 2], [3, 1])

#splitAt

splitAt : Int -> List a -> (List a, List a)
splitAt n xs

The first n elements, and the rest of the list.

Equivalent to (take n xs, drop n xs) in one pass.

> splitAt 2 [1, 2, 3, 4]
([1, 2], [3, 4])

#sliceClamped

sliceClamped : Int -> Int -> List a -> List a
sliceClamped lo hi xs

The elements at indices [lo, hi).

Indices are clamped to the list, so an out-of-range slice is shorter rather than a panic. xs.[lo..hi] is the panicking form.

> sliceClamped 1 3 [10, 20, 30, 40]
[20, 30]

#chunks

chunks : Int -> List a -> List (List a)
chunks n xs

The list split into consecutive groups of n elements.

The last group holds whatever remains, so it may be shorter. Empty when n <= 0.

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

#dropWhileEnd

dropWhileEnd : (a -> <e> Bool) -> List a -> <e> List a
dropWhileEnd p xs

The list without its longest suffix of elements satisfying p.

> dropWhileEnd (x => x == 0) [1, 2, 0, 0]
[1, 2]

#takeWhileEnd

takeWhileEnd : (a -> <e> Bool) -> List a -> <e> List a
takeWhileEnd p xs

The longest suffix whose elements all satisfy p.

> takeWhileEnd (x => x > 1) [1, 2, 3]
[2, 3]

#split

split : Eq a => List a -> List a -> List (List a)
split sep xs

The list split at every occurrence of the separator sep, with the separators removed.

An empty separator yields the whole list as the only piece. This is the list form of string.split; splitAt is the positional split.

> split [0] [1, 0, 2, 0, 3]
[[1], [2], [3]]
> split [0] [0, 1]
[[], [1]]

#Sublist predicates

#startsWith

startsWith : Eq a => List a -> List a -> Bool
startsWith prefix _

Whether the list begins with prefix.

Every list begins with the empty list. elem is the test for a single element.

> startsWith [1, 2] [1, 2, 3]
True
> startsWith [2, 3] [1, 2, 3]
False

#endsWith

endsWith : Eq a => List a -> List a -> Bool
endsWith suffix xs

Whether the list ends with suffix.

> endsWith [2, 3] [1, 2, 3]
True
> endsWith [1, 2] [1, 2, 3]
False

#containsSub

containsSub : Eq a => List a -> List a -> Bool
containsSub sub xs

Whether sub occurs as a contiguous run anywhere in the list.

The scan costs O(n * m). For text, string.contains is faster.

> containsSub [2, 3] [1, 2, 3, 4]
True
> containsSub [2, 4] [1, 2, 3, 4]
False

#Sorting

#sortBy

sortBy : (a -> a -> <e> Ordering) -> List a -> <e> List a
sortBy cmp xs

The list sorted by cmp.

The sort is stable: elements that compare equal keep their original order. It costs O(n log n).

> sortBy (x y => compare y x) [3, 1, 2]
[3, 2, 1]

#sort

sort : Ord a => List a -> List a
sort xs

The list sorted in ascending order.

The sort is stable.

> sort [3, 1, 2, 1]
[1, 1, 2, 3]

#sortOn

sortOn : Ord b => (a -> <e> b) -> List a -> <e> List a
sortOn key xs

The list sorted in ascending order of key.

key is computed once per element, so it may be expensive. The sort is stable.

> sortOn (x => 0 - x) [1, 3, 2]
[3, 2, 1]

#nubBy

nubBy : (a -> a -> <e> Bool) -> List a -> <e> List a
nubBy same xs

The list with duplicates removed, where same decides which elements are duplicates.

The first occurrence is kept. Costs O(n^2).

> nubBy (x y => x == y) [1, 2, 1, 3, 2]
[1, 2, 3]

#nub

nub : Eq a => List a -> List a
nub xs

The list with duplicate elements removed.

The first occurrence is kept. Costs O(n^2); for large lists, build a set.Set or hash_set.HashSet instead.

> nub [1, 2, 1, 3, 2, 1]
[1, 2, 3]

#deleteBy

deleteBy : (a -> a -> <e> Bool) -> a -> List a -> <e> List a
deleteBy same x _

The list without the first element that same matches against x.

Unchanged when nothing matches.

> deleteBy (x y => x == y) 2 [1, 2, 3, 2]
[1, 3, 2]

#delete

delete : Eq a => a -> List a -> List a
delete x xs

The list without the first occurrence of x.

Unchanged when x is absent. filter (/= x) removes every occurrence.

> delete 2 [1, 2, 3, 2]
[1, 3, 2]

#Grouping

#groupBy

groupBy : (a -> a -> <e> Bool) -> List a -> <e> List (List a)
groupBy same _

The list split into runs of adjacent elements that same considers equivalent.

> groupBy (x y => x == y) [1, 1, 2, 3, 3, 3]
[[1, 1], [2], [3, 3, 3]]

#group

group : Eq a => List a -> List (List a)
group xs

The list split into runs of adjacent equal elements.

> group [1, 1, 2, 3, 3]
[[1, 1], [2], [3, 3]]

#partition

partition : (a -> <e> Bool) -> List a -> <e> (List a, List a)
partition p _

The elements satisfying p, and the elements that do not.

Both parts keep the input's order.

> partition (x => x > 2) [1, 2, 3, 4]
([3, 4], [1, 2])

#somes

somes : List (Option a) -> List a

The values inside the Somes, with the Nones dropped.

> somes [Some 1, None, Some 3]
[1, 3]

#oks

oks : List (Result e a) -> List a

The values inside the Oks, with the Errs dropped.

> oks [Ok 1, Err "boom", Ok 3]
[1, 3]

#errs

errs : List (Result e a) -> List e

The values inside the Errs, with the Oks dropped.

> errs [Ok 1, Err "boom", Ok 3]
["boom"]

#partitionResults

partitionResults : List (Result e a) -> (List e, List a)

The Err values and the Ok values, as two lists.

> partitionResults [Ok 1, Err "boom", Ok 3]
(["boom"], [1, 3])

#tally

tally : Eq a => List a -> List (a, Int)
tally xs

Each distinct element paired with the number of times it occurs.

Elements appear in the order they were first seen.

> tally [1, 2, 1, 3, 1, 2]
[(1, 3), (2, 2), (3, 1)]

#Zipping

#zip

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

The elements of two lists paired up by position.

The result is as long as the shorter input. Extra elements of the longer one are dropped.

> zip [1, 2, 3] [10, 20]
[(1, 10), (2, 20)]

#zip3

zip3 : List a -> List b -> List c -> List (a, b, c)

The elements of three lists grouped into triples by position.

The result is as long as the shortest input.

> zip3 [1, 2] [3, 4] [5, 6]
[(1, 3, 5), (2, 4, 6)]

#zipWith

zipWith : (a -> b -> <e> c) -> List a -> List b -> <e> List c
zipWith f _ _

The elements of two lists combined by position with f.

The result is as long as the shorter input. zip is zipWith with a pairing function.

> zipWith (x y => x + y) [1, 2, 3] [10, 20, 30]
[11, 22, 33]

#zip4

zip4 : List a -> List b -> List c -> List d -> List (a, b, c, d)

The elements of four lists grouped into 4-tuples by position.

The result is as long as the shortest input.

> zip4 [1, 2] [3, 4] [5, 6] [7, 8]
[(1, 3, 5, 7), (2, 4, 6, 8)]

#zipWith3

zipWith3 : (a -> b -> c -> <e> d) -> List a -> List b -> List c -> <e> List d
zipWith3 f _ _ _

The elements of three lists combined by position with f.

The result is as long as the shortest input.

> zipWith3 (x y z => x + y + z) [1, 2] [10, 20] [100, 200]
[111, 222]

#unzip

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

A list of pairs separated into a pair of lists. The inverse of zip.

> unzip [(1, 2), (3, 4)]
([1, 3], [2, 4])

#unzip3

unzip3 : List (a, b, c) -> (List a, List b, List c)

A list of triples separated into three lists. The inverse of zip3.

> unzip3 [(1, 2, 3), (4, 5, 6)]
([1, 4], [2, 5], [3, 6])

#Instances

  • List: Eq, Semigroup, Monoid, Ord, Debug, Display, Hashable, Mappable, Applicative, Thenable, Alternative, Index, Slice, Foldable, Traversable, Filterable, Arbitrary

#Ord (List a)

impl Ord (List a) requires Ord a

Lists compare lexicographically: element by element, with a proper prefix sorting before any list that extends it ([1] < [1, 2], [] < [0]).

#Index (List a) Int a

impl Index (List a) Int a

xs[i] walks the list to position i, so it costs O(i).

Panics with an index error when i is out of range; list.get is the Option-returning form. Lists are immutable, so there is no IndexMut instance.

#Slice (List a)

impl Slice (List a)

The sublist over [lo, hi), in O(hi).

Panics with a slice error when the range runs outside the list; list.sliceClamped clamps instead.

> slice [10, 20, 30, 40] 1 3
[20, 30]

#Filterable List

impl Filterable List

filter and filterMap on lists.

> filter (x => x > 2) [1, 2, 3, 4]
[3, 4]

#Arbitrary (List a)

impl Arbitrary (List a) requires Arbitrary a

A random list of up to ten elements drawn from the element's instance.