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

Авторские права	(c) Росс Патерсон 2005 (c) Луи Вассерман 2009 (c) Дэвид Фир, Росс Патерсон и Милан Страка 2014
Лицензия	BSD-стиль
Поддержка	libraries@haskell.org
Стабильность	экспериментальная
Переносимость	переносимая
Safe Haskell	Надежная
Язык	Haskell98

тип Seq a Источник

Последовательности конечной длины общего назначения.

Создание

empty :: Seq a Источник

O(1). Пустая последовательность.

singleton :: a -> Seq a Источник

O(1). Последовательность из одного элемента.

(<|) :: a -> Seq a -> Seq a infixr 5 Источник

O(1). Добавление элемента в левую часть последовательности. Мемоническое обозначение: треугольник с одиночным элементом в вершине.

(|>) :: Seq a -> a -> Seq a infixl 5 Источник

O(1). Добавление элемента в правую часть последовательности. Мемоническое обозначение: треугольник с одиночным элементом в вершине.

(><) :: Seq a -> Seq a -> Seq a infixr 5 Источник

O(log(min(n1,n2))). Объединение двух последовательностей.

fromList :: [a] -> Seq a Источник

O(n). Создание последовательности из конечного списка элементов. Существует функция toList в противоположном направлении для всех экземпляров класса Foldable, включая Seq.

fromFunction :: Int -> (Int -> a) -> Seq a Источник

O(n). Преобразование заданной длины последовательности и функции, представляющей эту последовательность, в последовательность.

fromArray :: Ix i => Массив i a -> Seq a Источник

O(n). Создание последовательности, состоящей из элементов Array. Обратите внимание, что элементы результирующей последовательности могут быть вычислены лениво (как в GHC), поэтому необходимо принудительно вычислить всю структуру, чтобы убедиться, что исходный массив можно удалить из памяти.

Повторение

replicate :: Int -> a -> Seq a Источник

O(log n). replicate n x — это последовательность, состоящая из n копий x.

replicateA :: Applicative f => Int -> f a -> f (Seq a) Источник

replicateA — это версия replicate, использующая <*> и pure, осуществляя вызовы в O(log n).

replicateA n x = sequenceA (replicate n x)

replicateM :: Monad m => Int -> m a -> m (Seq a) Источник

replicateM — аналог replicateM для последовательностей.

replicateM n x = sequence (replicate n x)

Итеративное создание

iterateN :: Int -> (a -> a) -> a -> Seq a Источник

O(n). Строит последовательность путём многократного применения функции к начальному значению.

iterateN n f x = fromList (Prelude.take n (Prelude.iterate f x))

unfoldr :: (b -> Maybe (a, b)) -> b -> Seq a Source

Создаёт последовательность из начального значения. Занимает время, линейно зависящее от количества сгенерированных элементов. ПРЕДУПРЕЖДЕНИЕ: Если количество сгенерированных элементов бесконечно, этот метод не завершится.

unfoldl :: (b -> Maybe (b, a)) -> b -> Seq a Source

unfoldl f x is equivalent to reverse (unfoldr (fmap swap . f) x).

Разбиение

Дополнительные функции для разбиения последовательностей доступны через Foldable экземпляр Seq.

Запросы

null :: Seq a -> Bool Source

O(1). Является ли это пустой последовательностью?

length :: Seq a -> Int Source

O(1). Количество элементов в последовательности.

Представления

data ViewL a Source

Представление левого конца последовательности.

viewl :: Seq a -> ViewL a Source

O(1). Анализ левого конца последовательности.

data ViewR a Source

Представление правого конца последовательности.

viewr :: Seq a -> ViewR a Source

O(1). Анализ правого конца последовательности.

Сканирование

scanl :: (a -> b -> a) -> a -> Seq b -> Seq a Source

scanl is similar to foldl, but returns a sequence of reduced values from the left:

scanl f z (fromList [x1, x2, ...]) = fromList [z, z `f` x1, (z `f` x1) `f` x2, ...]

scanl1 :: (a -> a -> a) -> Seq a -> Seq a Source

scanl1 is a variant of scanl that has no starting value argument:

scanl1 f (fromList [x1, x2, ...]) = fromList [x1, x1 `f` x2, ...]

scanr :: (a -> b -> b) -> b -> Seq a -> Seq b Source

scanr is the right-to-left dual of scanl.

scanr1 :: (a -> a -> a) -> Seq a -> Seq a Source

scanr1 is a variant of scanr that has no starting value argument.

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

tails :: Seq a -> Seq (Seq a) Source

O(n). Возвращает последовательность всех суффиксов этой последовательности, начиная с самого длинного. Например,

tails (fromList "abc") = fromList [fromList "abc", fromList "bc", fromList "c", fromList ""]

Вычисление i-го суффикса занимает O(log(min(i, n-i))), но вычисление всех суффиксов в последовательности занимает O(n) благодаря общим данным.

