Module Hash_queue.List

module List: Core_list

type 'a t = 'a list

include Binable.S1

include Container.S1

include Sexpable.S1

include Monad.S

val nth : 'a t -> int -> 'a option

val nth_exn : 'a t -> int -> 'a

Return the n-th element of the given list. The first element (head of the list) is at position 0. Raise Failure "nth" if the list is too short. Raise Invalid_argument "List.nth" if n is negative.

val rev : 'a t -> 'a t

List reversal.

val rev_append : 'a t -> 'a t -> 'a t

List.rev_append l1 l2 reverses l1 and concatenates it to l2. This is equivalent to (List.rev l1) @ l2, but rev_append is more efficient.

val unordered_append : 'a t -> 'a t -> 'a t

val rev_map : f:('a -> 'b) -> 'a t -> 'b t

List.rev_map f l gives the same result as List.rev (ListLabels.map f l), but is more efficient.

val fold_left : 'a t -> init:'b -> f:('b -> 'a -> 'b) -> 'b

val iter2_exn : 'a t -> 'b t -> f:('a -> 'b -> unit) -> unit

List.iter2_exn f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f an bn. Raise Invalid_argument if the two lists have different lengths.

val rev_map2_exn : 'a t -> 'b t -> f:('a -> 'b -> 'c) -> 'c t

List.rev_map2_exn f l1 l2 gives the same result as List.rev (List.map2_exn f l1 l2), but is more efficient.

val fold2_exn : 'a t -> 'b t -> init:'c -> f:('c -> 'a -> 'b -> 'c) -> 'c

List.fold2_exn f a [b1; ...; bn] [c1; ...; cn] is f (... (f (f a b1 c1) b2 c2) ...) bn cn. Raise Invalid_argument if the two lists have different lengths.

val for_all2_exn : 'a t -> 'b t -> f:('a -> 'b -> bool) -> bool

Same as List.for_all, but for a two-argument predicate. Raise Invalid_argument if the two lists have different lengths.

val exists2_exn : 'a t -> 'b t -> f:('a -> 'b -> bool) -> bool

Same as List.exists, but for a two-argument predicate. Raise Invalid_argument if the end of one list is reached before the end of the other.

val mem : 'a -> set:'a t -> bool

mem a l is true if and only if a is equal to an element of l.

val memq : 'a -> set:'a t -> bool

Same as List.mem, but uses physical equality instead of structural equality to compare list elements.

val filter : f:('a -> bool) -> 'a t -> 'a t

filter p l returns all the elements of the list l that satisfy the predicate p. The order of the elements in the input list is preserved.

val rev_filter : f:('a -> bool) -> 'a t -> 'a t

Like filter, but reverses the order of the input list

val filteri : 'a t -> f:(int -> 'a -> bool) -> 'a t

val find_all : f:('a -> bool) -> 'a t -> 'a t

find_all is another name for List.filter.

val partition : 'a t -> f:('a -> bool) -> 'a t * 'a t

partition p l returns a pair of lists (l1, l2), where l1 is the list of all the elements of l that satisfy the predicate p, and l2 is the list of all the elements of l that do not satisfy p. The order of the elements in the input list is preserved.

val sort : cmp:('a -> 'a -> int) -> 'a t -> 'a t

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, Pervasives.compare is a suitable comparison function.

The current implementation uses Merge Sort. It runs in constant heap space and logarithmic stack space.

Presently, the sort is stable, meaning that two equal elements in the input will be in the same order in the output.

val stable_sort : cmp:('a -> 'a -> int) -> 'a t -> 'a t

Same as sort, but guaranteed to be stable

val merge : 'a t -> 'a t -> cmp:('a -> 'a -> int) -> 'a t

Merge two lists: Assuming that l1 and l2 are sorted according to the comparison function cmp, merge cmp l1 l2 will return a sorted list containting all the elements of l1 and l2. If several elements compare equal, the elements of l1 will be before the elements of l2.

val hd : 'a t -> 'a option

val tl : 'a t -> 'a t option

val hd_exn : 'a t -> 'a

Return the first element of the given list. Raise Failure "hd" if the list is empty.

val tl_exn : 'a t -> 'a t

Return the given list without its first element. Raise Failure "tl" if the list is empty.

val findi : 'a t -> f:(int -> 'a -> bool) -> (int * 'a) option

find_map t f applies f to each element of t until it finds * f a = Some b, at which point it returns Some b. If there is no such * element, find_map returns None.

val find_map : 'a t -> f:('a -> 'b option) -> 'b option

val find_exn : 'a t -> f:('a -> bool) -> 'a

find_exn t ~f returns the first element of t that satisfies f. It raises Not_found if there is no such element.

Tail-recursive implementations of standard List operations

val append : 'a t -> 'a t -> 'a t

E.g. append [1; 2] [3; 4; 5] is [1; 2; 3; 4; 5]

val map : 'a t -> f:('a -> 'b) -> 'b t

List.map f [a1; ...; an] applies function f to a1, ..., an, and builds the list [f a1; ...; f an] with the results returned by f.

val concat_map : 'a t -> f:('a -> 'b t) -> 'b t

concat_map t ~f is concat (map t ~f), except that there * is no guarantee about the order in which f is applied to the elements of * t.

val map2_exn : 'a t -> 'b t -> f:('a -> 'b -> 'c) -> 'c t

List.map2_exn f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn]. Raise Invalid_argument if the two lists have different lengths.

val rev_map3_exn : 'a t ->
       'b t ->
       'c t -> f:('a -> 'b -> 'c -> 'd) -> 'd t

val map3_exn : 'a t ->
       'b t ->
       'c t -> f:('a -> 'b -> 'c -> 'd) -> 'd t

val rev_map_append : 'a t -> 'b t -> f:('a -> 'b) -> 'b t

rev_map_append ~f l1 l2 reverses l1 mapping f over each element, and appends the result to the front of l2.

val fold_right : 'a t -> f:('a -> 'b -> 'b) -> init:'b -> 'b

List.fold_right f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...)).

