Концепция<Iterable>представляет собой структуры данных, поддерживающие внешнюю итерацию.
Интуитивно<Iterable>можно рассматривать как своего рода контейнер, элементы которого можно вытаскивать по одному за раз.<Iterable>также дает способ узнать, когдаконтейнерпуст, т.е. когда больше нет элементов для извлечения.
В то время как<Foldable>представляет собой структуры данных, поддерживающие внутреннюю итерацию с возможностью накопления результата, концепция<Iterable>позволяет инвертировать управление итерацией. Это более гибко, чем<Foldable>, так как позволяет повторять только часть конструкции. Это, в свою очередь, позволяет<Iterable>работать над бесконечными структурами, при этом попытка сложить такую структуру никогда бы не закончилась.
Minimal complete definition
<at>,<drop_front>и<is_empty>
The linearization of an Iterable
Интуитивно для<Iterable>структуры<xs>линеаризация<xs>представляет собой последовательность всех элементов в<xs>, как если бы они были помещены в (возможно, бесконечный) список:
linearization(xs) = [x1, x2, x3, ...]
К<n>элементу линеаризации<Iterable>можно получить доступ с функцией<at>. Иными словами,<at(xs, n) == xn>.
Обратите внимание, что это понятие является именно расширениемлинеаризациипонятия<Foldable>s до бесконечного случая. Это понятие полезно для выражения различных свойств<Iterable>с и используется для этого в других документах.
Compile-time Iterables
время компиляции<Iterable>— это<Iterable>, для которого<is_empty>возвращает время компиляции<Logical>. Эти структуры позволяют выполнять итерацию во время компиляции в том смысле, что «петля», выполняющая итерацию, может быть развернута, потому что общая длина структуры выкошена во время компиляции.
В частности, обратите внимание, что время компиляции<Iterable>не имеет ничего общего с конечным или бесконечным. Например, можно было бы создать последовательность, представляющую пифагорейские тройки как<integral_constant>с. Такая последовательность была бы бесконечной, но итерация на последовательности все равно была бы выполнена во время компиляции. Однако, если бы кто-то попытался повторитьвсеэлементы последовательности, компилятор зацикливался бы на неопределенный срок, в отличие от вашей программы, зацикливающейся на неопределенный срок, если бы последовательность была зацикленной.
В текущей версии библиотеки поддерживается только время компиляции<Iterable>с.Хотя теоретически было бы возможно поддерживать время выполнения<Iterable>, его эффективное выполнение является предметом некоторых исследований. В частности, следуйтеэтому вопросудля текущего состояния времени выполнения<Iterable>с.
Laws
Во-первых, мы требуем, чтобы равенство двух<Iterable>s было связано с равенством элементов в их линеаризации. Если<xs>и<ys>— два<Iterable>типа данных<It>, то
Это означает, что два<Iterable>должны иметь одинаковую линеаризацию, чтобы считаться равными.
Во-вторых, поскольку каждый<Iterable>также является<Searchable>, мы требуем, чтобы модели<Iterable>и<Searchable>были последовательными. Это уточняется следующими законами. Для любого<Iterable><xs>с линеаризацией<[x1, x2, x3, ...]>,
find_if(xs, pred) == just(the first xi such that pred(xi) is satisfied)
или<nothing>, если такой<xi>не существует.
Refined concepts
Searchable(бесплатная модель) ЛюбойIterableдаёт начало моделиSearchable, где ключи и значения являются элементами в структуре. Поиск ключа — это просто линейный поиск по элементам структуры.
// Авторское право Louis Dionne 2013-2016
// Распространяется под лицензией Boost Software License, версия 1.0.
// (См. сопроводительный файл LICENSE.md или копию на http://boost.org/LICENSE_1_0.txt)
Foldableдля конечногоIterables Всякое конечноеIterableпорождает модельFoldable. Чтобы эти модели были последовательными, мы требуем, чтобы моделиFoldableиIterableимели одинаковую линеаризацию.
Note
As explained above, Iterables are also Searchables and their models have to be consistent. By the laws presented here, it also means that the Foldable model for finite Iterables has to be consistent with the Searchable model.
Для удобства конечные<Iterable>s должны давать только определение<length>для моделирования концепции<Foldable>; определение более мощных<unpack>или<fold_left>не требуется (но все же возможно). Реализация по умолчанию<unpack>, полученная из<Iterable>+<length>, использует тот факт, что<at(xs, i)>обозначает<i>элемент линейности<xs>, и что линейность конечного<Iterable>должна быть такой же, как и его линейность<Foldable>.
Returns the nth element of an iterable.Given an Iterable and an IntegralConstant index, at returns the element located at the index in the linearization of the iterable. Specifically, given an iterable xs with a linearization of [x1, ..., xN], at(xs, k) is equivalent to xk. More...
Returns the last element of a non-empty and finite iterable.Given a non-empty and finite iterable xs with a linearization of [x1, ..., xN], back(xs) is equal to xN. Equivalently, back(xs) must be equivalent to at_c<N-1>(xs), and that regardless of the value category of xs (back must respect the reference semantics of at). More...
Drop the first n elements of an iterable, and return the rest.Given an Iterablexs with a linearization of [x1, x2, ...] and a non-negative IntegralConstantn, drop_front(xs, n) is an iterable with the same tag as xs whose linearization is [xn+1, xn+2, ...]. In particular, note that this function does not mutate the original iterable in any way. If n is not given, it defaults to an IntegralConstant with a value equal to 1. More...
Drop the first n elements of an iterable, and return the rest.Given an Iterablexs with a linearization of [x1, x2, ...] and a non-negative IntegralConstantn, drop_front_exactly(xs, n) is an iterable with the same tag as xs whose linearization is [xn+1, xn+2, ...]. In particular, note that this function does not mutate the original iterable in any way. If n is not given, it defaults to an IntegralConstant with a value equal to 1. More...
Drop elements from an iterable up to, but excluding, the first element for which the predicate is not satisfied.Specifically, drop_while returns an iterable containing all the elements of the original iterable except for those in the range delimited by [head, e), where head is the first element and e is the first element for which the predicate is not satisfied. If the iterable is not finite, the predicate has to return a false- valued Logical at a finite index for this method to return. More...
Returns the first element of a non-empty iterable.Given a non-empty Iterable xs with a linearization of [x1, ..., xN], front(xs) is equal to x1. If xs is empty, it is an error to use this function. Equivalently, front(xs) must be equivalent to at_c<0>(xs), and that regardless of the value category of xs (front must respect the reference semantics of at). More...
Returns whether the iterable is empty.Given an Iterablexs, is_empty returns whether xs contains no more elements. In other words, it returns whether trying to extract the tail of xs would be an error. In the current version of the library, is_empty must return an IntegralConstant holding a value convertible to bool. This is because only compile-time Iterables are supported right now. More...
Short-circuiting lexicographical comparison of two Iterables with an optional custom predicate, by default hana::less.Given two Iterables xs and ys and a binary predicate pred, lexicographical_compare returns whether xs is to be considered less than ys in a lexicographical ordering. Specifically, let's denote the linearizations of xs and ys by [x1, x2, ...] and [y1, y2, ...], respectively. If the first couple satisfying the predicate is of the form xi, yi, lexicographical_compare returns true. Otherwise, if the first couple to satisfy the predicate is of the form yi, xi, lexicographical_compare returns false. If no such couple can be found, lexicographical_compare returns whether xs has fewer elements than ys. More...
Возвращает<n>элемент итерации. Учитывая<Iterable>и<IntegralConstant>индекс,<at>возвращает элемент, расположенный в индексе, в линеаризации итерируемого. В частности, учитывая итерабельность<xs>с линеаризацией<[x1, ..., xN]>,<at(xs, k)>эквивалентен<xk>.
Если<Iterable>на самом деле хранит элементы, которые он содержит,<at>требуется вернуть ссылку на lvalue, ссылку на lvalue на const или ссылку на rvalue на соответствующий элемент, где тип ссылки должен соответствовать типу ссылки, передаваемой на<at>. Если<Iterable>не хранит элементы, которые он содержит (т.е. генерирует их по требованию), это требование отпадает.
Parameters
xs
Итерация, в которой элемент извлекается. Он должен содержать не менее 92 элементов.
n
Неотрицательный<IntegralConstant>, представляющий нулевой индекс элемента для возврата. Ошибочно называть<at>индексом, который выходит за пределы итерируемого.
Example
// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
Returns the nth element of an iterable.Given an Iterable and an IntegralConstant index, at returns the element located at the index in the linearization of the iterable. Specifically, given an iterable xs with a linearization of [x1, ..., xN], at(xs, k) is equivalent to xk.
Definition: at.hpp:50
<at>Для удобства.
Note
hana::at_c<n> is an overloaded function, not a function object. Hence, it can't be passed to higher-order algorithms. This is done for compile-time performance reasons.
Example
// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
Возвращает последний элемент непустого и конечного итерабельного. При непустой и конечной итерации<xs>с линеаризацией<[x1, ..., xN]><back(xs)>равно<xN>. Эквивалентно<back(xs)>должно быть эквивалентно<at_c<N-1>(xs)>, и что независимо от ценностной категории<xs><back>должно соблюдать эталонную семантику<at>.
Example
// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
Опустить первые 108 элементов и вернуть остальные.<Iterable><xs>с линеаризацией<[x1, x2, ...]>и неотрицательной<IntegralConstant><n>,<drop_front(xs, n)>является итерируемым с той же меткой, что и<xs>, линеаризация которого<[xn+1, xn+2, ...]>. В частности, обратите внимание, что эта функция никоим образом не мутирует исходный итерируемый. Если<n>не дано, он по умолчанию<IntegralConstant>со значением, равным<1>.
В случае<length(xs) <= n>,<drop_front>просто отбросит весь итерируемый без отказа, таким образом возвращая пустой итерируемый. Это отличается от<drop_front_exactly>, который ожидает<n <= length(xs)>, но может быть лучше оптимизирован из-за этой дополнительной гарантии.
Parameters
xs
Итерабельность, из которой выпадают элементы.
n
Неотрицательный<IntegralConstant>, представляющий количество элементов, которые должны быть выброшены из итерабельного. Если<n>не дано, он по умолчанию<IntegralConstant>со значением, равным<1>.
Example
// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
Откажитесь от первых 129 элементов и верните остальные.<Iterable><xs>с линеаризацией<[x1, x2, ...]>и неотрицательным<IntegralConstant><n>,<drop_front_exactly(xs, n)>является итерируемым с той же меткой, что и<xs>, линеаризация которого<[xn+1, xn+2, ...]>. В частности, обратите внимание, что эта функция никоим образом не мутирует исходный итерируемый. Если<n>не дано, он по умолчанию<IntegralConstant>со значением, равным<1>.
Ошибка в использовании<drop_front_exactly>с<n > length(xs)>. Эта дополнительная гарантия позволяет лучше оптимизировать<drop_front_exactly>, чем функция<drop_front>, которая позволяет<n > length(xs)>.
Parameters
xs
Итерабельность, из которой выпадают элементы.
n
Неотрицательный<IntegralConstant>, представляющий число элементов, которые должны быть выброшены из итерируемого. В дополнение к тому, чтобы быть неотрицательным,<n>должно быть меньше или равно количеству элементов в<xs>. Если<n>не дано, он по умолчанию<IntegralConstant>со значением, равным<1>.
Example
// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
Отбрасывайте элементы от повторяемого до первого элемента, для которого<predicate>не удовлетворяется. В частности,<drop_while>возвращает итерируемый элемент, содержащий все элементы оригинального итерируемого, за исключением тех, которые находятся в диапазоне, ограниченном<head>,<e>, где<head>является первым элементом и<e>является первым элементом, для которого<predicate>не удовлетворяется. Если итерируемое не является конечным, то<predicate>должно вернуть ложное значение<Logical>при конечном индексе для возврата этого метода.
Parameters
iterable
Итерабельность, из которой выпадают элементы.
predicate
Функция, называемая<predicate(x)>, где<x>является элементом структуры, и возвращающая<Logical>, представляющая, следует ли<x>выбросить из структуры. В текущей версии библиотеки<predicate>должно вернуться время компиляции<Logical>.
Example
// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
Возвращает первый элемент непустого итерируемого. При непустом итерируемом<xs>с линеаризацией<[x1, ..., xN]>,<front(xs)>равно<x1>. Если<xs>пуст, то использовать эту функцию ошибочно. Равнозначно<front(xs)>должно быть эквивалентно<at_c<0>(xs)>, и что независимо от ценностной категории<xs><front>должно соблюдать эталонную семантику<at>.
Example
// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
Возвращает ли итерируемый пустой.<Iterable><xs>,<is_empty>возвращает<xs>не содержит больше элементов. Иными словами, он возвращает, будет ли попытка извлечь хвост<xs>ошибкой. В текущей версии библиотеки<is_empty>должно быть возвращено<IntegralConstant>значение, конвертируемое в<bool>. Это связано с тем, что сейчас поддерживается только время компиляции<Iterable>.
Example
// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
Returns a Logical representing whether x is less than y.
Definition: less.hpp:37
Краткосрочное лексикографическое сравнение двух<Iterable>с необязательным пользовательским предикатом по умолчанию<hana::less>.Учитывая два<Iterable>с<xs>и<ys>и двоичный предикат<pred>,<lexicographical_compare>возвращает, следует ли<xs>считать менее<ys>в лексикографическом порядке. Конкретно, давайте обозначим линейности<xs>и<ys><[x1, x2, ...]>и<[y1, y2, ...]>соответственно. Если первая пара, удовлетворяющая предикату, имеет форму<xi, yi>,<lexicographical_compare>возвращается истинной. В противном случае, если первая пара, удовлетворяющая предикату, имеет форму<yi, xi>,<lexicographical_compare>возвращается ложной. Если такой пары нет,<lexicographical_compare>возвращает<xs>меньше элементов, чем<ys>.
Note
This algorithm will short-circuit as soon as it can determine that one sequence is lexicographically less than the other. Hence, it can be used to compare infinite sequences. However, for the procedure to terminate on infinite sequences, the predicate has to be satisfied at a finite index.
Signature
При наличии двух<Iterable>s<It1(T)>и<It2(T)>и предиката \(предварительно: T \times T \to Bool \) (где<Bool>является неким<Logical>),<lexicographical_compare>имеет следующие подписи. Для варианта с заданным предикатом,
Бинарная функция называется<pred(x, y)>и<pred(y, x)>, где<x>и<y>являются элементами<xs>и<ys>соответственно.<pred>должен вернуть<Logical>, представляя, следует ли считать его первый аргумент меньшим, чем его второй аргумент. Также обратите внимание, что<pred>должен определять общую упорядоченность, как определено концепцией<Orderable>. Когда<pred>не предусмотрено, он по умолчанию<less>.
Example
// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
