Module CCList
Complements to list
type 'a sequence
= ('a -> unit) -> unit
type 'a gen
= unit -> 'a option
type 'a klist
= unit -> [ `Nil | `Cons of 'a * 'a klist ]
type 'a printer
= Stdlib.Format.formatter -> 'a -> unit
type 'a random_gen
= Stdlib.Random.State.t -> 'a
include module type of Stdlib.List
val length : 'a list -> int
val compare_lengths : 'a list -> 'b list -> int
val compare_length_with : 'a list -> int -> int
val cons : 'a -> 'a list -> 'a list
val hd : 'a list -> 'a
val tl : 'a list -> 'a list
val nth : 'a list -> int -> 'a
val nth_opt : 'a list -> int -> 'a option
val rev : 'a list -> 'a list
val init : int -> (int -> 'a) -> 'a list
val append : 'a list -> 'a list -> 'a list
val rev_append : 'a list -> 'a list -> 'a list
val concat : 'a list list -> 'a list
val flatten : 'a list list -> 'a list
val iter : ('a -> unit) -> 'a list -> unit
val iteri : (int -> 'a -> unit) -> 'a list -> unit
val map : ('a -> 'b) -> 'a list -> 'b list
val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
val rev_map : ('a -> 'b) -> 'a list -> 'b list
val filter_map : ('a -> 'b option) -> 'a list -> 'b list
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a
val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c
val for_all : ('a -> bool) -> 'a list -> bool
val exists : ('a -> bool) -> 'a list -> bool
val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
val mem : 'a -> 'a list -> bool
val memq : 'a -> 'a list -> bool
val find : ('a -> bool) -> 'a list -> 'a
val find_opt : ('a -> bool) -> 'a list -> 'a option
val filter : ('a -> bool) -> 'a list -> 'a list
val find_all : ('a -> bool) -> 'a list -> 'a list
val partition : ('a -> bool) -> 'a list -> 'a list * 'a list
val assoc : 'a -> ('a * 'b) list -> 'b
val assoc_opt : 'a -> ('a * 'b) list -> 'b option
val assq : 'a -> ('a * 'b) list -> 'b
val assq_opt : 'a -> ('a * 'b) list -> 'b option
val mem_assoc : 'a -> ('a * 'b) list -> bool
val mem_assq : 'a -> ('a * 'b) list -> bool
val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
val split : ('a * 'b) list -> 'a list * 'b list
val combine : 'a list -> 'b list -> ('a * 'b) list
val sort : ('a -> 'a -> int) -> 'a list -> 'a list
val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list
val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list
val sort_uniq : ('a -> 'a -> int) -> 'a list -> 'a list
val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
val to_seq : 'a list -> 'a Stdlib.Seq.t
val of_seq : 'a Stdlib.Seq.t -> 'a list
val empty : 'a t
empty
is[]
.
val is_empty : _ t -> bool
is_empty l
returnstrue
iffl = []
.- since
- 0.11
val cons_maybe : 'a option -> 'a t -> 'a t
cons_maybe (Some x) l
isx :: l
.cons_maybe None l
isl
.- since
- 0.13
val filter : ('a -> bool) -> 'a t -> 'a t
Safe version of
List
.filter.filter p l
returns all the elements of the listl
that satisfy the predicatep
. The order of the elements in the input list is preserved.
val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
Safe version of
fold_right
.fold_right f [a1; ...; an] b
isf a1 (f a2 (... (f an b) ...))
.
val fold_while : ('a -> 'b -> 'a * [ `Stop | `Continue ]) -> 'a -> 'b t -> 'a
Fold until a stop condition via
('a, `Stop)
is indicated by the accumulator.- since
- 0.8
val fold_map : ('acc -> 'a -> 'acc * 'b) -> 'acc -> 'a list -> 'acc * 'b list
fold_map f init l
is afold_left
-like function, but it also maps the list to another list.- since
- 0.14
val scan_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a list -> 'acc list
scan_left f init l
returns the list[init; f init x0; f (f init x0) x1; ...]
wherex0
,x1
, etc. are the elements ofl
.- since
- 1.2, but only
- since
- 2.2 with labels
val fold_map2 : ('acc -> 'a -> 'b -> 'acc * 'c) -> 'acc -> 'a list -> 'b list -> 'acc * 'c list
fold_map2
is tofold_map
whatList.map2
is toList.map
.- raises Invalid_argument
if the lists do not have the same length.
- since
- 0.16
val fold_filter_map : ('acc -> 'a -> 'acc * 'b option) -> 'acc -> 'a list -> 'acc * 'b list
fold_filter_map f init l
is afold_left
-like function, but also generates a list of output in a way similar tofilter_map
.- since
- 0.17
val fold_flat_map : ('acc -> 'a -> 'acc * 'b list) -> 'acc -> 'a list -> 'acc * 'b list
fold_flat_map f acc l
is afold_left
-like function, but it also maps the list to a list of lists that is thenflatten
'd.- since
- 0.14
val count : ('a -> bool) -> 'a list -> int
count p l
counts how many elements ofl
satisfy predicatep
.- since
- 1.5, but only
- since
- 2.2 with labels
val init : int -> (int -> 'a) -> 'a t
init len f
isf 0; f 1; ...; f (len-1)
.- raises Invalid_argument
if len < 0.
- since
- 0.6
val combine : 'a list -> 'b list -> ('a * 'b) list
Like
List
.combine but tail-recursive. Transform a pair of lists into a list of pairs:combine [a1; ...; an] [b1; ...; bn]
is[(a1,b1); ...; (an,bn)]
.- raises Invalid_argument
if the lists have distinct lengths.
- since
- 1.2, but only
- since
- 2.2 with labels
val combine_gen : 'a list -> 'b list -> ('a * 'b) gen
Lazy version of
combine
. Unlikecombine
, it does not fail if the lists have different lengths; instead, the output has as many pairs as the smallest input list.- since
- 1.2, but only
- since
- 2.2 with labels
val split : ('a * 'b) t -> 'a t * 'b t
A tail-recursive version of
List
.split. Transform a list of pairs into a pair of lists:split [(a1,b1); ...; (an,bn)]
is([a1; ...; an], [b1; ...; bn])
.- since
- 1.2, but only
- since
- 2.2 with labels
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val compare_lengths : 'a t -> 'b t -> int
Equivalent to
compare (length l1) (length l2)
but more efficient. Compare the lengths of two lists.- since
- 1.5, but only
- since
- 2.2 with labels
val compare_length_with : 'a t -> int -> int
Equivalent to
compare (length l) x
but more efficient. Compare the length of a list to an integer.- since
- 1.5, but only
- since
- 2.2 with labels
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
val flat_map : ('a -> 'b t) -> 'a t -> 'b t
Map and flatten at the same time (safe). Evaluation order is not guaranteed.
val product : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
Cartesian product of the two lists, with the given combinator.
val cartesian_product : 'a t t -> 'a t t
Produce the cartesian product of this list of lists, by returning all the ways of picking one element per sublist. NOTE the order of the returned list is unspecified. For example:
# cartesian_product [[1;2];[3];[4;5;6]] |> sort = [[1;3;4];[1;3;5];[1;3;6];[2;3;4];[2;3;5];[2;3;6]];; # cartesian_product [[1;2];[];[4;5;6]] = [];; # cartesian_product [[1;2];[3];[4];[5];[6]] |> sort = [[1;3;4;5;6];[2;3;4;5;6]];;
invariant:
cartesian_product l = map_product id l
.- since
- 1.2, but only
- since
- 2.2 with labels
val map_product_l : ('a -> 'b list) -> 'a list -> 'b list list
map_product_l f l
maps each element ofl
to a list of objects of type'b
usingf
. We obtain[l1;l2;...;ln]
wherelength l=n
andli : 'b list
. Then, it returns all the ways of picking exactly one element perli
.- since
- 1.2, but only
- since
- 2.2 with labels
val diagonal : 'a t -> ('a * 'a) t
All pairs of distinct positions of the list.
list_diagonal l
will return the list ofList.nth i l, List.nth j l
ifi < j
.
val partition_map : ('a -> [< `Left of 'b | `Right of 'c | `Drop ]) -> 'a list -> 'b list * 'c list
partition_map f l
mapsf
onl
and gather results in lists:- if
f x = `Left y
, addsy
to the first list. - if
f x = `Right z
, addsz
to the second list. - if
f x = `Drop
, ignoresx
.
- since
- 0.11
- if
val group_by : ?hash:('a -> int) -> ?eq:('a -> 'a -> bool) -> 'a t -> 'a list t
Group equal elements, regardless of their order of appearance. precondition: for any
x
andy
, ifeq x y
thenhash x=hash y
must hold.- since
- 2.3
val join : join_row:('a -> 'b -> 'c option) -> 'a t -> 'b t -> 'c t
join ~join_row a b
combines every element ofa
with every element ofb
usingjoin_row
. Ifjoin_row
returns None, then the two elements do not combine. Assume thatb
allows for multiple iterations.- since
- 2.3
val join_by : ?eq:('key -> 'key -> bool) -> ?hash:('key -> int) -> ('a -> 'key) -> ('b -> 'key) -> merge:('key -> 'a -> 'b -> 'c option) -> 'a t -> 'b t -> 'c t
join key1 key2 ~merge
is a binary operation that takes two sequencesa
andb
, projects their elements resp. withkey1
andkey2
, and combine values(x,y)
from(a,b)
with the samekey
usingmerge
. Ifmerge
returnsNone
, the combination of values is discarded. precondition: for anyx
andy
, ifeq x y
thenhash x=hash y
must hold.- since
- 2.3
val join_all_by : ?eq:('key -> 'key -> bool) -> ?hash:('key -> int) -> ('a -> 'key) -> ('b -> 'key) -> merge:('key -> 'a list -> 'b list -> 'c option) -> 'a t -> 'b t -> 'c t
join_all_by key1 key2 ~merge
is a binary operation that takes two sequencesa
andb
, projects their elements resp. withkey1
andkey2
, and, for each keyk
occurring in at least one of them:- compute the list
l1
of elements ofa
that map tok
- compute the list
l2
of elements ofb
that map tok
- call
merge k l1 l2
. Ifmerge
returnsNone
, the combination of values is discarded, otherwise it returnsSome c
andc
is inserted in the result.
- since
- 2.3
- compute the list
val group_join_by : ?eq:('a -> 'a -> bool) -> ?hash:('a -> int) -> ('b -> 'a) -> 'a t -> 'b t -> ('a * 'b list) t
group_join_by key2
associates to every elementx
of the first sequence, all the elementsy
of the second sequence such thateq x (key y)
. Elements of the first sequences without corresponding values in the second one are mapped to[]
precondition: for anyx
andy
, ifeq x y
thenhash x=hash y
must hold.- since
- 2.3
val sublists_of_len : ?last:('a list -> 'a list option) -> ?offset:int -> int -> 'a list -> 'a list list
sublists_of_len n l
returns sub-lists ofl
that have lengthn
. By default, these sub-lists are non overlapping:sublists_of_len 2 [1;2;3;4;5;6]
returns[1;2]; [3;4]; [5;6]
.Examples:
sublists_of_len 2 [1;2;3;4;5;6] = [[1;2]; [3;4]; [5;6]]
.sublists_of_len 2 ~offset:3 [1;2;3;4;5;6] = [1;2];[4;5]
.sublists_of_len 3 ~last:CCOpt.return [1;2;3;4] = [1;2;3];[4]
.sublists_of_len 2 [1;2;3;4;5] = [[1;2]; [3;4]]
.
- parameter offset
the number of elements skipped between two consecutive sub-lists. By default it is
n
. Ifoffset < n
, the sub-lists will overlap; ifoffset > n
, some elements will not appear at all.
- parameter last
if provided and the last group of elements
g
is such thatlength g < n
,last g
is called. Iflast g = Some g'
,g'
is appended; otherwiseg
is dropped. Iflast = CCOpt.return
, it will simply keep the last group. By default,last = fun _ -> None
, i.e. the last group is dropped if shorter thann
.
- raises Invalid_argument
if
offset <= 0
orn <= 0
. SeeCCList.sublists_of_len
for more details.
- since
- 1.0, but only
- since
- 1.5 with labels
val intersperse : 'a -> 'a list -> 'a list
Insert the first argument between every element of the list.
- since
- 2.1, but only
- since
- 2.2 with labels
val interleave : 'a list -> 'a list -> 'a list
interleave [x1…xn] [y1…ym]
isx1,y1,x2,y2,…
and finishes with the suffix of the longest list.- since
- 2.1, but only
- since
- 2.2 with labels
val pure : 'a -> 'a t
pure
isreturn
.
val return : 'a -> 'a t
return x
isx
.
val hd_tl : 'a t -> 'a * 'a t
hd_tl (x :: l)
returnshd, l
.- raises Failure
if the list is empty.
- since
- 0.16
val take_drop : int -> 'a t -> 'a t * 'a t
take_drop n l
returnsl1, l2
such thatl1 @ l2 = l
andlength l1 = min (length l) n
.
val take_while : ('a -> bool) -> 'a t -> 'a t
take_while f l
returns the longest prefix ofl
for whichf
istrue
.- since
- 0.13
val drop_while : ('a -> bool) -> 'a t -> 'a t
drop_while f l
drops the longest prefix ofl
for whichf
istrue
.- since
- 0.13
val take_drop_while : ('a -> bool) -> 'a t -> 'a t * 'a t
take_drop_while p l
=take_while p l, drop_while p l
.- since
- 1.2, but only
- since
- 2.2 with labels
val last : int -> 'a t -> 'a t
last n l
takes the lastn
elements ofl
(or less ifl
doesn't have that many elements).
val head_opt : 'a t -> 'a option
First element.
- since
- 0.20
val last_opt : 'a t -> 'a option
Last element.
- since
- 0.20
val find_pred : ('a -> bool) -> 'a t -> 'a option
find_pred p l
finds the first element ofl
that satisfiesp
, or returnsNone
if no element satisfiesp
.- since
- 0.11
val find_opt : ('a -> bool) -> 'a t -> 'a option
Safe version of
find
.- since
- 1.5, but only
- since
- 2.2 with labels
val find_pred_exn : ('a -> bool) -> 'a t -> 'a
Unsafe version of
find_pred
.- raises Not_found
if no such element is found.
- since
- 0.11
val find_map : ('a -> 'b option) -> 'a t -> 'b option
find_map f l
traversesl
, applyingf
to each element. If for some elementx
,f x = Some y
, thenSome y
is returned. Otherwise the call returnsNone
.- since
- 0.11
val find_mapi : (int -> 'a -> 'b option) -> 'a t -> 'b option
Like
find_map
, but also pass the index to the predicate function.- since
- 0.11
val find_idx : ('a -> bool) -> 'a t -> (int * 'a) option
find_idx p x
returnsSome (i,x)
wherex
is thei
-th element ofl
, andp x
holds. Otherwise returnsNone
.
val remove : eq:('a -> 'a -> bool) -> key:'a -> 'a t -> 'a t
remove ~key l
removes every instance ofkey
froml
. Tail-recursive.- parameter eq
equality function.
- since
- 0.11
val filter_map : ('a -> 'b option) -> 'a t -> 'b t
filter_map f l
is the sublist ofl
containing only elements for whichf
returnsSome e
. Map and remove elements at the same time.
val keep_some : 'a option t -> 'a t
keep_some l
retains only elements of the formSome x
. Likefilter_map CCFun.id
.- since
- 1.3, but only
- since
- 2.2 with labels
val keep_ok : ('a, _) Result.result t -> 'a t
keep_ok l
retains only elements of the formOk x
.- since
- 1.3, but only
- since
- 2.2 with labels
val all_some : 'a option t -> 'a t option
all_some l
returnsSome l'
if all elements ofl
are of the formSome x
, orNone
otherwise.- since
- 1.3, but only
- since
- 2.2 with labels
val all_ok : ('a, 'err) Result.result t -> ('a t, 'err) Result.result
all_ok l
returnsOk l'
if all elements ofl
are of the formOk x
, orError e
otherwise (with the first error met).- since
- 1.3, but only
- since
- 2.2 with labels
val sorted_merge : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
Merge elements from both sorted list.
val sort_uniq : cmp:('a -> 'a -> int) -> 'a list -> 'a list
Sort the list and remove duplicate elements.
val sorted_merge_uniq : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
sorted_merge_uniq l1 l2
merges the sorted listsl1
andl2
and removes duplicates.- since
- 0.10
val is_sorted : cmp:('a -> 'a -> int) -> 'a list -> bool
is_sorted l
returnstrue
iffl
is sorted (according to given order).- parameter cmp
the comparison function (default
Pervasives.compare
).
- since
- 0.17
val sorted_insert : cmp:('a -> 'a -> int) -> ?uniq:bool -> 'a -> 'a list -> 'a list
sorted_insert x l
insertsx
intol
such that, ifl
was sorted, thensorted_insert x l
is sorted too.- parameter uniq
if true and
x
is already in sorted position inl
, thenx
is not duplicated. Defaultfalse
(x
will be inserted in any case).
- since
- 0.17
val uniq_succ : eq:('a -> 'a -> bool) -> 'a list -> 'a list
uniq_succ l
removes duplicate elements that occur one next to the other. Examples:uniq_succ [1;2;1] = [1;2;1]
.uniq_succ [1;1;2] = [1;2]
.- since
- 0.10
val group_succ : eq:('a -> 'a -> bool) -> 'a list -> 'a list list
group_succ ~eq l
groups together consecutive elements that are equal according toeq
.- since
- 0.11
Indices
val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
Like
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.
val iteri : (int -> 'a -> unit) -> 'a t -> unit
Like
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.
val iteri2 : (int -> 'a -> 'b -> unit) -> 'a t -> 'b t -> unit
Iter on two lists.
- raises Invalid_argument
when lists do not have the same length.
- since
- 2.0, but only
- since
- 2.2 with labels
val foldi : ('b -> int -> 'a -> 'b) -> 'b -> 'a t -> 'b
Like
fold
but it also passes in the index of each element to the folded function. Tail-recursive.
val foldi2 : ('c -> int -> 'a -> 'b -> 'c) -> 'c -> 'a t -> 'b t -> 'c
Fold on two lists, with index.
- raises Invalid_argument
when lists do not have the same length.
- since
- 2.0, but only
- since
- 2.2 with labels
val get_at_idx : int -> 'a t -> 'a option
Get by index in the list. If the index is negative, it will get element starting from the end of the list.
val nth_opt : 'a t -> int -> 'a option
Safe version of
nth
.- raises Invalid_argument
if the int is negative.
- since
- 1.5, but only
- since
- 2.2 with labels
val get_at_idx_exn : int -> 'a t -> 'a
Get the i-th element, or
- raises Not_found
if the index is invalid. If the index is negative, it will get element starting from the end of the list.
val set_at_idx : int -> 'a -> 'a t -> 'a t
Set i-th element (removes the old one), or does nothing if index is too high. If the index is negative, it will set element starting from the end of the list.
Set Operators
Those operations maintain the invariant that the list does not contain duplicates (if it already satisfies it).
val add_nodup : eq:('a -> 'a -> bool) -> 'a -> 'a t -> 'a t
add_nodup x set
addsx
toset
if it was not already present. Linear time.- since
- 0.11
val remove_one : eq:('a -> 'a -> bool) -> 'a -> 'a t -> 'a t
remove_one x set
removes one occurrence ofx
fromset
. Linear time.- since
- 0.11
val mem : eq:('a -> 'a -> bool) -> 'a -> 'a t -> bool
Membership to the list. Linear time.
val uniq : eq:('a -> 'a -> bool) -> 'a t -> 'a t
Remove duplicates w.r.t the equality predicate. Complexity is quadratic in the length of the list, but the order of elements is preserved. If you wish for a faster de-duplication but do not care about the order, use
sort_uniq
.
Other Constructors
val range_by : step:int -> int -> int -> int t
range_by ~step i j
iterates on integers fromi
toj
included, where the difference between successive elements isstep
. Use a negativestep
for a decreasing list.- raises Invalid_argument
if
step=0
.
- since
- 0.18
val range : int -> int -> int t
range i j
iterates on integers fromi
toj
included. It works both for decreasing and increasing ranges.
val range' : int -> int -> int t
Like
range
but the second bound is excluded. For instancerange' 0 5 = [0;1;2;3;4]
.
val (--) : int -> int -> int t
Infix alias for
range
.
val (--^) : int -> int -> int t
Infix alias for
range'
.- since
- 0.17
val replicate : int -> 'a -> 'a t
Replicate the given element
n
times.
Association Lists
module Assoc : sig ... end
val assoc : eq:('a -> 'a -> bool) -> 'a -> ('a * 'b) t -> 'b
Like
Assoc.get_exn
.- since
- 2.0
val assoc_opt : eq:('a -> 'a -> bool) -> 'a -> ('a * 'b) t -> 'b option
Like
Assoc.get
.- since
- 1.5, but only
- since
- 2.0 with labels
val assq_opt : 'a -> ('a * 'b) t -> 'b option
Safe version of
assq
.- since
- 1.5, but only
- since
- 2.0 with labels
val mem_assoc : eq:('a -> 'a -> bool) -> 'a -> ('a * _) t -> bool
Like
Assoc.mem
.- since
- 2.0
References on Lists
- since
- 0.3.3
module Ref : sig ... end
module type MONAD = sig ... end
Conversions
val random : 'a random_gen -> 'a t random_gen
val random_non_empty : 'a random_gen -> 'a t random_gen
val random_len : int -> 'a random_gen -> 'a t random_gen
val random_choose : 'a t -> 'a random_gen
Randomly choose an element in the list.
- raises Not_found
if the list is empty.
val random_sequence : 'a random_gen t -> 'a t random_gen
val to_seq : 'a t -> 'a sequence
Return a
sequence
of the elements of the list.
val of_seq : 'a sequence -> 'a t
Build a list from a given
sequence
. In the result, elements appear in the same order as they did in the sourcesequence
.
Infix Operators
It is convenient to open CCList
.Infix to access the infix operators without cluttering the scope too much.
- since
- 0.16
module Infix : sig ... end