Модуль Iarray

module Iarray: sig .. end

Операции с неизменяемыми массивами.

Этот модуль повторяет API модуля Array, но не включает функции, предполагающие возможность изменения массива; помимо функций, явно изменяющих массив, в него не входят copy, а также функции make, create_float и make_matrix, создающие массивы, состоящие только из констант. Исключение составляют функции сортировки: для них предусмотрен копирующий API вместо изменения массива на месте.

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

  let a : _ Iarray.t = [|1;2;3|]
  let b = let f (a : _ Iarray.t) = a in
    f [|1;2;3|]
  let c = ([|1;2;3|] : _ Iarray.t)

Начиная с версии 5.4

type 'a t = 'a iarray

Псевдоним типа неизменяемых массивов.

val length : 'a iarray -> int

Возвращает длину (количество элементов) заданного неизменяемого массива.

val get : 'a iarray -> int -> 'a

get a n возвращает элемент с номером n неизменяемого массива a. Номер первого элемента — 0. Номер последнего элемента — length a - 1.

Вызывает исключение Invalid_argument, если n находится вне диапазона от 0 до (length a - 1).

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

init n f возвращает новый неизменяемый массив длины n, элемент с номером i которого инициализирован результатом f i. Иными словами, init n f заполняет массив результатами применения f к целым числам от 0 до n-1.

Вызывает исключение Invalid_argument, если n < 0 или n > Sys.max_array_length. Если тип возвращаемого значения f — float, максимальный размер составляет лишь Sys.max_array_length / 2.

val append : 'a iarray -> 'a iarray -> 'a iarray

append v1 v2 возвращает новый неизменяемый массив, содержащий результат конкатенации неизменяемых массивов v1 и v2.

Вызывает исключение Invalid_argument, если length v1 + length v2 > Sys.max_array_length.

val concat : 'a iarray list -> 'a iarray

Аналогично Iarray.append, но объединяет список неизменяемых массивов.

val sub : 'a iarray -> pos:int -> len:int -> 'a iarray

sub a ~pos ~len возвращает новый неизменяемый массив длины len, содержащий элементы с номерами от pos до pos + len - 1 неизменяемого массива a. При этом создаётся копия выбранной части неизменяемого массива.

Вызывает исключение Invalid_argument, если pos и len не задают допустимый подмассив a, то есть если pos < 0, или len < 0, или pos + len > length a.

val to_list : 'a iarray -> 'a list

to_list a возвращает список всех элементов a.

val of_list : 'a list -> 'a iarray

of_list l возвращает новый неизменяемый массив, содержащий элементы l.

Вызывает исключение Invalid_argument, если длина l превышает Sys.max_array_length.

Преобразование в изменяемые массивы и обратно

val to_array : 'a iarray -> 'a array

to_array a возвращает изменяемую копию неизменяемого массива a, то есть новый (изменяемый) массив, содержащий те же элементы, что и a

val of_array : 'a array -> 'a iarray

of_array ma возвращает неизменяемую копию изменяемого массива ma, то есть новый неизменяемый массив, содержащий те же элементы, что и ma

Сравнение

val equal : ('a -> 'a -> bool) -> 'a iarray -> 'a iarray -> bool

eq [|a1; ...; an|] [|b1; ..; bm|] выполняется, если длины двух входных неизменяемых массивов совпадают и для каждой пары элементов ai, bi, находящихся на одинаковых позициях, выполняется eq ai bi.

val compare : ('a -> 'a -> int) -> 'a iarray -> 'a iarray -> int

Если функция cmp задаёт предпорядок на элементах, compare cmp a b сначала сравнивает a и b по длине, а затем, если длины равны, — по элементам согласно лексикографическому предпорядку.

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

Итераторы

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

iter f a последовательно применяет функцию f ко всем элементам a. Эквивалентно f (get a 0); f (get a 1); ...; f (get a (length a - 1)); ().

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

Аналогично Iarray.iter, но функция получает индекс элемента первым аргументом, а сам элемент — вторым.

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

map f a применяет функцию f ко всем элементам a и создаёт неизменяемый массив из результатов, возвращаемых f: [| f (get a 0); f (get a 1); ...; f (get a (length a - 1)) |].

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

Аналогично Iarray.map, но функция получает индекс элемента первым аргументом, а сам элемент — вторым.

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

fold_left f init a вычисляет f (... (f (f init (get a 0)) (get a 1)) ...) (get a n-1), где n — длина неизменяемого массива a.

val fold_left_map : ('a -> 'b -> 'a * 'c) -> 'a -> 'b iarray -> 'a * 'c iarray

fold_left_map сочетает в себе Iarray.fold_left и Iarray.map, передавая аккумулятор между вызовами f.