inits :: Seq a -> Seq (Seq a) Source

O(n). Возвращает последовательность всех префиксов этой последовательности, начиная с самого короткого. Например,

inits (fromList "abc") = fromList [fromList "", fromList "a", fromList "ab", fromList "abc"]

Вычисление i-го префикса занимает O(log(min(i, n-i))), но вычисление всех префиксов в последовательности занимает O(n) благодаря общим данным.

Последовательный поиск

takeWhileL :: (a -> Bool) -> Seq a -> Seq a Source

O(i) где i - длина префикса. takeWhileL, применённый к предикату p и последовательности xs, возвращает самый длинный префикс (возможно, пустой) xs элементов, которые удовлетворяют p.

takeWhileR :: (a -> Bool) -> Seq a -> Seq a Source

O(i) где i — длина суффикса. takeWhileR, применённая к предикату p и последовательности xs, возвращает самый длинный суффикс (возможно, пустой) последовательности xs элементов, удовлетворяющих p.

takeWhileR p xs эквивалентно reverse (takeWhileL p (reverse xs)).

dropWhileL :: (a -> Bool) -> Seq a -> Seq a Source

O(i) где i — длина префикса. dropWhileL p xs возвращает суффикс, оставшийся после takeWhileL p xs.

dropWhileR :: (a -> Bool) -> Seq a -> Seq a Source

O(i) где i — длина суффикса. dropWhileR p xs возвращает префикс, оставшийся после takeWhileR p xs.

dropWhileR p xs эквивалентно reverse (dropWhileL p (reverse xs)).

spanl :: (a -> Bool) -> Seq a -> (Seq a, Seq a) Source

O(i) где i — длина префикса. spanl, применённая к предикату p и последовательности xs, возвращает пару, первым элементом которой является самый длинный префикс (возможно, пустой) последовательности xs элементов, удовлетворяющих p, а вторым — остаток последовательности.

spanr :: (a -> Bool) -> Seq a -> (Seq a, Seq a) Source

O(i) где i — длина суффикса. spanr, применённая к предикату p и последовательности xs, возвращает пару, первым элементом которой является самый длинный суффикс (возможно, пустой) последовательности xs элементов, удовлетворяющих p, а вторым — остаток последовательности.

breakl :: (a -> Bool) -> Seq a -> (Seq a, Seq a) Source

O(i) где i — индекс разрыва. breakl, применённая к предикату p и последовательности xs, возвращает пару, первым элементом которой является самый длинный префикс (возможно, пустой) последовательности xs элементов, не удовлетворяющих p, а вторым — остаток последовательности.

breakl p эквивалентно spanl (not . p).

breakr :: (a -> Bool) -> Seq a -> (Seq a, Seq a) Source

breakr p эквивалентно spanr (not . p).

partition :: (a -> Bool) -> Seq a -> (Seq a, Seq a) Source

O(n). Функция partition принимает предикат p и последовательность xs и возвращает последовательности элементов, которые удовлетворяют и не удовлетворяют предикату.

filter :: (a -> Bool) -> Seq a -> Seq a Source

O(n). Функция filter принимает предикат p и последовательность xs и возвращает последовательность элементов, удовлетворяющих предикату.

Сортировка

sort :: Ord a => Seq a -> Seq a Source

O(n log n). sort сортирует указанную Seq по естественному порядку элементов. Сортировка стабильная. Если стабильность не требуется, unstableSort может быть значительно быстрее, а также использовать меньше памяти.

sortBy :: (a -> a -> Ordering) -> Seq a -> Seq a Source

O(n log n). sortBy сортирует указанную Seq в соответствии с заданным компаратором. Сортировка стабильная. Если стабильность не требуется, unstableSortBy может быть значительно быстрее, а также использовать меньше памяти.

unstableSort :: Ord a => Seq a -> Seq a Source

O(n log n). unstableSort сортирует указанную Seq по естественному порядку элементов, но сортировка нестабильна. Этот алгоритм часто быстрее и использует меньше памяти, чем sort, и работает очень хорошо — часто вдвое быстрее, чем sort — когда последовательность уже почти отсортирована.

unstableSortBy :: (a -> a -> Ordering) -> Seq a -> Seq a Source

O(n log n). Обобщение unstableSort, unstableSortBy принимает произвольный компаратор и сортирует указанную последовательность. Сортировка нестабильна. Этот алгоритм часто быстрее и использует меньше памяти, чем sortBy, и работает очень хорошо — часто вдвое быстрее, чем sortBy — когда последовательность уже почти отсортирована.

Индексирование

index :: Seq a -> Int -> a Source

O(log(min(i,n-i))). Элемент в указанной позиции, считая с 0. Аргумент должен быть неотрицательным целым числом, меньшим размера последовательности. Если позиция вне диапазона, index завершается ошибкой.

adjust :: (a -> a) -> Int -> Seq a -> Seq a Source

O(log(min(i,n-i))). Обновление элемента в указанной позиции. Если позиция вне диапазона, возвращается исходная последовательность.

