Модуль Seq

module Seq: sig .. end

Последовательности.

Последовательность типа 'a Seq.t можно рассматривать как отложенный список, то есть список, элементы которого вычисляются только тогда, когда они затребованы потребителем. Это позволяет генерировать и преобразовывать последовательности лениво (по одному элементу за раз) вместо жадно (все элементы сразу). Это также позволяет создавать концептуально бесконечные последовательности.

Тип 'a Seq.t определен как синоним для unit -> 'a Seq.node. Это тип функции; поэтому он непрозрачен. Потребитель может запросить элемент последовательности, чтобы получить следующий элемент (если он есть), но иначе никак не может проверить последовательность.

Поскольку он непрозрачен, тип 'a Seq.t не показывает, является ли последовательность:

постоянной, что означает, что последовательность можно использовать неограниченное количество раз, каждый раз получая одни и те же элементы, как неизменяемый список; или
временной, что означает, что последовательность не является постоянной. Запрос временной последовательности может иметь наблюдаемое побочное действие, например, увеличение значения изменяемой переменной. В качестве общего частного случая, временная последовательность может быть аффинна, что означает, что ее можно запросить не более одного раза.

Он также не показывает, являются ли элементы последовательности:

предварительно вычислены и сохранены в памяти, что означает, что обращение к последовательности недорого;
вычислены при первом запросе и затем сохранены в памяти, что означает, что обращение к последовательности один раз может быть дорогостоящим, но обращение к той же последовательности повторно — недорого; или
пересчитываются каждый раз, когда они запрашиваются, что может быть или не быть дешевым.

Программист должен помнить об этих различиях, чтобы понимать требования к времени и памяти последовательностей.

Для простоты большей части документации далее используется неявное предположение о том, что последовательности постоянны. Мы обычно не указываем, когда или сколько раз вызывается каждая функция, потому что это было бы слишком многословно. Например, в описании map, мы пишем: «если xs — это последовательность x0; x1; ..., то map f xs — это последовательность f x0; f x1; ...». Если бы мы хотели быть более ясными, мы могли бы указать, что преобразование происходит по требованию: то есть элементы map f xs вычисляются только при запросе. Другими словами, определение let ys = map f xs завершается немедленно и не вызывает f. Вызов функции f x0 происходит только тогда, когда запрашивается первый элемент ys, посредством вызова функции ys(). Кроме того, вызов ys() дважды заставляет f x0 быть вызванным дважды. Если требуется, чтобы f применялся не более одного раза к каждому элементу xs, даже в сценариях, когда ys запрашивается более одного раза, то следует использовать let ys = memoize (map f xs).

Как общее правило, функции, создающие последовательности, такие как map, filter, scan, take, и т. д., создают последовательности, элементы которых вычисляются только по требованию. Функции, жадно потребляющие последовательности, такие как is_empty, find, length, iter, fold_left, и т. д., — это функции, которые принуждают к вычислениям.

