Модуль 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.

Since 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 больше нельзя будет использовать после выполнения этого вызова.

Since 4.14

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

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

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

Since 4.14

val length : 'a t -> int

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

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

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

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

Since 4.14

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

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

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

Since 4.14

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

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

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

Since 4.14

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

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

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

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

Since 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