Модуль Seq

Последовательность xs типа 'a t — это отложенный список элементов типа 'a. Такая последовательность запрашивается путём выполнения функции xs(). Этот вызов функции возвращает узел, позволяя вызывающей стороне определить, пустая ли последовательность или нет, и в последнем случае получить ее голову и хвост.

Узел — это либо Nil, что означает, что последовательность пуста, либо Cons (x, xs), что означает, что x — первый элемент последовательности, а xs — остаток последовательности.

is_empty xs определяет, пуста ли последовательность xs.

Рекомендуется, чтобы последовательность xs была постоянной. Действительно, is_empty xs запрашивает голову последовательности xs, поэтому, если xs временная, может случиться, что xs больше нельзя использовать после этого вызова.

Если xs пуста, то uncons xs равно None.

Если xs не пуста, то uncons xs равно Some (x, ys) , где x — голова последовательности, а ys — ее хвост.

length xs — это длина последовательности xs.

Последовательность xs должна быть конечной.

iter f xs вызывает f x последовательно для каждого элемента x последовательности xs, слева направо.

Завершается только если последовательность xs конечна.

fold_left f _ xs вызывает f _ x последовательно для каждого элемента x последовательности xs, слева направо.

Аккумулятор типа 'a передаётся через вызовы f.

Завершается только если последовательность xs конечна.

iteri f xs вызывает f i x последовательно для каждого элемента x с индексом i в последовательности xs.

Завершается только если последовательность xs конечна.

iteri f xs эквивалентно iter (fun (i, x) -> f i x) (zip (ints 0) xs).

fold_lefti f _ xs вызывает f _ i x последовательно для каждого элемента x с индексом i в последовательности xs.

Аккумулятор типа 'b передаётся через вызовы f.

Завершается только если последовательность xs конечна.

fold_lefti f accu xs эквивалентно fold_left (fun accu (i, x) -> f accu i x) accu (zip (ints 0) xs).

for_all p xs определяет, удовлетворяют ли все элементы x последовательности xs условию p x.

Последовательность xs должна быть конечной.

exists xs p определяет, удовлетворяет ли хотя бы один элемент x последовательности xs условию p x.

Последовательность xs должна быть конечной.

find p xs возвращает Some x, где x — первый элемент последовательности xs , удовлетворяющий условию p x, если такой элемент есть.

Возвращает None если такого элемента нет.

Последовательность xs должна быть конечной.

find_index p xs возвращает Some i, где i это индекс первого элемента последовательности xs, удовлетворяющего p x, если такой элемент существует.

Возвращает None, если такого элемента нет.

Последовательность xs должна быть конечной.

find_map f xs возвращает Some y, где x это первый элемент последовательности xs, такой что f x = Some _, если такой элемент существует, и где y определяется как f x = Some y.

Возвращает None, если такого элемента нет.

Последовательность xs должна быть конечной.

То же, что и find_map, но предикат применяется к индексу элемента в качестве первого аргумента (нумерация с 0), а сам элемент — в качестве второго аргумента.

Последовательность xs должна быть конечной.

iter2 f xs ys вызывает f x y последовательно для каждой пары (x, y) элементов, синхронно извлекаемых из последовательностей xs и ys.

Если последовательности xs и ys имеют разную длину, то итерация прекращается, как только одна из последовательностей исчерпана; лишние элементы в другой последовательности игнорируются.

Итерация завершается только если хотя бы одна из последовательностей xs и ys конечна.

iter2 f xs ys эквивалентно iter (fun (x, y) -> f x y) (zip xs ys).

fold_left2 f _ xs ys вызывает f _ x y последовательно для каждой пары (x, y) элементов, синхронно извлекаемых из последовательностей xs и ys.

Аккумулятор типа 'a передаётся через вызовы f.

Если последовательности xs и ys имеют разную длину, то итерация прекращается, как только одна из последовательностей исчерпана; лишние элементы в другой последовательности игнорируются.

Итерация завершается только если хотя бы одна из последовательностей xs и ys конечна.