val fold_right : ('b -> 'a -> 'a) -> 'b iarray -> 'a -> 'a

fold_right f a init вычисляет f (get a 0) (f (get a 1) ( ... (f (get a (n-1)) init) ...)), где n — длина неизменяемого массива a.

Итераторы для двух массивов

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

iter2 f a b применяет функцию f ко всем элементам a и b.

Вызывает исключение Invalid_argument, если размеры неизменяемых массивов не совпадают.

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

map2 f a b применяет функцию f ко всем элементам a и b и создаёт неизменяемый массив из результатов, возвращаемых f: [| f (get a 0) (get b 0); ...; f (get a (length a - 1)) (get b (length b - 1))|].

Вызывает исключение Invalid_argument, если размеры неизменяемых массивов не совпадают.

Поиск по массиву

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

for_all f [|a1; ...; an|] проверяет, удовлетворяют ли все элементы неизменяемого массива предикату f. Иными словами, возвращает (f a1) && (f a2) && ... && (f an).

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

exists f [|a1; ...; an|] проверяет, удовлетворяет ли хотя бы один элемент неизменяемого массива предикату f. Иными словами, возвращает (f a1) || (f a2) || ... || (f an).

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

Аналогично Iarray.for_all, но для предиката с двумя аргументами.

Вызывает исключение Invalid_argument, если длины двух неизменяемых массивов различаются.

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

Аналогично Iarray.exists, но для предиката с двумя аргументами.

Вызывает исключение Invalid_argument, если длины двух неизменяемых массивов различаются.

val mem : 'a -> 'a iarray -> bool

mem a set истинно тогда и только тогда, когда a структурно равен одному из элементов set (то есть в set существует x такой, что compare a x = 0).

val memq : 'a -> 'a iarray -> bool

Аналогично Iarray.mem, но для сравнения элементов массива используется физическое равенство вместо структурного.

val find_opt : ('a -> bool) -> 'a iarray -> 'a option

find_opt f a возвращает первый элемент неизменяемого массива a, удовлетворяющий предикату f, или None, если в массиве a нет значения, удовлетворяющего f.

val find_index : ('a -> bool) -> 'a iarray -> int option

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

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

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

find_map f a последовательно применяет f к элементам a и возвращает первый результат вида Some v либо None, если таких результатов нет.

val find_mapi : (int -> 'a -> 'b option) -> 'a iarray -> 'b option

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

Массивы пар

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

split [|(a1,b1); ...; (an,bn)|] — это ([|a1; ...; an|], [|b1; ...; bn|]).

val combine : 'a iarray -> 'b iarray -> ('a * 'b) iarray

combine [|a1; ...; an|] [|b1; ...; bn|] — это [|(a1,b1); ...; (an,bn)|]. Вызывает исключение Invalid_argument, если длины двух неизменяемых массивов различаются.

Сортировка

val sort : ('a -> 'a -> int) -> 'a iarray -> 'a iarray

Сортирует неизменяемый массив по возрастанию согласно функции сравнения. Функция сравнения должна возвращать 0, если её аргументы равны, положительное целое число, если первый аргумент больше, и отрицательное целое число, если первый аргумент меньше (полная спецификация приведена ниже). Например, compare — подходящая функция сравнения. Результатом вызова sort будет новый неизменяемый массив, содержащий те же элементы, что и исходный, но отсортированные по возрастанию. Помимо этого нового массива, гарантируется, что sort использует постоянный объём памяти в куче и (не более чем) логический объём памяти в стеке.

Текущая реализация использует пирамидальную сортировку. Она использует постоянный объём памяти в стеке.

Спецификация функции сравнения: пусть a — неизменяемый массив, а cmp — функция сравнения. Для любых x, y, z из a должны выполняться следующие условия:

cmp x y > 0 тогда и только тогда, когда cmp y x < 0
если cmp x y >= 0 и cmp y z >= 0, то cmp x z >= 0

Результат sort, который обозначим a', содержит те же элементы, что и a, переставленные так, что для любых допустимых индексов i и j массива a (или, что эквивалентно, a'):

cmp (get a' i) (get a' j) >= 0 тогда и только тогда, когда i >= j

val stable_sort : ('a -> 'a -> int) -> 'a iarray -> 'a iarray

Аналогично Iarray.sort, но алгоритм сортировки является устойчивым (то есть элементы с одинаковым результатом сравнения сохраняют исходный порядок) и не гарантирует постоянный объём памяти в куче.

Текущая реализация использует сортировку слиянием. Она использует временный массив длины n/2, где n — длина неизменяемого массива. Обычно она работает быстрее текущей реализации Iarray.sort.

val fast_sort : ('a -> 'a -> int) -> 'a iarray -> 'a iarray

Аналогично Iarray.sort или Iarray.stable_sort — в зависимости от того, какой вариант быстрее на типичных входных данных.

Итераторы

val to_seq : 'a iarray -> 'a Seq.t

Обходит неизменяемый массив в порядке возрастания.

val to_seqi : 'a iarray -> (int * 'a) Seq.t

Обходит неизменяемый массив в порядке возрастания, передавая вместе с элементами их индексы.

val of_seq : 'a Seq.t -> 'a iarray

Создаёт неизменяемый массив с помощью генератора