module Kwlist: sig .. end

val mapi : ?i:int -> (int -> 'a -> 'b) -> 'a list -> 'b list

like List.map but pass index as first parameter; NOT tail-recursive
Returns new list of mapped values

val iteri : ?i:int -> (int -> 'a -> 'b) -> 'a list -> unit

like List.iter but pass index as first parameter
Returns ()

val filteri : ?i:int -> (int -> 'a -> bool) -> 'a list -> 'a list

Like List.filter but pass index as first parameter
Returns list of items which satisfy f

val foldl1 : ('a -> 'a -> 'a) -> 'a list -> 'a

foldl1 f list: like List.fold_left but use List.hd list as initial accumulator

Tail recursive.
Raises Failure _ if list = []

val scan : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a list

Apply List.fold_left f a to all prefixes of list; e.g. scan (+) 0 returns list of running totals.
Returns list of folds

val foldgroup : ?skiprem:bool -> int -> ('a -> 'b list -> 'a) -> 'a -> 'b list -> 'a

fold a function across subsequences of list

The function (f acc g) is applied to an accumulator and a sublist of length size; unless skiprem is true, f must be prepared to receive a final sublist of length less than size if the length of list is not evenly divisible by size.

For efficiency, the sublists passed to f will be in the reverse of the order in which they occur in list; f can reverse them if necessary.

val first_true : ('a -> bool) -> 'a list -> 'a option

first_true p list: return the first element elt of list for which (p elt) is true.

Much faster than:

     let first_true p = List.filter p $ catch List.hd

when the first true item is near the beginning of a large list; takes the same amount of time if the first true item is near the end.

val first : ?flex:bool -> int -> 'a list -> 'a list

first ?flex n list: return first n elements of list.

If n is > length list, raise Invalid_argument, unless flex, in which case return entire list.
Raises Invalid_argument if n < 0 or n > length of list
Returns prefix of list

val final : int -> 'a list -> 'a list

Return final n elements of list

Tail-recursive.
Returns suffix of list

val last : 'a list -> 'a

Return last element of list

More efficient than List.nth when you don't know the length of the list. Tail-recursive.

val init : 'a list -> 'a list

init list: Return all the elements of a list except the last one.

The list must be non-empty. Tail-recursive.

val evens : 'a list -> 'a list

Return even elements of list

List.nth list 0; List.nth list 2; List.nth list 4; ....

val odds : 'a list -> 'a list

Return odd elements of list

List.nth list 1; List.nth list 3; List.nth list 5; ....

val split_at : 'a -> 'a list -> 'a list * 'a list

Split a list at some delimiter value, returning a pair of lists: those elements occurring before the (first) delimiter and those occurring after it.

If the delimiter does not occur, all the elements are returned in the first list and the second is empty.

The delimiter itself is not returned; if the delimiter occurs multiple times, only the first counts; all the rest are simple values and will be in the right-hand list.
Returns pair of left- and right-hand lists of elements

val split : int -> 'a list -> 'a list * 'a * 'a list

split a list into 3 parts: the list of elts before n, element n itself, and the list of elts after n
Returns 3-tuple

val halve : 'a list -> 'a list * 'a list

divide a list into two halves

One-pass algorthm.
Returns two halves of list as a 2-tuple

val splitat : int -> 'a list -> 'a list * 'a list

splitat n xs: given an integer (positive or zero) and a list, splits the list into two lists (returned as a tuple) at the position corresponding to the given integer.

If the integer is greater than the length of the list, it returns a tuple containing the entire list as its first element and the empty list as its second element.

Tail recursive.

val take : ?atmost:bool -> int -> 'a list -> 'a list

Return the first n elements of a list

val takewhile : ('a -> bool) -> 'a list -> 'a list

Return leading sublist of a list of elements that satisfy a predicate

Return the list that results from taking leading elements from the input list as long as f applied to those elements returns true; stop taking elements as soon as f fails.

Example: (takewhile ((=) 0) [0;0;0;0;1;2;0;3;0]) => [0; 0; 0; 0].

Tail-recursive.
Returns prefix of list

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

Return the list resulting from dropping the first n elements of a list

val dropwhile : ('a -> bool) -> 'a list -> 'a list

Delete leading elements of a list that satisfy a predicate

Return the list that results from removing leading elements from the input list as long as f applied to those elements returns true; stop removing elements as soon as f fails.

Example: (dropwhile ((=) 0) [0;0;0;0;1;2;0;3;0]) => [1; 2; 0; 3; 0].

Tail-recursive.
Returns trimmed list

val takeall : int -> 'a list -> 'a list list

takeall size list: like take size list, except applied successively to all remaining substrings of list.

So, takeall 3 (1--10) = [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]; [10]].
Returns list of lists of size elements (final element may be < size)

val index : ?i:int -> 'a list -> (int * 'a) list

add indexes (list positions) to list elements, converting an 'a list to an (int*'a) list
Returns list of pairs of index,element

val project : ?sorted:bool -> int list -> 'a list -> 'a list

Project items from list in accord with indices; tail recursive

val prefix : 'a list -> 'a list -> bool

Given two lists, return true if the first is a list prefix of the second, false otherwise

Example: (prefix [1;2;3] [1;2;3;4;5]) => true
Returns bool

val repeat : int -> 'a -> 'a list

return list of length n, each element of which is x
Returns list of repetitions

val lrepeat : int -> 'a -> 'a list

Deprecated.You should use Kwlist.repeat

val prepend : 'a list -> 'a list -> 'a list

prepend a b: prepend onto list a the list b

Exactly the same as flip (@). So, not tail-recursive (length of the second argument).

val combine : ?def:'a -> 'a list -> 'a list -> ('a * 'a) list

combine ?def x y: like List.combine, but if ?def givem, use as default value in the case that either list is short.

E.g. combine ~def:0 [1;2] [] = [(1, 0); (2, 0)]

val concat_reversed : 'a list list -> 'a list

concat_reversed lists: reverse each list in lists and then concatenate them.

Tail-recursive version of (map List.rev $ List.concat)

val remove : ?eq:('a -> 'a -> bool) -> 'a -> 'a list -> 'a list

remove ?eq x l: remove all instances of x from list l.

val nub : ?by:('a -> 'a -> bool) -> 'a list -> 'a list

nub ?by list: remove duplicate elements from a list.

"In particular, it keeps only the first occurrence of each element. (The name nub means `essence'.)" -- stolen from Haskell Hierarchical Libraries
Returns de-duped list

val transpose : 'a list list -> 'a list list

Transpose a list of lists

Example: (transpose [[1;2;3];[4;5;6]]) => [[1; 4]; [2; 5]; [3; 6]].

Tail-recursive.
Raises Invalid_argument if matrix is non-rectangular
Returns transposed version

val cartesian_product : 'a list list -> 'a list list

cartesian_product list: Cartesian product of list of lists.

Tail recursive.

val behead : 'a list -> 'a list -> 'a list

Remove prefix pat of list subj.

Example: (behead [1;2;3] [1;2;3;4;5]) => [4; 5]
Raises Failure "behead"
Returns remainder of list subj

val pad : int -> 'a -> 'a list -> 'a list

pad n def list: pad a list to length n with def values.
Before 1.20140612 removed ?trunc parameter; compose with truncate instead
Returns padded list with length >= n

val truncate : int -> 'a list -> 'a list

truncate n list: truncate list to first n elements.

val sort_sorted : 'a list -> 'a list

efficient insertion sort for almost-sorted lists

Minimizes copying.
Author(s): Dr Jon D Harrop, Flying Frog Consultancy Ltd.

val subsort : ('a -> 'a -> int) -> ('b -> 'a) list -> 'b -> 'b -> int

Comparator-generator for sub-sorting

This is a sort-predicate generator. It takes a comparison function ('a -> 'a -> int) -- Pervasives.compare is suitable -- and a list of selector functions, one for each sort field, in order, and returns a function of two arguments suitable for passing to List.sort (or Array.sort). Typically one would use partial application like so:

sort (subsort compare [sel 1; sel 4; sel 2]) some_list_of_recs

which would sort a list of lists on the 1th field of each sublist, using the 4th and the 2nd fields for the subsort (assuming that you write the "sel" function correctly).

A selector is a function ('a -> 'b) which will be passed a "record" and will return anything (but probably some "subfield" of that record), which will be used for sorting.

Example 1: sort a list of lists of three integers on fields 2, 1, 0.

# let nth n list = List.nth list n
  val nth : int -> 'a list -> 'a = <fun>
  # let x1 = [[1;2;3];[2;1;1];[3;2;1];[2;2;3]];;
  val x1 : int list list = [[1; 2; 3]; [2; 1; 1]; [3; 2; 1]; [2; 2; 3]]
  # List.sort (subsort compare [nth 2; nth 1; nth 0]) x1;;
  ... int list list = [[2; 1; 1]; [3; 2; 1]; [1; 2; 3]; [2; 2; 3]]

Example 2: same thing, but compare strings ignoring case. Pervasives.compare will compare most anything, so: (subsort compare nth 2; nth 1; nth 0) will work to compare strings, but we need to implement case insensitivity:

# let strcmp a b = compare (String.lowercase a) (String.lowercase b)
  # List.sort (subsort strcmp [nth 2; nth 1; nth 0]) ...

Returns comparison function suitable for List.sort or Array.sort

val uniq : 'a list -> 'a list

Like Unix command uniq(1); given a (typically sorted) 'a list, return an 'a list consisting of the unique subsequences of 'a's.

Example: uniq [[1;1;2;3;3;3;3]] = [[1;2;3]]
Returns uniquified list

val uniqc : 'a list -> (int * 'a) list

Like Unix command uniq(1) with -c; given a (typically sorted) 'a list, return an (int * 'a) list consisting of the unique subsequences of 'a's, with a count of how many times each occurred.

Example: uniqc [1;1;2;3;3;3;3] = [(2, 1); (1, 2); (4, 3)]
Returns the counted list

val shuffle : 'a list -> 'a list

shuffle (randomize) a list

Probably O(nlogn) with a bad constant factor; also, not a perfect shuffle.
Returns the shuffled list

val choose : ?n:int -> int -> 'a list -> 'a list

choose ?n m lst: choose m random elements from a list of length n.

1-pass algorithm due to Knuth; if you don't provide n, requires 2 passes.
Returns a list of length m

val permutations : 'a list -> 'a list list

list of all permutations of a list
Author(s): Michel Quercia
Returns list of lists

val asplit : 'a -> ('a * 'b) list -> 'b list * ('a * 'b) list

extract from an alist all the values associated with key, returning the list of values and the alist with all key pairs removed.
Returns a pair, the list of values associated with key (original order preserved) and the remainder of the alist (original order preserved)

val coalesce : ('a * 'b) list -> ('a * 'b list) list

coalesce an alist with repeating keys into one with unique keys bound to lists of values

val move_assocs : ('a * 'b) list ->
       'a list -> ('a * 'b) list -> ('a * 'b) list * ('a * 'b) list

move_assocs keys alist: remove pairs with keys in keys from alist, collecting them in a new record; return the new record and the old record with the pairs removed; hence, move pairs matching keys from alist in newrec

val remove_assocs : 'a list -> ('a * 'b) list -> ('a * 'b) list

remove_assocs keys alist: remove all pairs from alist with any of the keys in keys

val adjoin : 'a -> 'b -> ('a * 'b) list -> ('a * 'b) list

adjoin k v alist: adjoins v to the collection of values associated with key k in the alist.

The alist is not coalesced and the new pair will be consed onto the front.

val classify : ('a -> 'b) -> ('b * 'a) list -> 'a -> ('b * 'a) list

classify f alist x: classify x according to the equivalence relation defined by f into the alist.

The result of partially-applying classify to a function is suitable for use with any left fold.

For example, to classify the elements of a list of integers into even and odd subsets:

foldl (classify (flip (mod) 2)) []

If the order of the classified values needs to match their order in the original list, be sure to reverse them, e.g.:

foldl (classify (flip (mod) 2)) [] list |> List.rev

val explode : string -> char list

Convert string to list of char

Inverse of implode. Tail-recursive.
Returns list of the characters of str

val implode : char list -> string

Convert list of char to string

Inverse of explode. Tail-recursive.
Returns a string

val intersect : 'a list -> 'a list -> 'a list

intersect l1 l2: return the intersection of the two lists