fold_left2 f accu xs ys эквивалентно fold_left (fun accu (x, y) -> f accu x y) (zip xs ys).

for_all2 p xs ys определяет, удовлетворяют ли все пары (x, y) элементов, синхронно извлекаемых из последовательностей xs и ys, условию p x y.

Если последовательности xs и ys имеют разную длину, то итерация прекращается, как только одна из последовательностей исчерпана; лишние элементы в другой последовательности игнорируются. В частности, если xs или ys пуста, то for_all2 p xs ys истинно. Именно здесь for_all2 и equal различаются: equal eq xs ys может быть истинно только если xs и ys имеют одинаковую длину.

Хотя бы одна из последовательностей xs и ys должна быть конечной.

for_all2 p xs ys эквивалентно for_all (fun b -> b) (map2 p xs ys).

exists2 p xs ys определяет, удовлетворяет ли какая-либо пара (x, y) элементов, синхронно извлекаемых из последовательностей xs и ys, условию p x y.

Если последовательности xs и ys имеют разную длину, то итерация должна прекратиться, как только одна из последовательностей исчерпана; лишние элементы в другой последовательности игнорируются.

Хотя бы одна из последовательностей xs и ys должна быть конечной.

exists2 p xs ys эквивалентно exists (fun b -> b) (map2 p xs ys).

При условии, что функция eq определяет равенство элементов, equal eq xs ys определяет, являются ли последовательности xs и ys поэлементно равными.

Хотя бы одна из последовательностей xs и ys должна быть конечной.

При условии, что функция cmp определяет предпорядок на элементах, compare cmp xs ys сравнивает последовательности xs и ys в соответствии с лексикографическим предпорядком.

Для получения дополнительной информации о функциях сравнения см. Array.sort.

Хотя бы одна из последовательностей xs и ys должна быть конечной.

empty это пустая последовательность. Она не имеет элементов. Её длина равна 0.

return x это последовательность, единственным элементом которой является x. Её длина равна 1.

cons x xs это последовательность, которая начинается с элемента x, за которым следует последовательность xs.

Запись cons (f()) xs приводит к тому, что вызов функции f() происходит немедленно. Для того, чтобы этот вызов был отложен до запроса последовательности, следует написать (fun () -> Cons(f(), xs)).

init n f это последовательность f 0; f 1; ...; f (n-1).

n должно быть неотрицательным.

При желании, бесконечная последовательность f 0; f 1; ... может быть определена как map f (ints 0).

unfold создаёт последовательность из функции шага и начального состояния.

Если f u равно None, то unfold f u это пустая последовательность. Если f u равно Some (x, u'), то unfold f u это непустая последовательность cons x (unfold f u').

Например, unfold (function [] -> None | h :: t -> Some (h, t)) l эквивалентно List.to_seq l.

repeat x это бесконечная последовательность, где элемент x повторяется бесконечно.

repeat x эквивалентно cycle (return x).

forever f это бесконечная последовательность, где каждый элемент создаётся (по требованию) вызовом функции f().

Например, forever Random.bool это бесконечная последовательность случайных битов.

forever f эквивалентно map f (repeat ()).

cycle xs это бесконечная последовательность, состоящая из бесконечного числа повторений последовательности xs.

Если xs это пустая последовательность, то cycle xs также пуста.

Потребление (префикса) последовательности cycle xs один раз может привести к тому, что последовательность xs будет потреблена более одного раза. Поэтому xs должна быть постоянной.

iterate f x это бесконечная последовательность, элементы которой равны x, f x, f (f x), и так далее.

Другими словами, это орбита функции f, начинающаяся с x.

map f xs это образ последовательности xs при преобразовании f.

Если xs это последовательность x0; x1; ..., то map f xs это последовательность f x0; f x1; ....

mapi аналогично map, но применяет функцию f к индексу и элементу.

mapi f xs эквивалентно map2 f (ints 0) xs.

filter p xs это последовательность элементов x из xs, удовлетворяющих p x.