val split : ('a * 'b) t -> 'a t * 'b t

Transform a list of pairs into a pair of lists: split [(a1,b1); ...; (an,bn)] is ([a1; ...; an], [b1; ...; bn]).

val combine_exn : 'a t -> 'b t -> ('a * 'b) t

Transform a pair of lists into a list of pairs: combine [a1; ...; an] [b1; ...; bn] is [(a1,b1); ...; (an,bn)]. Raise Invalid_argument if the two lists have different lengths.

val mapi : 'a t -> f:(int -> 'a -> 'b) -> 'b t

mapi is just like map, but it also passes in the index of each element as the first argument to the mapped function. Tail-recursive.

val rev_mapi : 'a t -> f:(int -> 'a -> 'b) -> 'b t

val iteri : 'a t -> f:(int -> 'a -> unit) -> unit

iteri is just like iter, but it also passes in the index of each element as the first argument to the iter'd function. Tail-recursive.

val foldi : 'a t -> f:(int -> 'b -> 'a -> 'b) -> init:'b -> 'b

foldi is just like fold, but it also passes in the index of each element as the first argument to the folded function. Tail-recursive.

val reduce_exn : 'a t -> f:('a -> 'a -> 'a) -> 'a

reduce f [a1; ...; an] is f (... (f (f a1 a2) a3) ...) an. It fails on the empty list. Tail recursive.

val reduce : 'a t -> f:('a -> 'a -> 'a) -> 'a option

val group : 'a t -> break:('a -> 'a -> bool) -> 'a t t

group l ~break returns a list of lists (i.e., groups) whose concatenation is equal to the original list. Each group is broken where break returns true on a pair of successive elements.

Example

group ~break:(<>) 'M';'i';'s';'s';'i';'s';'s';'i';'p';'p';'i' ->

['M'];['i'];['s';'s'];['i'];['s';'s'];['i'];['p';'p'];['i']

val groupi : 'a t ->
       break:(int -> 'a -> 'a -> bool) -> 'a t t

This is just like group, except that you get the index in the original list of the current element along with the two elements.

Example, group the chars of Mississippi into triples

groupi ~break:(fun i _ _ -> i mod 3 = 0) 'M';'i';'s';'s';'i';'s';'s';'i';'p';'p';'i' ->

['M'; 'i'; 's']; ['s'; 'i'; 's']; ['s'; 'i'; 'p']; ['p'; 'i']

val last : 'a t -> 'a option

The final element of a list. The _exn version raises Invalid_argument on the empty list.

val last_exn : 'a t -> 'a

val dedup : ?compare:('a -> 'a -> int) -> 'a t -> 'a t

dedup (de-duplicate). The same list with duplicates removed, but the order is not guaranteed.

val stable_dedup : 'a t -> 'a t

stable_dedup Same as dedup but maintains the order of the list and doesn't allow compare function to be specified (uses set membership).