Когда это возможно, рекомендуется использовать последовательности вместо распределителей (функций типа unit -> 'a option которые производят элементы по требованию). В то время как последовательности могут быть постоянными или временными, распределители всегда временные и обычно сложнее использовать, чем последовательности. Предоставлены две функции преобразования, Seq.to_dispenser и Seq.of_dispenser.

С 4.07

type 'a t = unit -> 'a node

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

type 'a node =

`\|`	`Nil`
`\|`	`Cons of 'a * 'a t`

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

Потребление последовательностей

Функции в этом разделе потребляют свой аргумент — последовательность — частично или полностью:

is_empty и uncons потребляют последовательность до глубины 1. То есть, они запрашивают первый элемент последовательности, если он есть.
iter, fold_left, length, и т. д., потребляют последовательность до конца. Они завершаются только если последовательность конечна.
for_all, exists, find, и т. д. потребляют последовательность до определённой глубины, которая априори непредсказуема.

Аналогично, среди функций, потребляющих две последовательности, можно выделить две группы:

iter2 и fold_left2 потребляют обе последовательности до конца, при условии, что последовательности имеют одинаковую длину.
for_all2, exists2, equal, compare потребляют последовательности до определённой глубины, которая априори непредсказуема.

Функции, потребляющие две последовательности, могут быть применены к двум последовательностям разной длины: в этом случае избыточные элементы в более длинной последовательности игнорируются. (Возможно, затребован один избыточный элемент, хотя этот элемент не используется.)

Ни одна из функций в этом разделе не является ленивой. Эти функции являются потребителями: они заставляют происходить некоторые вычисления.

val is_empty : 'a t -> bool

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

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

С 4.14

val uncons : 'a t -> ('a * 'a t) option

Если xs пустая, то uncons xs — None.

Если xs непустая, то uncons xs — Some (head xs, tail xs), то есть пара из головы и хвоста последовательности xs.

Это равенство выполняется, если xs постоянна. Если xs временна, то следует использовать uncons, а не отдельные вызовы head и tail, так как это приведет к двукратному запросу xs.

С 4.14

val length : 'a t -> int

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

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

С 4.14

val iter : ('a -> unit) -> 'a t -> unit

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

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

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

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

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

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

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

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

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

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

С 4.14

val fold_lefti : ('b -> int -> 'a -> 'b) -> 'b -> 'a t -> 'b

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).

С 4.14

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

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

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

С 4.14

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

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

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

С 4.14

val find : ('a -> bool) -> 'a t -> 'a option

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

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

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

С 4.14

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

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

В противном случае возвращается None.

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

Since 4.14

val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit

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

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

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

Since 4.14

val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b t -> 'c t -> 'a

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

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

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

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

Since 4.14

val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

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).

Since 4.14

val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

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).

Since 4.14

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

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

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

Since 4.14

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

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

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

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

Since 4.14

Создание последовательностей

Функции в этом разделе ленивые: то есть, они возвращают последовательности, элементы которых вычисляются только по мере необходимости.

val empty : 'a t

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

val return : 'a -> 'a t

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

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

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

Запись cons (f()) xs вызывает немедленное выполнение функции f(). Чтобы вызвать функцию позже, нужно использовать (fun () -> Cons(f(), xs)).

Since 4.11

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

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

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

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

Since 4.14
Raises Invalid_argument если n отрицательно.

val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t

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.

Since 4.11

val repeat : 'a -> 'a t

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

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

Since 4.14

val forever : (unit -> 'a) -> 'a t

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

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

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

Since 4.14

val cycle : 'a t -> 'a t

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

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

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

Since 4.14

val iterate : ('a -> 'a) -> 'a -> 'a t

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

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

Since 4.14

Преобразование последовательностей

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

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

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

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

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

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

Since 4.14

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

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

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

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

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)).

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

Если 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.

Since 4.14

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

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

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

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

Since 4.14
Raises Invalid_argument если n отрицательное.

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

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

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

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

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

Since 4.14
Raises Invalid_argument если n отрицательное.

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

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

Since 4.14

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

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

Since 4.14

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

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

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

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

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

Since 4.14

val memoize : 'a t -> 'a t

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

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

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

Since 4.14

exception Forced_twice

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

Since 4.14

val once : 'a t -> 'a t

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

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

Since 4.14
Raises Forced_twice если once xs, или её суффикс, запрашивается более одного раза.

val transpose : 'a t t -> 'a t t

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

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

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

Матрица xss должна быть неизменяемой.

Since 4.14

Объединение последовательностей

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

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

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

Since 4.11

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

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

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

Since 4.13

val flat_map : ('a -> 'b t) -> 'a t -> 'b t

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

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

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

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

Since 4.13

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

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

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

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

Since 4.14

val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

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

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

Since 4.14

val interleave : 'a t -> 'a t -> 'a t

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

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

Since 4.14

val sorted_merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t

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

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

Since 4.14

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

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

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

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

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

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

Since 4.14

val map_product : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

Последовательность 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).

Since 4.14

Разделение последовательности на две последовательности

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

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

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

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

Since 4.14

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

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

Since 4.14

val partition_map : ('a -> ('b, 'c) Either.t) -> 'a t -> 'b t * 'c t

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).

Since 4.14

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

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).

Since 4.14

Преобразование между последовательностями и распределителями

Распределитель — это представление последовательности как функции типа unit -> 'a option. Каждый раз, когда эта функция вызывается, она возвращает следующий элемент последовательности. Если элементов больше нет, она возвращает None . Распределитель имеет изменяемое внутреннее состояние, поэтому является временным: последовательность, которую он представляет, может быть обработана не более одного раза.

val of_dispenser : (unit -> 'a option) -> 'a t

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

Since 4.14

val to_dispenser : 'a t -> unit -> 'a option

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

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

Since 4.14

Последовательности целых чисел

val ints : int -> int t

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

Since 4.14