Module List
: sigend
List operations.
Some functions are flagged as not tail-recursive. A tail-recursive function uses constant stack space,
while a non-tail-recursive function uses stack space proportional to the length of its list argument,
which can be a problem with very long lists. When the function takes several list arguments, an
approximate formula giving stack usage (in some unspecified constant unit) is shown in parentheses.
The above considerations can usually be ignored if your lists are not longer than about 10000 elements.
The labeled version of this module can be used as described in the StdLabels module.
type'at = 'alist =
| []
| (::) of'a*'alist
An alias for the type of lists.
vallength : 'alist->int
Return the length (number of elements) of the given list.
valcompare_lengths : 'alist->'blist->int
Compare the lengths of two lists. compare_lengthsl1l2 is equivalent to compare(lengthl1)(lengthl2)
, except that the computation stops after reaching the end of the shortest list.
Since 4.05
valcompare_length_with : 'alist->int->int
Compare the length of a list to an integer. compare_length_withllen is equivalent to compare(lengthl)len , except that the computation stops after at most len iterations on the list.
Since 4.05
valis_empty : 'alist->boolis_emptyl is true if and only if l has no elements. It is equivalent to compare_length_withl0=0 .
Since 5.1
valcons : 'a->'alist->'alistconsxxs is x::xsSince 4.03 (4.05 in ListLabels)
valhd : 'alist->'a
Return the first element of the given list.
RaisesFailure if the list is empty.
valtl : 'alist->'alist
Return the given list without its first element.
RaisesFailure if the list is empty.
valnth : 'alist->int->'a
Return the n -th element of the given list. The first element (head of the list) is at position 0.
RaisesFailure if the list is too short.
RaisesInvalid_argument if n is negative.
valnth_opt : 'alist->int->'aoption
Return the n -th element of the given list. The first element (head of the list) is at position 0.
Return None if the list is too short.
Since 4.05
RaisesInvalid_argument if n is negative.
valrev : 'alist->'alist
List reversal.
valinit : int->(int->'a)->'alistinitlenf is [f0;f1;...;f(len-1)] , evaluated left to right.
Since 4.06
RaisesInvalid_argument if len<0 .
valappend : 'alist->'alist->'alistappendl0l1 appends l1 to l0 . Same function as the infix operator @ .
Since 5.1 this function is tail-recursive.
valrev_append : 'alist->'alist->'alistrev_appendl1l2 reverses l1 and concatenates it with l2 . This is equivalent to (List.revl1)@l2 .
valconcat : 'alistlist->'alist
Concatenate a list of lists. The elements of the argument are all concatenated together (in the same
order) to give the result. Not tail-recursive (length of the argument + length of the longest sub-list).
valflatten : 'alistlist->'alist
Same as List.concat . Not tail-recursive (length of the argument + length of the longest sub-list).
Comparisonvalequal : ('a->'a->bool)->'alist->'alist->boolequaleq[a1;...;an][b1;..;bm] holds when the two input lists have the same length, and for each
pair of elements ai , bi at the same position we have eqaibi .
Note: the eq function may be called even if the lists have different length. If you know your equality
function is costly, you may want to check List.compare_lengths first.
Since 4.12
valcompare : ('a->'a->int)->'alist->'alist->intcomparecmp[a1;...;an][b1;...;bm] performs a lexicographic comparison of the two input lists, using
the same 'a->'a->int interface as compare :
- a1::l1 is smaller than a2::l2 (negative result) if a1 is smaller than a2 , or if they are equal (0
result) and l1 is smaller than l2
-the empty list [] is strictly smaller than non-empty lists
Note: the cmp function will be called even if the lists have different lengths.
Since 4.12
Iteratorsvaliter : ('a->unit)->'alist->unititerf[a1;...;an] applies function f in turn to [a1;...;an] . It is equivalent to fa1;fa2;...;fan .
valiteri : (int->'a->unit)->'alist->unit
Same as List.iter , but the function is applied to the index of the element as first argument (counting
from 0), and the element itself as second argument.
Since 4.00
valmap : ('a->'b)->'alist->'blistmapf[a1;...;an] applies function f to a1,...,an , and builds the list [fa1;...;fan] with the
results returned by f .
valmapi : (int->'a->'b)->'alist->'blist
Same as List.map , but the function is applied to the index of the element as first argument (counting
from 0), and the element itself as second argument.
Since 4.00
valrev_map : ('a->'b)->'alist->'blistrev_mapfl gives the same result as List.rev(List.mapfl) , but is more efficient.
valfilter_map : ('a->'boption)->'alist->'blistfilter_mapfl applies f to every element of l , filters out the None elements and returns the list of
the arguments of the Some elements.
Since 4.08
valconcat_map : ('a->'blist)->'alist->'blistconcat_mapfl gives the same result as List.concat(List.mapfl) . Tail-recursive.
Since 4.10
valfold_left_map : ('acc->'a->'acc*'b)->'acc->'alist->'acc*'blistfold_left_map is a combination of fold_left and map that threads an accumulator through calls to f .
Since 4.11
valfold_left : ('acc->'a->'acc)->'acc->'alist->'accfold_leftfinit[b1;...;bn] is f(...(f(finitb1)b2)...)bn .
valfold_right : ('a->'acc->'acc)->'alist->'acc->'accfold_rightf[a1;...;an]init is fa1(fa2(...(faninit)...)) . Not tail-recursive.
Iteratorsontwolistsvaliter2 : ('a->'b->unit)->'alist->'blist->unititer2f[a1;...;an][b1;...;bn] calls in turn fa1b1;...;fanbn .
RaisesInvalid_argument if the two lists are determined to have different lengths.
valmap2 : ('a->'b->'c)->'alist->'blist->'clistmap2f[a1;...;an][b1;...;bn] is [fa1b1;...;fanbn] .
RaisesInvalid_argument if the two lists are determined to have different lengths.
valrev_map2 : ('a->'b->'c)->'alist->'blist->'clistrev_map2fl1l2 gives the same result as List.rev(List.map2fl1l2) , but is more efficient.
valfold_left2 : ('acc->'a->'b->'acc)->'acc->'alist->'blist->'accfold_left2finit[a1;...;an][b1;...;bn] is f(...(f(finita1b1)a2b2)...)anbn .
RaisesInvalid_argument if the two lists are determined to have different lengths.
valfold_right2 : ('a->'b->'acc->'acc)->'alist->'blist->'acc->'accfold_right2f[a1;...;an][b1;...;bn]init is fa1b1(fa2b2(...(fanbninit)...)) .
RaisesInvalid_argument if the two lists are determined to have different lengths. Not tail-recursive.
Listscanningvalfor_all : ('a->bool)->'alist->boolfor_allf[a1;...;an] checks if all elements of the list satisfy the predicate f . That is, it returns
(fa1)&&(fa2)&&...&&(fan) for a non-empty list and true if the list is empty.
valexists : ('a->bool)->'alist->boolexistsf[a1;...;an] checks if at least one element of the list satisfies the predicate f . That is, it
returns (fa1)||(fa2)||...||(fan) for a non-empty list and false if the list is empty.
valfor_all2 : ('a->'b->bool)->'alist->'blist->bool
Same as List.for_all , but for a two-argument predicate.
RaisesInvalid_argument if the two lists are determined to have different lengths.
valexists2 : ('a->'b->bool)->'alist->'blist->bool
Same as List.exists , but for a two-argument predicate.
RaisesInvalid_argument if the two lists are determined to have different lengths.
valmem : 'a->'alist->boolmemaset is true if and only if a is equal to an element of set .
valmemq : 'a->'alist->bool
Same as List.mem , but uses physical equality instead of structural equality to compare list elements.
Listsearchingvalfind : ('a->bool)->'alist->'afindfl returns the first element of the list l that satisfies the predicate f .
RaisesNot_found if there is no value that satisfies f in the list l .
valfind_opt : ('a->bool)->'alist->'aoptionfindfl returns the first element of the list l that satisfies the predicate f . Returns None if there
is no value that satisfies f in the list l .
Since 4.05
valfind_index : ('a->bool)->'alist->intoptionfind_indexfxs returns Somei , where i is the index of the first element of the list xs that satisfies
fx , if there is such an element.
It returns None if there is no such element.
Since 5.1
valfind_map : ('a->'boption)->'alist->'boptionfind_mapfl applies f to the elements of l in order, and returns the first result of the form Somev ,
or None if none exist.
Since 4.10
valfind_mapi : (int->'a->'boption)->'alist->'boption
Same as find_map , but the predicate is applied to the index of the element as first argument (counting
from 0), and the element itself as second argument.
Since 5.1
valfilter : ('a->bool)->'alist->'alistfilterfl returns all the elements of the list l that satisfy the predicate f . The order of the
elements in the input list is preserved.
valfind_all : ('a->bool)->'alist->'alistfind_all is another name for List.filter .
valfilteri : (int->'a->bool)->'alist->'alist
Same as List.filter , but the predicate is applied to the index of the element as first argument
(counting from 0), and the element itself as second argument.
Since 4.11
Listmanipulationvaltake : int->'alist->'alisttakenl returns the prefix of l of length n , or a copy of l if n>lengthl .
n must be nonnegative.
Since 5.3
RaisesInvalid_argument if n is negative.
valdrop : int->'alist->'alistdropnl returns the suffix of l after n elements, or [] if n>lengthl .
n must be nonnegative.
Since 5.3
RaisesInvalid_argument if n is negative.
valtake_while : ('a->bool)->'alist->'alisttake_whilepl is the longest (possibly empty) prefix of l containing only elements that satisfy p .
Since 5.3
valdrop_while : ('a->bool)->'alist->'alistdrop_whilepl is the longest (possibly empty) suffix of l starting at the first element that does not
satisfy p .
Since 5.3
valpartition : ('a->bool)->'alist->'alist*'alistpartitionfl returns a pair of lists (l1,l2) , where l1 is the list of all the elements of l that
satisfy the predicate f , and l2 is the list of all the elements of l that do not satisfy f . The order
of the elements in the input list is preserved.
valpartition_map : ('a->('b,'c)Either.t)->'alist->'blist*'clistpartition_mapfl returns a pair of lists (l1,l2) such that, for each element x of the input list l :
-if fx is Lefty1 , then y1 is in l1 , and
-if fx is Righty2 , then y2 is in l2 .
The output elements are included in l1 and l2 in the same relative order as the corresponding input
elements in l .
In particular, partition_map(funx->iffxthenLeftxelseRightx)l is equivalent to partitionfl
.
Since 4.12
Associationlistsvalassoc : 'a->('a*'b)list->'bassocal returns the value associated with key a in the list of pairs l . That is, assoca[...;(a,b);...]=b if (a,b) is the leftmost binding of a in list l .
RaisesNot_found if there is no value associated with a in the list l .
valassoc_opt : 'a->('a*'b)list->'boptionassoc_optal returns the value associated with key a in the list of pairs l . That is, assoc_opta[...;(a,b);...]=Someb if (a,b) is the leftmost binding of a in list l . Returns None if there is no
value associated with a in the list l .
Since 4.05
valassq : 'a->('a*'b)list->'b
Same as List.assoc , but uses physical equality instead of structural equality to compare keys.
valassq_opt : 'a->('a*'b)list->'boption
Same as List.assoc_opt , but uses physical equality instead of structural equality to compare keys.
Since 4.05
valmem_assoc : 'a->('a*'b)list->bool
Same as List.assoc , but simply return true if a binding exists, and false if no bindings exist for the
given key.
valmem_assq : 'a->('a*'b)list->bool
Same as List.mem_assoc , but uses physical equality instead of structural equality to compare keys.
valremove_assoc : 'a->('a*'b)list->('a*'b)listremove_assocal returns the list of pairs l without the first pair with key a , if any. Not
tail-recursive.
valremove_assq : 'a->('a*'b)list->('a*'b)list
Same as List.remove_assoc , but uses physical equality instead of structural equality to compare keys.
Not tail-recursive.
Listsofpairsvalsplit : ('a*'b)list->'alist*'blist
Transform a list of pairs into a pair of lists: split[(a1,b1);...;(an,bn)] is ([a1;...;an],[b1;...;bn]) . Not tail-recursive.
valcombine : 'alist->'blist->('a*'b)list
Transform a pair of lists into a list of pairs: combine[a1;...;an][b1;...;bn] is [(a1,b1);...;(an,bn)] .
RaisesInvalid_argument if the two lists have different lengths. Not tail-recursive.
Sortingvalsort : ('a->'a->int)->'alist->'alist
Sort a list in increasing order according to a comparison function. The comparison function must return 0
if its arguments compare as equal, a positive integer if the first is greater, and a negative integer if
the first is smaller (see Array.sort for a complete specification). For example, compare is a suitable
comparison function. The resulting list is sorted in increasing order. List.sort is guaranteed to run
in constant heap space (in addition to the size of the result list) and logarithmic stack space.
The current implementation uses Merge Sort. It runs in constant heap space and logarithmic stack space.
valstable_sort : ('a->'a->int)->'alist->'alist
Same as List.sort , but the sorting algorithm is guaranteed to be stable (i.e. elements that compare
equal are kept in their original order).
The current implementation uses Merge Sort. It runs in constant heap space and logarithmic stack space.
valfast_sort : ('a->'a->int)->'alist->'alist
Same as List.sort or List.stable_sort , whichever is faster on typical input.
valsort_uniq : ('a->'a->int)->'alist->'alist
Same as List.sort , but also remove duplicates.
Since 4.02 (4.03 in ListLabels)
valmerge : ('a->'a->int)->'alist->'alist->'alist
Merge two lists: Assuming that l1 and l2 are sorted according to the comparison function cmp , mergecmpl1l2 will return a sorted list containing all the elements of l1 and l2 . If several elements compare
equal, the elements of l1 will be before the elements of l2 . Not tail-recursive (sum of the lengths of
the arguments).
ListsandSequencesvalto_seq : 'alist->'aSeq.t
Iterate on the list.
Since 4.07
valof_seq : 'aSeq.t->'alist
Create a list from a sequence.
Since 4.07
OCamldoc 2025-06-12 List(3o)
Install Now
PNG Icons