Другими словами, filter p xs это последовательность xs, лишённая элементов x, таких что p x ложно.

filter_map f xs — это последовательность элементов y такая, что f x = Some y, где x принимает значения из xs.

filter_map f xs эквивалентно map Option.get (filter Option.is_some (map f xs)).

Если xs — это последовательность [x0; x1; x2; ...], то scan f a0 xs — это последовательность аккумуляторов [a0; a1; a2; ...], где a1 — это f a0 x0, a2 — это f a1 x1, и так далее.

Таким образом, scan f a0 xs концептуально связано с fold_left f a0 xs. Однако вместо выполнения жадной итерации и немедленного возвращения конечного аккумулятора, оно возвращает последовательность аккумуляторов.

Например, scan (+) 0 преобразует последовательность целых чисел в последовательность её частичных сумм.

Если xs имеет длину n, то scan f a0 xs имеет длину n+1.

take n xs — это последовательность из первых n элементов xs.

Если xs содержит меньше, чем n элементов, то take n xs эквивалентно xs.

n должно быть неотрицательным.

drop n xs — это последовательность xs, лишённая первых n элементов.

Если xs содержит меньше, чем n элементов, то drop n xs пуста.

n должно быть неотрицательным.

drop ленивая: первые n+1 элементов последовательности xs требуются только тогда, когда требуется первый элемент drop n xs. По этой причине, drop 1 xs не эквивалентно tail xs, которое запрашивает xs немедленно.

take_while p xs — это наибольший префикс последовательности xs, где каждый элемент x удовлетворяет условию p x.

drop_while p xs — это последовательность xs, лишённая префикса take_while p xs.

При условии, что функция eq определяет равенство элементов, group eq xs — это последовательность максимальных последовательностей одинаковых смежных элементов последовательности xs.

Каждый элемент group eq xs является непустой последовательностью равных элементов.

Конкатенация concat (group eq xs) равна xs.

Обращение к group eq xs, и к последовательностям, которые она содержит, может привести к тому, что xs будет обработана более одного раза. Поэтому xs должна быть персистентной.

Последовательность memoize xs содержит те же элементы, что и последовательность xs.

Независимо от того, является ли xs временной или персистентной, memoize xs является персистентной: даже если она запрашивается несколько раз, xs запрашивается не более одного раза.

Построение последовательности memoize xs внутренне использует приостановки, предоставляемые модулем Lazy. Эти приостановки не потокобезопасны. Поэтому к последовательности memoize xs нельзя обращаться из нескольких потоков одновременно.

Это исключение возникает, когда последовательность, возвращённая Seq.once (или её суффикс) запрашивается более одного раза.

Последовательность once xs содержит те же элементы, что и последовательность xs.

Независимо от того, является ли xs временной или персистентной, once xs является временной последовательностью: к ней можно обратиться не более одного раза. Если она (или её суффикс) запрашивается более одного раза, то возникает исключение Forced_twice. Это может быть полезно при отладке или тестировании для обеспечения того, что к последовательности обращаются не более одного раза.

Если xss — матрица (последовательность строк), то transpose xss — это последовательность столбцов матрицы xss.

Строки матрицы xss не обязаны иметь одинаковую длину.

Матрица xss не обязана быть конечной (в любом направлении).

Матрица xss должна быть персистентной.

append xs ys — это конкатенация последовательностей xs и ys.

Её элементы — это элементы xs, за которыми следуют элементы ys.

Если xss — это последовательность последовательностей, то concat xss — это её конкатенация.

Если xss — это последовательность xs0; xs1; ..., то concat xss — это последовательность xs0 @ xs1 @ ....

flat_map f xs эквивалентно concat (map f xs).

concat_map f xs эквивалентно concat (map f xs).

concat_map — псевдоним для flat_map.

zip xs ys — это последовательность пар (x, y), взятых синхронно из последовательностей xs и ys.

Если последовательности xs и ys имеют разную длину, то последовательность завершается, как только одна из последовательностей исчерпана; лишние элементы в другой последовательности игнорируются.