update :: Int -> a -> Seq a -> Seq a Source

O(log(min(i,n-i))). Замена элемента в указанной позиции. Если позиция вне диапазона, возвращается исходная последовательность.

take :: Int -> Seq a -> Seq a Source

O(log(min(i,n-i))). Первые i элементы последовательности. Если i отрицательно, take i s возвращает пустую последовательность. Если последовательность содержит меньше, чем i элементов, возвращается вся последовательность.

drop :: Int -> Seq a -> Seq a Source

O(log(min(i,n-i))). Элементы последовательности после первого i. Если i отрицательно, drop i s возвращает всю последовательность. Если последовательность содержит меньше i элементов, возвращается пустая последовательность.

splitAt :: Int -> Seq a -> (Seq a, Seq a) Source

O(log(min(i,n-i))). Разделение последовательности по заданной позиции. splitAt i s = (take i s, drop i s).

Индексирование с помощью предикатов

Эти функции выполняют последовательный поиск с левого или правого конца последовательности, возвращая индексы совпадающих элементов.

elemIndexL :: Eq a => a -> Seq a -> Maybe Int Source

elemIndexL находит левосторонний индекс указанного элемента, если он присутствует, в противном случае Nothing.

elemIndicesL :: Eq a => a -> Seq a -> [Int] Source

elemIndicesL находит индексы указанного элемента слева направо (т.е. в порядке возрастания).

elemIndexR :: Eq a => a -> Seq a -> Maybe Int Source

elemIndexR находит правосторонний индекс указанного элемента, если он присутствует, в противном случае Nothing.

elemIndicesR :: Eq a => a -> Seq a -> [Int] Source

elemIndicesR находит индексы указанного элемента справа налево (т.е. в порядке убывания).

findIndexL :: (a -> Bool) -> Seq a -> Maybe Int Source

findIndexL p xs находит индекс левостороннего элемента, удовлетворяющего p, если таковые существуют.

findIndicesL :: (a -> Bool) -> Seq a -> [Int] Source

findIndicesL p находит все индексы элементов, удовлетворяющих p, в порядке возрастания.

findIndexR :: (a -> Bool) -> Seq a -> Maybe Int Source

findIndexR p xs находит индекс правостороннего элемента, удовлетворяющего p, если таковые существуют.

findIndicesR :: (a -> Bool) -> Seq a -> [Int] Source

findIndicesR p находит все индексы элементов, удовлетворяющих p, в порядке убывания.

Складывание

Общие складывания доступны через Foldable экземпляр Seq.

foldlWithIndex :: (b -> Int -> a -> b) -> b -> Seq a -> b Source

foldlWithIndex — это версия foldl, которая также предоставляет доступ к индексу каждого элемента.

foldrWithIndex :: (Int -> a -> b -> b) -> b -> Seq a -> b Source

foldrWithIndex — это версия foldr, которая также предоставляет доступ к индексу каждого элемента.

Преобразования

mapWithIndex :: (Int -> a -> b) -> Seq a -> Seq b Source

O(n). Обобщение fmap, mapWithIndex принимает функцию отображения, также зависящую от индекса элемента, и применяет её к каждому элементу в последовательности.

reverse :: Seq a -> Seq a Source

O(n). Обратная последовательность.

Сжатия

zip :: Seq a -> Seq b -> Seq (a, b) Source

O(min(n1,n2)). zip берёт две последовательности и возвращает последовательность соответствующих пар. Если один вход короче, лишние элементы отбрасываются с правого конца более длинной последовательности.

zipWith :: (a -> b -> c) -> Seq a -> Seq b -> Seq c Source

O(min(n1,n2)). zipWith обобщает zip путём сжатия с помощью функции, заданной в качестве первого аргумента, вместо функции туплирования. Например, zipWith (+) применяется к двум последовательностям, чтобы получить последовательность соответствующих сумм.

zip3 :: Seq a -> Seq b -> Seq c -> Seq (a, b, c) Source

O(min(n1,n2,n3)). zip3 берёт три последовательности и возвращает последовательность троек, аналогично zip.

zipWith3 :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d Source

O(min(n1,n2,n3)). zipWith3 берёт функцию, которая объединяет три элемента, а также три последовательности и возвращает последовательность их точечных комбинаций, аналогично zipWith.

zip4 :: Seq a -> Seq b -> Seq c -> Seq d -> Seq (a, b, c, d) Source

O(min(n1,n2,n3,n4)). zip4 берёт четыре последовательности и возвращает последовательность четвёрок, аналогично zip.

zipWith4 :: (a -> b -> c -> d -> e) -> Seq a -> Seq b -> Seq c -> Seq d -> Seq e Source

O(min(n1,n2,n3,n4)). zipWith4 берёт функцию, которая объединяет четыре элемента, а также четыре последовательности и возвращает последовательность их точечных комбинаций, аналогично zipWith.