List
Import List for operations on [a]. Unless noted otherwise, functions
preserve input order and return new lists without modifying their inputs.
Shape
prepend
Adds a value to the front of a list in O(1).
reverse
Returns the values in reverse order in O(n).
length
Counts the values in O(n).
isEmpty
Returns True only for []. This is O(1).
Safe access
head
Returns Just containing the first value, or Nothing for []. This is
O(1).
tail
Returns every value after the head, or Nothing for []. This is O(1).
last
Returns the final value, or Nothing for [], in O(n).
init
Returns every value except the last, or Nothing for [], in O(n).
at
Returns the zero-based value at the index. Negative and out-of-range indices
return Nothing. The cost is O(min(n, index)) for a non-negative index.
Slicing
take
Returns at most the first count values. Counts below zero clamp to zero. The
cost is linear in the returned prefix.
drop
Skips at most the first count values. Counts below zero clamp to zero. The
cost is linear in the skipped prefix.
splitAt
Returns (take count values, drop count values). Negative counts yield
an empty prefix and the original list as the suffix.
Combining
append
Returns the left list followed by the right list. The cost is O(n) in the
left list.
concat
Flattens lists from left to right. The cost is linear in the fragment count and the total number of produced values.
repeat
Returns count copies of a value. Non-positive counts return []. The cost is
linear in the output length.
intersperse
Places the separator between adjacent values, never before the first or after the last. This is linear in the output length.
intercalate
Inserts the separator list between adjacent fragments and concatenates the result. Work is linear in fragments plus produced values.
Transforming
map
Transforms every value from left to right and preserves order. This is O(n)
plus callback work.
filter
Keeps values whose predicate returns True, preserving their order. This is
O(n) plus callback work.
filterMap
Calls the transform for each value, keeping values inside Just and discarding
Nothing. Output order matches input order.
partition
Returns matching values first and rejected values second. Both lists preserve
input order. This is O(n) plus callback work.
Folding
foldLeft
Combines values from left to right, starting with the supplied accumulator.
This is O(n) plus callback work.
foldRight
Combines values from right to left, starting with the supplied terminal value.
This is O(n) plus callback work.
scanLeft
Returns the initial accumulator followed by every successive left-fold result, so the output has one more value than the input.
Example: scanLeft (\(sum, value) -> sum + value) 0 [1, 2, 3] produces
[0, 1, 3, 6].
Search
any
Returns True at the first matching value and short-circuits. It returns
False for [] and is O(n) worst case.
all
Returns False at the first rejected value and short-circuits. It returns
True for [] and is O(n) worst case.
contains
Tests equality against values from left to right and short-circuits at the
first match. This is O(n) worst case and requires Equatable(a).
find
Returns the first matching value as Just, or Nothing when no value matches.
The search short-circuits and is O(n) worst case.
findIndex
Returns the zero-based index of the first match, or Nothing. The search
short-circuits and is O(n) worst case.
Pair views
zip
Pairs corresponding values and stops when either input ends. Example:
zip [1, 2] ["a"] produces [(1, "a")].
unzip
Separates pairs into left and right lists while preserving pair order. This is
O(n).
indexed
Pairs values with zero-based indices in input order. This is O(n).
Normalization
distinct
Removes repeated values while preserving the first occurrence of each value.
This requires Equatable(a) and is O(n²) worst case.
group
Groups adjacent equal values. Equal values separated by another value remain
in different groups. This is O(n) plus equality work.
groupBy
Groups runs according to adjacent comparisons. A run continues while the
predicate returns True for each value and the value immediately following it.
This is O(n) plus callback work.
Ordering
minimum
Returns the least value, or Nothing for [], in O(n).
maximum
Returns the greatest value, or Nothing for [], in O(n).
sort
Returns a stable ascending merge sort using Comparable(a). The cost is
O(n log n).
sortBy
Returns a stable merge sort ordered by the comparator. LT places the left
value first; EQ preserves the input order of equal values. The cost is
O(n log n) plus comparator work.
Functions that may not find a value return Maybe.
Generic methods
The Prelude supplies element-based Equatable, Mappable, Reducible, and Combinable instances for List. The specialized functions keep their documented argument order.