val contains_dup : ?compare:('a -> 'a -> int) -> 'a t -> bool

contains_dup True if there are any two elements in the list which are the same.

val find_a_dup : ?compare:('a -> 'a -> int) -> 'a t -> 'a option

find_a_dup returns a duplicate from the list (no guarantees about which duplicate you get), or None if there are no dups.

exception Duplicate_found of (unit -> Sexplib.Sexp.t) * string

val exn_if_dup : ?compare:('a -> 'a -> int) ->
       ?context:string -> 'a t -> to_sexp:('a -> Sexplib.Sexp.t) -> unit

exn_if_dup ?compare ?context t ~to_sexp will run find_a_dup on t, and raise Duplicate_found if a duplicate is found. The context is the second argument of the exception

val count : 'a t -> f:('a -> bool) -> int

count f l is the number of elements in l that satisfy the predicate f.

val range : ?stride:int -> int -> int -> int t

range stride low high is the list of integers from low(inclusive) to high(exclusive), stepping by stride. If unspecified, stride defaults to 1.

val frange : ?stride:float -> float -> float -> float t

frange is similar to range, but for floats.

val init : int -> f:(int -> 'a) -> 'a t

init f n is [(f 0); (f 1); ...; (f (n-1))]. It is an error if n < 0.

val rev_filter_map : 'a t -> f:('a -> 'b option) -> 'b t

rev_filter_map f l is the reversed sublist of l containing only elements for which f returns Some e.

val rev_filter_mapi : 'a t -> f:(int -> 'a -> 'b option) -> 'b t

rev_filter_mapi is just like rev_filter_map, but it also passes in the index of each element as the first argument to the mapped function. Tail-recursive.

val filter_map : 'a t -> f:('a -> 'b option) -> 'b t

filter_map f l is the sublist of l containing only elements for which f returns Some e.

val filter_mapi : 'a t -> f:(int -> 'a -> 'b option) -> 'b t

filter_mapi is just like filter_map, but it also passes in the index of each element as the first argument to the mapped function. Tail-recursive.

val filter_opt : 'a option t -> 'a t

filter_opt l is the sublist of l containing only elements which are Some e. In other words, filter_opt l = filter_map ~f:ident l.

val partition_map : 'a t ->
       f:('a -> [ `Fst of 'b | `Snd of 'c ]) -> 'b t * 'c t

partition_map t ~f partitions t according to f.

module Assoc: sig .. end

val split_n : 'a t -> int -> 'a t * 'a t

split_n n [e1; ...; em] is ([e1; ...; en], [en+1; ...; em]). If n > m, ([e1; ...; em], []) is returned. If n < 0, ([], [e1; ...; em]) is returned.

Note that sub and slice are inconsistent in the sense that only the former uses python-style indices!

val sub : 'a t -> pos:int -> len:int -> 'a t

sub pos len l is the len-element sublist of l, starting at pos.

val slice : 'a t -> int -> int -> 'a t

slice l start stop returns a new list including elements l.(start) through l.(stop-1), normalized python-style.

val take : 'a t -> int -> 'a t

take l n is fst (split_n n l). drop l n is snd (split_n n l).

val drop : 'a t -> int -> 'a t

val take_while : 'a t -> f:('a -> bool) -> 'a t

take_while l ~f returns the longest prefix of l for which f is true.

val drop_while : 'a t -> f:('a -> bool) -> 'a t

drop_while l ~f drops the longest prefix of l for which f is true.

val concat : 'a t t -> 'a t

Concatenate a list of lists. The elements of the argument are all concatenated together (in the same order) to give the result. Tail recursive over outer and inner lists.

val flatten : 'a t t -> 'a t

Same as concat.

val flatten_no_order : 'a t t -> 'a t

Same as flatten but faster and without preserving any ordering (ie for lists that are essentially viewed as multi-sets.

val cons : 'a -> 'a t -> 'a t

val cartesian_product : 'a t -> 'b t -> ('a * 'b) t

val to_string : ('a -> string) -> 'a t -> string

val permute : ?random_state:Random.State.t -> 'a t -> 'a t

permute l shuffles l, using Random.int

val is_sorted : 'a t -> compare:('a -> 'a -> int) -> bool

val compare : 'a t -> 'a t -> cmp:('a -> 'a -> int) -> int

lexicographic

val equal : 'a t -> 'a t -> ('a -> 'a -> bool) -> bool

module Infix: sig .. end