zip xs ys эквивалентно map2 (fun a b -> (a, b)) xs ys.

map2 f xs ys — это последовательность элементов f x y, где пары (x, y) взяты синхронно из последовательностей xs и ys.

Если последовательности xs и ys имеют разную длину, то последовательность завершается, как только одна из последовательностей исчерпана; лишние элементы в другой последовательности игнорируются.

map2 f xs ys эквивалентно map (fun (x, y) -> f x y) (zip xs ys).

interleave xs ys — это последовательность, которая начинается с первого элемента xs, продолжает первым элементом ys, и так далее.

Когда одна из последовательностей xs и ys исчерпана, interleave xs ys продолжается с остальной частью другой последовательности.

Если последовательности xs и ys отсортированы по общему упорядочению cmp, то sorted_merge cmp xs ys — это отсортированная последовательность, полученная путём слияния последовательностей xs и ys.

Подробнее о функциях сравнения см. Array.sort.

product xs ys — это декартово произведение последовательностей xs и ys.

Для каждого элемента x последовательности xs и для каждого элемента y последовательности ys, пара (x, y) появляется один раз как элемент product xs ys.

Порядок появления пар не определён.

Последовательности xs и ys не обязаны быть конечными.

Последовательности xs и ys должны быть персистентными.

Последовательность map_product f xs ys представляет собой изображение через f декартова произведения последовательностей xs и ys.

Для каждого элемента x последовательности xs и для каждого элемента y последовательности ys, элемент f x y появляется один раз в качестве элемента map_product f xs ys.

Порядок, в котором эти элементы появляются, не определён.

Последовательности xs и ys не обязательно должны быть конечными.

Последовательности xs и ys должны быть персистентными.

map_product f xs ys эквивалентно map (fun (x, y) -> f x y) (product xs ys).

unzip преобразует последовательность пар в пару последовательностей.

unzip xs эквивалентно (map fst xs, map snd xs).

Обращение к любой из последовательностей, возвращаемых unzip xs, приводит к обращению к xs. Следовательно, обращение к обеим из них приводит к двойному обращению к xs. Таким образом, xs должна быть персистентной и быстрой. Если это не так, используйте unzip (memoize xs).

split является псевдонимом для unzip.

partition_map f xs возвращает пару последовательностей (ys, zs), где:

• ys — последовательность элементов y, удовлетворяющих условию f x = Left y, где x проходит по xs;

• zs — последовательность элементов z, удовлетворяющих условию f x = Right z, где x проходит по xs.

partition_map f xs эквивалентно паре filter_map Either.find_left (map f xs) и filter_map Either.find_right (map f xs).

Обращение к любой из последовательностей, возвращаемых partition_map f xs, приводит к обращению к xs. Следовательно, обращение к обеим из них приводит к двойному обращению к xs. Таким образом, xs должна быть персистентной и быстрой. Если это не так, используйте partition_map f (memoize xs).

partition p xs возвращает пару подпоследовательностей элементов xs, удовлетворяющих условию p, и элементов xs, не удовлетворяющих условию p.

partition p xs эквивалентно filter p xs, filter (fun x -> not (p x)) xs.

Обработка обеих последовательностей, возвращаемых partition p xs, приводит к двойной обработке xs и двойному применению функции f к каждому элементу списка. Поэтому f должна быть чистой и быстрой. Кроме того, xs должна быть персистентной и быстрой. Если это не так, используйте partition p (memoize xs).

of_dispenser it — это последовательность элементов, производимых дисператором it. Это эфемерная последовательность: она может быть обработана не более одного раза. Если нужна персистентная последовательность, используйте memoize (of_dispenser it).

to_dispenser xs — это новый дисператор на последовательности xs.

Этот дисператор имеет изменяемое внутреннее состояние, которое не защищено блокировкой; поэтому его нельзя использовать несколькими потоками одновременно.

ints i — бесконечная последовательность целых чисел, начинающаяся с i и увеличивающаяся.