Модуль 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, слева направо.

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

Функция завершается только в том случае, если последовательность 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.

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

Функция завершается только в том случае, если последовательность 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 p xs определяет, удовлетворяет ли хотя бы один элемент 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.

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

Если последовательности 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 определяет, удовлетворяют ли условию p x y все пары (x, y) элементов, синхронно взятых из последовательностей xs и ys.

Если последовательности 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 определяет, удовлетворяет ли условию p x y хотя бы одна пара (x, y) элементов, синхронно взятых из последовательностей xs и ys.

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

singleton x возвращает последовательность из одного элемента, содержащую только x.

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.

delay (fun () -> seq) содержит те же элементы, что и seq, но выражение seq вычисляется только при запросе первого элемента.

Например,

   let rec of_tree t =
     match t with
     | Leaf v -> Seq.return v
     | Node(l, r) -> Seq.append (of_tree l) (of_tree r)
   

работает не так, как ожидается, поскольку строго обходит входное дерево, даже если выходная последовательность не вычисляется.

Вместо этого эту функцию можно записать следующим образом:

   let rec of_tree t =
     Seq.delay @@ fun () ->
     match t with
     | Leaf v -> Seq.return v
     | Node(l, r) -> Seq.append (of_tree l) (of_tree r)
   

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 ложно.

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

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.

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 — это образ декартова произведения последовательностей xs и ys посредством f.

Для каждого элемента 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 и двукратному применению функции p к каждому элементу последовательности. Поэтому p должна быть чистой и дешёвой. Кроме того, xs должна быть персистентной и дешёвой. Если это не так, используйте partition p (memoize xs).

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

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

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

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