Список.Список

data Список a Источник

Встроенный тип связанного списка.

В Haskell списки являются одним из важнейших типов данных, так как они часто используются аналогично циклам в императивных языках программирования. Эти списки являются односвязными, что делает их непригодными для операций, требующих доступ \(\mathcal{O}(1)\). Вместо этого они предназначены для обхода.

Вы можете использовать List a или [a] в сигнатурах типов:

length :: [a] -> Int

или

length :: List a -> Int

Они полностью эквивалентны, и List a будет нормализовано до [a].

Использование

Списки строятся рекурсивно с использованием правого ассоциативного оператора конструктора (или cons) (:) :: a -> [a] -> [a], который добавляет элемент в начало списка, и пустого списка [].

(1 : 2 : 3 : []) == (1 : (2 : (3 : []))) == [1, 2, 3]

Списки также можно создавать, используя литералы списков вида [x_1, x_2, ..., x_n], которые являются синтаксическим сахаром и, если не включена опция -XOverloadedLists, переводятся в использование (:) и []

Литералы String, такие как "I 💜 hs", переводятся в списки символов, ['I', ' ', '💜', ' ', 'h', 's'].

Реализация

╭───┬───┬──╮   ╭───┬───┬──╮   ╭───┬───┬──╮   ╭────╮
│(:)│   │ ─┼──>│(:)│   │ ─┼──>│(:)│   │ ─┼──>│ [] │
╰───┴─┼─┴──╯   ╰───┴─┼─┴──╯   ╰───┴─┼─┴──╯   ╰────╯
      v              v              v
      1              2              3

Примеры

>>> ['H', 'a', 's', 'k', 'e', 'l', 'l']
"Haskell"

>>> 1 : [4, 1, 5, 9]
[1,4,1,5,9]

>>> [] : [] : []
[[],[]]

С момента: ghc-prim-0.10.0

(++) :: [a] -> [a] -> [a] infixr 5 Исходный код

(++) добавляет две списки, то есть

[x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
[x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]

Если первый список не конечен, результатом является первый список.

Рассмотрение производительности

Примеры

>>> [1, 2, 3] ++ [4, 5, 6]
[1,2,3,4,5,6]

>>> [] ++ [1, 2, 3]
[1,2,3]

>>> [3, 2, 1] ++ []
[3,2,1]

head :: HasCallStack => [a] -> a Исходный код

\(\mathcal{O}(1)\). Извлечь первый элемент списка, который должен быть не пустым.

Чтобы отключить предупреждение о частичности, поместите {-# OPTIONS_GHC -Wno-x-partial -Wno-unrecognised-warning-flags #-} вверху файла. Чтобы отключить его во всем пакете, поместите те же параметры в раздел ghc-options файла Cabal. Чтобы отключить его в GHCi, поместите :set -Wno-x-partial -Wno-unrecognised-warning-flags в файл конфигурации ~/.ghci. См. также руководство по миграции.

Примеры

>>> head [1, 2, 3]
1

>>> head [1..]
1

>>> head []
*** Exception: Prelude.head: empty list

last :: HasCallStack => [a] -> a Источник

\(\mathcal{O}(n)\). Извлечь последний элемент списка, который должен быть конечным и непустым.

ПРЕДУПРЕЖДЕНИЕ: Эта функция частичная. Рассмотрите использование unsnoc вместо неё.

Примеры

>>> last [1, 2, 3]
3

>>> last [1..]
* Hangs forever *

>>> last []
*** Exception: Prelude.last: empty list

tail :: HasCallStack => [a] -> [a] Источник

\(\mathcal{O}(1)\). Извлечь элементы после первого элемента списка, который должен быть непустым.

Чтобы отключить предупреждение о частичности, поместите {-# OPTIONS_GHC -Wno-x-partial -Wno-unrecognised-warning-flags #-} вверху файла. Чтобы отключить его во всём пакете, поместите те же параметры в раздел ghc-options файла Cabal. Чтобы отключить его в GHCi, поместите :set -Wno-x-partial -Wno-unrecognised-warning-flags в файл конфигурации ~/.ghci. См. также руководство по миграции.

Примеры

>>> tail [1, 2, 3]
[2,3]

>>> tail [1]
[]

>>> tail []
*** Exception: Prelude.tail: empty list

init :: HasCallStack => [a] -> [a] Источник

\(\mathcal{O}(n)\). Возвратить все элементы списка, кроме последнего. Список должен быть непустым.

ПРЕДУПРЕЖДЕНИЕ: Эта функция частичная. Рассмотрите использование unsnoc вместо неё.

Примеры

>>> init [1, 2, 3]
[1,2]

>>> init [1]
[]

>>> init []
*** Exception: Prelude.init: empty list

uncons :: [a] -> Maybe (a, [a]) Источник

\(\mathcal{O}(1)\). Разложить список на его head и tail.

• Если список пуст, возвращает Nothing.
• Если список непустой, возвращает Just (x, xs), где x - head списка, а xs - его tail.

Примеры

>>> uncons []
Nothing

>>> uncons [1]
Just (1,[])

>>> uncons [1, 2, 3]
Just (1,[2,3])

С момента: base-4.8.0.0

unsnoc :: [a] -> Maybe ([a], a) Источник

\(\mathcal{O}(n)\). Разложить список на init и last.

• Если список пуст, возвращает Nothing.
• Если список непустой, возвращает Just (xs, x), где xs - init часть списка, а x - его last элемент.

unsnoc является двойственной к uncons: для конечного списка xs

unsnoc xs = (\(hd, tl) -> (reverse tl, hd)) <$> uncons (reverse xs)

Примеры

>>> unsnoc []
Nothing

>>> unsnoc [1]
Just ([],1)

>>> unsnoc [1, 2, 3]
Just ([1,2],3)

Ленивость

>>> fst <$> unsnoc [undefined]
Just []

>>> head . fst <$> unsnoc (1 : undefined)
Just *** Exception: Prelude.undefined

>>> head . fst <$> unsnoc (1 : 2 : undefined)
Just 1

С момента: base-4.19.0.0

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

Создать список из одного элемента.

Примеры

>>> singleton True
[True]

>>> singleton [1, 2, 3]
[[1,2,3]]

>>> singleton 'c'
"c"

С момента: base-4.15.0.0

null :: Foldable t => t a -> Bool Источник

Проверить, пустая ли структура. По умолчанию левоассоциативна и ленива как в начальном элементе, так и в аккумуляторе. Таким образом, оптимизирована для структур, где первый элемент можно получить за постоянное время. Структуры, где это не так, должны иметь реализацию отличную от по умолчанию.

Примеры

>>> null []
True

>>> null [1]
False

>>> null [1..]
False

С момента: base-4.8.0.0

length :: Foldable t => t a -> Int Источник

Возвращает размер/длину конечной структуры как Int. Реализация по умолчанию просто считает элементы, начиная с самого левого. Экземпляры для структур, которые могут вычислить количество элементов быстрее, чем путем подсчета по элементам, должны предоставить специализированную реализацию.

Примеры

>>> length []
0

>>> length ['a', 'b', 'c']
3
>>> length [1..]
* Hangs forever *

С момента: base-4.8.0.0

compareLength :: [a] -> Int -> Ordering Источник

Используйте compareLength xs n в качестве более безопасной и быстрой альтернативы compare (length xs) n. Аналогично, лучше написать compareLength xs 10 == LT вместо length xs < 10.

В то время как length принудит и пройдёт по всей спине xs (что может даже разойтись, если xs бесконечно), compareLength пройдёт по максимум n элементам, чтобы определить свой результат.

>>> compareLength [] 0
EQ
>>> compareLength [] 1
LT
>>> compareLength ['a'] 1
EQ
>>> compareLength ['a', 'b'] 1
GT
>>> compareLength [0..] 100
GT
>>> compareLength undefined (-1)
GT
>>> compareLength ('a' : undefined) 0
GT

С момента: base-4.21.0.0

map :: (a -> b) -> [a] -> [b] Источник

\(\mathcal{O}(n)\). map f xs - это список, полученный путем применения f к каждому элементу xs, т.е.,

map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
map f [x1, x2, ...] == [f x1, f x2, ...]

это означает, что map id == id

Примеры

>>> map (+1) [1, 2, 3]
[2,3,4]

>>> map id [1, 2, 3]
[1,2,3]

>>> map (\n -> 3 * n + 1) [1, 2, 3]
[4,7,10]

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

\(\mathcal{O}(n)\). reverse xs возвращает элементы xs в обратном порядке. xs должен быть конечным.

Ленивость

>>> head (reverse [undefined, 1])
1

>>> reverse (1 : 2 : undefined)
*** Exception: Prelude.undefined

Примеры

>>> reverse []
[]

>>> reverse [42]
[42]

>>> reverse [2,5,7]
[7,5,2]

>>> reverse [1..]
* Hangs forever *

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

\(\mathcal{O}(n)\). The intersperse function takes an element and a list and `intersperses' that element between the elements of the list.

Ленивость

>>> take 1 (intersperse undefined ('a' : undefined))
"a"

>>> take 2 (intersperse ',' ('a' : undefined))
"a*** Exception: Prelude.undefined

Примеры

>>> intersperse ',' "abcde"
"a,b,c,d,e"

>>> intersperse 1 [3, 4, 5]
[3,1,4,1,5]

intercalate :: [a] -> [[a]] -> [a] Исходный код

intercalate xs xss эквивалентно (concat (intersperse xs xss)). Оно вставляет список xs между списками в xss и конкатенирует результат.

Ленивость

>>> take 5 (intercalate undefined ("Lorem" : undefined))
"Lorem"

>>> take 6 (intercalate ", " ("Lorem" : undefined))
"Lorem*** Exception: Prelude.undefined

Примеры

>>> intercalate ", " ["Lorem", "ipsum", "dolor"]
"Lorem, ipsum, dolor"

>>> intercalate [0, 1] [[2, 3], [4, 5, 6], []]
[2,3,0,1,4,5,6,0,1]

>>> intercalate [1, 2, 3] [[], []]
[1,2,3]

transpose :: [[a]] -> [[a]] Исходный код

Функция transpose транспонирует строки и столбцы своего аргумента.

Ленивость

>>> take 1 (transpose ['a' : undefined, 'b' : undefined])
["ab"]

Примеры

>>> transpose [[1,2,3],[4,5,6]]
[[1,4],[2,5],[3,6]]

>>> transpose [[10,11],[20],[],[30,31,32]]
[[10,20,30],[11,31],[32]]

>>> transpose (repeat [])
* Hangs forever *

subsequences :: [a] -> [[a]] Исходный код

Функция subsequences возвращает список всех подпоследовательностей аргумента.

Ленивость

>>> take 1 (subsequences undefined)
[[]]
>>> take 2 (subsequences ('a' : undefined))
["","a"]

Примеры

>>> subsequences "abc"
["","a","b","ab","c","ac","bc","abc"]

>>> take 8 $ subsequences ['a'..]
["","a","b","ab","c","ac","bc","abc"]

permutations :: [a] -> [[a]] Исходный код

Функция permutations возвращает список всех перестановок аргумента.

Обратите внимание, что порядок перестановок не лексикографический. Он удовлетворяет следующему свойству:

map (take n) (take (product [1..n]) (permutations ([1..n] ++ undefined))) == permutations [1..n]

Ленивость

Примеры

>>> permutations "abc"
["abc","bac","cba","bca","cab","acb"]

>>> permutations [1, 2]
[[1,2],[2,1]]

>>> permutations []
[[]]

>>> take 6 $ map (take 3) $ permutations ['a'..]
["abc","bac","cba","bca","cab","acb"]

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b Исходный код

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

В случае списков, foldl, при применении к бинарному оператору, начальному значению (обычно левому тождеству оператора) и списку, сводит список с помощью бинарного оператора слева направо:

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

Обратите внимание, что для получения внешнего применения оператора необходимо пройти весь входной список. Как и все левоассоциативные свертки, foldl расходится при бесконечном списке.

Если вам нужна эффективная строгая левосторонняя свертка, вы, вероятно, хотите использовать foldl' вместо foldl. Причина в том, что последняя не принуждает внутренние результаты (например, z `f` x1 в приведенном выше примере) перед их применением к оператору (например, к (`f` x2)). Это приводит к цепочке ленивых вычислений длиной O(n) элементов, которые затем должны быть вычислены снаружи вовнутрь.

Для общей структуры Foldable это должно быть семантически идентично:

foldl f z = foldl f z . toList

Примеры

>>> foldl (+) 42 [1,2,3,4]
52

>>> foldl (\acc c -> c : acc) "abcd" "efgh"
"hgfeabcd"

>>> foldl (\a _ -> a) 0 $ repeat 1
* Hangs forever *

foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b Исходный код

Левоассоциативная свертка структуры, но со строгим применением оператора.

Это гарантирует, что каждый шаг свертки приводится к слабой нормальной форме перед применением, избегая сбора ленивых вычислений, которые в противном случае возникли бы. Это часто то, что вам нужно для строгого сокращения конечной структуры до единственного строгого результата (например, sum).

Для общей структуры Foldable это должно быть семантически идентично,

foldl' f z = foldl' f z . toList

С момента: base-4.6.0.0

foldl1 :: Foldable t => (a -> a -> a) -> t a -> a Исходный код

Вариант foldl, у которого нет базового случая, и поэтому он может применяться только к непустым структурам.

Эта функция неполна и вызовет исключение во время выполнения, если структура окажется пустой.

foldl1 f = foldl1 f . toList

Примеры

>>> foldl1 (+) [1..4]
10

>>> foldl1 (+) []
*** Exception: Prelude.foldl1: empty list

>>> foldl1 (+) Nothing
*** Exception: foldl1: empty structure

>>> foldl1 (-) [1..4]
-8

>>> foldl1 (&&) [True, False, True, True]
False

>>> foldl1 (||) [False, False, True, True]
True

>>> foldl1 (+) [1..]
* Hangs forever *

foldl1' :: HasCallStack => (a -> a -> a) -> [a] -> a Исходный код

Строгая версия foldl1.

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b Исходный код

Правоассоциативная свертка структуры, ленива по аккумулятору.

В случае списков, foldr, при применении к бинарному оператору, начальному значению (обычно правому тождеству оператора) и списку, сводит список с помощью бинарного оператора справа налево:

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

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

Для общей структуры Foldable это должно быть семантически идентично,

foldr f z = foldr f z . toList

Примеры

>>> foldr (||) False [False, True, False]
True

>>> foldr (||) False []
False

>>> foldr (\c acc -> acc ++ [c]) "foo" ['a', 'b', 'c', 'd']
"foodcba"

>>> foldr (||) False (True : repeat False)
True

>>> foldr (||) False (repeat False ++ [True])
* Hangs forever *

>>> take 5 $ foldr (\i acc -> i : fmap (+3) acc) [] (repeat 1)
[1,4,7,10,13]

foldr1 :: Foldable t => (a -> a -> a) -> t a -> a Источник

Вариант foldr, у которого нет базового случая, и поэтому он может применяться только к непустым структурам.

Эта функция неполная и вызовет исключение во время выполнения, если структура окажется пустой.

Примеры

>>> foldr1 (+) [1..4]
10

>>> foldr1 (+) []
Exception: Prelude.foldr1: empty list

>>> foldr1 (+) Nothing
*** Exception: foldr1: empty structure

>>> foldr1 (-) [1..4]
-2

>>> foldr1 (&&) [True, False, True, True]
False

>>> foldr1 (||) [False, False, True, True]
True

>>> foldr1 (+) [1..]
* Hangs forever *

concat :: Foldable t => t [a] -> [a] Источник

Конкатенация всех элементов контейнера списков.

Примеры

>>> concat (Just [1, 2, 3])
[1,2,3]

>>> concat (Left 42)
[]

>>> concat [[1, 2, 3], [4, 5], [6], []]
[1,2,3,4,5,6]

concatMap :: Foldable t => (a -> [b]) -> t a -> [b] Источник

Применение функции к всем элементам контейнера и конкатенация получившихся списков.

Примеры

>>> concatMap (take 3) [[1..], [10..], [100..], [1000..]]
[1,2,3,10,11,12,100,101,102,1000,1001,1002]

>>> concatMap (take 3) (Just [1..])
[1,2,3]

and :: Foldable t => t Bool -> Bool Источник

and возвращает конъюнкцию контейнера булевых значений. Для того чтобы результат был True, контейнер должен быть конечным; False, однако, результат получается из значения False на конечном расстоянии слева.

Примеры

>>> and []
True

>>> and [True]
True

>>> and [False]
False

>>> and [True, True, False]
False

>>> and (False : repeat True) -- Infinite list [False,True,True,True,...
False

>>> and (repeat True)
* Hangs forever *

or :: Foldable t => t Bool -> Bool Источник

or возвращает дизъюнкцию контейнера булевых значений. Для того чтобы результат был False, контейнер должен быть конечным; True, однако, результат получается из значения True на конечном расстоянии слева.

Примеры

>>> or []
False

>>> or [True]
True

>>> or [False]
False

>>> or [True, True, False]
True

>>> or (True : repeat False) -- Infinite list [True,False,False,False,...
True

>>> or (repeat False)
* Hangs forever *

any :: Foldable t => (a -> Bool) -> t a -> Bool Источник

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

Примеры

>>> any (> 3) []
False

>>> any (> 3) [1,2]
False

>>> any (> 3) [1,2,3,4,5]
True

>>> any (> 3) [1..]
True

>>> any (> 3) [0, -1..]
* Hangs forever *

all :: Foldable t => (a -> Bool) -> t a -> Bool Источник

Определяет, удовлетворяют ли все элементы структуры предикату.

Примеры

>>> all (> 3) []
True

>>> all (> 3) [1,2]
False

>>> all (> 3) [1,2,3,4,5]
False

>>> all (> 3) [1..]
False

>>> all (> 3) [4..]
* Hangs forever *

sum :: (Foldable t, Num a) => t a -> a Источник

Функция sum вычисляет сумму чисел в структуре.

Примеры

>>> sum []
0

>>> sum [42]
42

>>> sum [1..10]
55

>>> sum [4.1, 2.0, 1.7]
7.8

>>> sum [1..]
* Hangs forever *

С момента: base-4.8.0.0

product :: (Foldable t, Num a) => t a -> a Источник

Функция product вычисляет произведение чисел в структуре.

Примеры

>>> product []
1

>>> product [42]
42

>>> product [1..10]
3628800

>>> product [4.1, 2.0, 1.7]
13.939999999999998

>>> product [1..]
* Hangs forever *

С момента: base-4.8.0.0

maximum :: (Foldable t, Ord a) => t a -> a Источник

Наибольший элемент непустой структуры. Эта функция эквивалентна foldr1 max, и её поведение на структурах с несколькими наибольшими элементами зависит от соответствующей реализации max. В реализации max (max x y = if x <= y then y else x) используется порядок структуры для разбора ничьих: если есть несколько наибольших элементов, выбирается самый правый из них (что эквивалентно maximumBy compare).

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

Примеры

>>> maximum [1..10]
10

>>> maximum []
*** Exception: Prelude.maximum: empty list

>>> maximum Nothing
*** Exception: maximum: empty structure

С момента: base-4.8.0.0

minimum :: (Foldable t, Ord a) => t a -> a Источник

Наименьший элемент непустой структуры. Эта функция эквивалентна foldr1 min, и её поведение на структурах с несколькими наименьшими элементами зависит от соответствующей реализации min. В реализации min (min x y = if x <= y then x else y) используется порядок структуры для разбора ничьих: если есть несколько наименьших элементов, выбирается самый левый из них (что эквивалентно minimumBy compare).

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

Примеры

>>> minimum [1..10]
1

>>> minimum []
*** Exception: Prelude.minimum: empty list

>>> minimum Nothing
*** Exception: minimum: empty structure

С: base-4.8.0.0

scanl :: (b -> a -> b) -> b -> [a] -> [b] Источник

\(\mathcal{O}(n)\). scanl аналогично foldl, но возвращает список последовательных уменьшенных значений слева:

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

Обратите внимание, что

last (scanl f z xs) == foldl f z xs

Примеры

>>> scanl (+) 0 [1..4]
[0,1,3,6,10]

>>> scanl (+) 42 []
[42]

>>> scanl (-) 100 [1..4]
[100,99,97,94,90]

>>> scanl (\reversedString nextChar -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']
["foo","afoo","bafoo","cbafoo","dcbafoo"]

>>> take 10 (scanl (+) 0 [1..])
[0,1,3,6,10,15,21,28,36,45]

>>> take 1 (scanl undefined 'a' undefined)
"a"

scanl' :: (b -> a -> b) -> b -> [a] -> [b] Источник

\(\mathcal{O}(n)\). Строгая версия scanl.

scanl1 :: (a -> a -> a) -> [a] -> [a] Источник

\(\mathcal{O}(n)\). scanl1 — это вариант scanl, у которого нет аргумента начального значения:

scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]

Примеры

>>> scanl1 (+) [1..4]
[1,3,6,10]

>>> scanl1 (+) []
[]

>>> scanl1 (-) [1..4]
[1,-1,-4,-8]

>>> scanl1 (&&) [True, False, True, True]
[True,False,False,False]

>>> scanl1 (||) [False, False, True, True]
[False,False,True,True]

>>> take 10 (scanl1 (+) [1..])
[1,3,6,10,15,21,28,36,45,55]

>>> take 1 (scanl1 undefined ('a' : undefined))
"a"

scanr :: (a -> b -> b) -> b -> [a] -> [b] Источник

\(\mathcal{O}(n)\). scanr — это правая двойственная scanl. Обратите внимание, что порядок параметров в функции накопления обратный по сравнению с scanl. Также обратите внимание, что

head (scanr f z xs) == foldr f z xs.

Примеры

>>> scanr (+) 0 [1..4]
[10,9,7,4,0]

>>> scanr (+) 42 []
[42]

>>> scanr (-) 100 [1..4]
[98,-97,99,-96,100]

>>> scanr (\nextChar reversedString -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']
["abcdfoo","bcdfoo","cdfoo","dfoo","foo"]

>>> force $ scanr (+) 0 [1..]
*** Exception: stack overflow

scanr1 :: (a -> a -> a) -> [a] -> [a] Источник

\(\mathcal{O}(n)\). scanr1 — это вариант scanr, у которого нет аргумента начального значения.

Примеры

>>> scanr1 (+) [1..4]
[10,9,7,4]

>>> scanr1 (+) []
[]

>>> scanr1 (-) [1..4]
[-2,3,-1,4]

>>> scanr1 (&&) [True, False, True, True]
[False,False,True,True]

>>> scanr1 (||) [True, True, False, False]
[True,True,False,False]

>>> force $ scanr1 (+) [1..]
*** Exception: stack overflow

mapAccumL :: Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b) Источник

Функция mapAccumL ведет себя как комбинация fmap и foldl; она применяет функцию к каждому элементу структуры, передавая накопительный параметр слева направо, и возвращает конечное значение этого аккумулятора вместе с новой структурой.

Примеры

>>> mapAccumL (\a b -> (a + b, a)) 0 [1..10]
(55,[0,1,3,6,10,15,21,28,36,45])

>>> mapAccumL (\a b -> (a <> show b, a)) "0" [1..5]
("012345",["0","01","012","0123","01234"])

mapAccumR :: Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b) Источник

Функция mapAccumR ведет себя как комбинация fmap и foldr; она применяет функцию к каждому элементу структуры, передавая накопительный параметр справа налево, и возвращает конечное значение этого аккумулятора вместе с новой структурой.

Примеры

>>> mapAccumR (\a b -> (a + b, a)) 0 [1..10]
(55,[54,52,49,45,40,34,27,19,10,0])

>>> mapAccumR (\a b -> (a <> show b, a)) "0" [1..5]
("054321",["05432","0543","054","05","0"])

iterate :: (a -> a) -> a -> [a] Источник

iterate f x возвращает бесконечный список повторяющихся применений f к x:

iterate f x == [x, f x, f (f x), ...]

Лень

>>> take 1 $ iterate undefined 42
[42]

Примеры

>>> take 10 $ iterate not True
[True,False,True,False,True,False,True,False,True,False]

>>> take 10 $ iterate (+3) 42
[42,45,48,51,54,57,60,63,66,69]

>>> take 10 $ iterate id 1
[1,1,1,1,1,1,1,1,1,1]

iterate' :: (a -> a) -> a -> [a] Источник

iterate' — это строгая версия iterate.

Она заставляет результат каждого применения функции к слабой нормальной форме (WHNF) перед продолжением.

>>> take 1 $ iterate' undefined 42
*** Exception: Prelude.undefined

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

repeat x — это бесконечный список, где x — значение каждого элемента.

Примеры

>>> take 10 $ repeat 17
[17,17,17,17,17,17,17,17,17, 17]

>>> repeat undefined
[*** Exception: Prelude.undefined

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

replicate n x — это список длиной n со значением x каждого элемента. Это пример более общей функции genericReplicate, где n может быть любого целого типа.

Примеры

>>> replicate 0 True
[]

>>> replicate (-1) True
[]

>>> replicate 4 True
[True,True,True,True]

cycle :: HasCallStack => [a] -> [a] Источник

cycle связывает конечный список в циклический, или, равнозначно, бесконечное повторение исходного списка. Это тождество для бесконечных списков.

Примеры

>>> cycle []
*** Exception: Prelude.cycle: empty list

>>> take 10 (cycle [42])
[42,42,42,42,42,42,42,42,42,42]

>>> take 10 (cycle [2, 5, 7])
[2,5,7,2,5,7,2,5,7,2]

>>> take 1 (cycle (42 : undefined))
[42]

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] Источник

Функция unfoldr — `двойственная' foldr: в то время как foldr сводит список к суммарному значению, unfoldr строит список из начального значения. Функция берет элемент и возвращает Nothing если закончила построение списка, или возвращает Just (a,b), в этом случае a предписывается в список, и b используется как следующий элемент в рекурсивном вызове. Например,

iterate f == unfoldr (\x -> Just (x, f x))

В некоторых случаях unfoldr может отменить операцию foldr:

unfoldr f' (foldr f z xs) == xs

если выполняется следующее:

f' (f x y) = Just (x,y)
f' z       = Nothing

Лень

>>> take 1 (unfoldr (\x -> Just (x, undefined)) 'a')
"a"

Примеры

>>> unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
[10,9,8,7,6,5,4,3,2,1]

>>> take 10 $ unfoldr (\(x, y) -> Just (x, (y, x + y))) (0, 1)
[0,1,1,2,3,5,8,13,21,54]

take :: Int -> [a] -> [a] Source

take n, применённая к списку xs, возвращает префикс xs длины n, или сам список xs, если n >= length xs.

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

Ленивость

>>> take 0 undefined
[]
>>> take 2 (1 : 2 : undefined)
[1,2]

Примеры

>>> take 5 "Hello World!"
"Hello"

>>> take 3 [1,2,3,4,5]
[1,2,3]

>>> take 3 [1,2]
[1,2]

>>> take 3 []
[]

>>> take (-1) [1,2]
[]

>>> take 0 [1,2]
[]

drop :: Int -> [a] -> [a] Source

drop n xs возвращает суффикс xs после первых n элементов, или [] если n >= length xs.

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

Примеры

>>> drop 6 "Hello World!"
"World!"

>>> drop 3 [1,2,3,4,5]
[4,5]

>>> drop 3 [1,2]
[]

>>> drop 3 []
[]

>>> drop (-1) [1,2]
[1,2]

>>> drop 0 [1,2]
[1,2]

splitAt :: Int -> [a] -> ([a], [a]) Source

splitAt n xs возвращает кортеж, где первый элемент — xs префикс длины n, а второй — остаток списка:

splitAt — экземпляр более общей функции genericSplitAt, в которой n может быть любого целочисленного типа.

Ленивость

>>> fst (splitAt 0 undefined)
[]

>>> take 1 (fst (splitAt 10 (1 : undefined)))
[1]

Примеры

>>> splitAt 6 "Hello World!"
("Hello ","World!")

>>> splitAt 3 [1,2,3,4,5]
([1,2,3],[4,5])

>>> splitAt 1 [1,2,3]
([1],[2,3])

>>> splitAt 3 [1,2,3]
([1,2,3],[])

>>> splitAt 4 [1,2,3]
([1,2,3],[])

>>> splitAt 0 [1,2,3]
([],[1,2,3])

>>> splitAt (-1) [1,2,3]
([],[1,2,3])

takeWhile :: (a -> Bool) -> [a] -> [a] Source

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

Ленивость

>>> takeWhile (const False) undefined
*** Exception: Prelude.undefined

>>> takeWhile (const False) (undefined : undefined)
[]

>>> take 1 (takeWhile (const True) (1 : undefined))
[1]

Примеры

>>> takeWhile (< 3) [1,2,3,4,1,2,3,4]
[1,2]

>>> takeWhile (< 9) [1,2,3]
[1,2,3]

>>> takeWhile (< 0) [1,2,3]
[]

dropWhile :: (a -> Bool) -> [a] -> [a] Source

dropWhile p xs возвращает суффикс, оставшийся после takeWhile p xs.

Примеры

>>> dropWhile (< 3) [1,2,3,4,5,1,2,3]
[3,4,5,1,2,3]

>>> dropWhile (< 9) [1,2,3]
[]

>>> dropWhile (< 0) [1,2,3]
[1,2,3]

dropWhileEnd :: (a -> Bool) -> [a] -> [a] Source

Функция dropWhileEnd удаляет самый длинный суффикс списка, в котором заданный предикат выполняется для всех элементов.

Ленивость

>>> take 1 (dropWhileEnd (< 0) (1 : undefined))
[1]

>>> take 1 (reverse $ dropWhile (< 0) $ reverse (1 : undefined))
*** Exception: Prelude.undefined

>>> last (dropWhileEnd (< 0) [undefined, 1])
*** Exception: Prelude.undefined

>>> last (reverse $ dropWhile (< 0) $ reverse [undefined, 1])
1

Примеры

>>> dropWhileEnd isSpace "foo\n"
"foo"

>>> dropWhileEnd isSpace "foo bar"
"foo bar"
>>> dropWhileEnd (> 10) [1..20]
[1,2,3,4,5,6,7,8,9,10]

Since: base-4.5.0.0

span :: (a -> Bool) -> [a] -> ([a], [a]) Source

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

span p xs эквивалентна (takeWhile p xs, dropWhile p xs), даже если p — _|_.

Ленивость

>>> span undefined []
([],[])
>>> fst (span (const False) undefined)
*** Exception: Prelude.undefined
>>> fst (span (const False) (undefined : undefined))
[]
>>> take 1 (fst (span (const True) (1 : undefined)))
[1]

>>> take 10 (fst (span (const True) [1..]))
[1,2,3,4,5,6,7,8,9,10]

Примеры

>>> span (< 3) [1,2,3,4,1,2,3,4]
([1,2],[3,4,1,2,3,4])

>>> span (< 9) [1,2,3]
([1,2,3],[])

>>> span (< 0) [1,2,3]
([],[1,2,3])

break :: (a -> Bool) -> [a] -> ([a], [a]) Source

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

break p эквивалентна span (not . p) и, следовательно, (takeWhile (not . p) xs, dropWhile (not . p) xs), даже если p — _|_.

Ленивость

>>> break undefined []
([],[])

>>> fst (break (const True) undefined)
*** Exception: Prelude.undefined

>>> fst (break (const True) (undefined : undefined))
[]

>>> take 1 (fst (break (const False) (1 : undefined)))
[1]

>>> take 10 (fst (break (const False) [1..]))
[1,2,3,4,5,6,7,8,9,10]

Примеры

>>> break (> 3) [1,2,3,4,1,2,3,4]
([1,2,3],[4,1,2,3,4])

>>> break (< 9) [1,2,3]
([],[1,2,3])

>>> break (> 9) [1,2,3]
([1,2,3],[])

stripPrefix :: Eq a => [a] -> [a] -> Maybe [a] Source

\(\mathcal{O}(\min(m,n))\). Функция stripPrefix удаляет указанный префикс из списка. Она возвращает Nothing если список не начинался с данного префикса, или Just список после префикса, если начинался.

Примеры

>>> stripPrefix "foo" "foobar"
Just "bar"

>>> stripPrefix "foo" "foo"
Just ""

>>> stripPrefix "foo" "barfoo"
Nothing

>>> stripPrefix "foo" "barfoobaz"
Nothing

group :: Eq a => [a] -> [[a]] Source

Функция group берёт список и возвращает список списков, такой, что конкатенация результата равна аргументу. Более того, каждый подсписок в результате непустой, все элементы равны первому, и все последовательные одинаковые элементы входного списка оказываются в одном элементе выходного списка.

group — частный случай groupBy, который позволяет программисту задать собственную функцию равенства.

Часто предпочтительнее использовать Data.List.NonEmpty.group, которое обеспечивает гарантии на уровне типов, что внутренние списки не пусты. Общий приём для сжатия повторяющихся элементов map head . group лучше реализуется с помощью map Data.List.NonEmpty.head . Data.List.NonEmpty.group, поскольку это позволяет избежать частичных функций.

Примеры

>>> group "Mississippi"
["M","i","ss","i","ss","i","pp","i"]

>>> group [1, 1, 1, 2, 2, 3, 4, 5, 5]
[[1,1,1],[2,2],[3],[4],[5,5]]

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

Функция inits возвращает все начальные сегменты аргумента, начиная с самого короткого.

inits семантически эквивалентна map reverse . scanl (flip (:)) [], но под капотом использует очередь для амортизации затрат на reverse.

Ленивость

Примеры

>>> inits "abc"
["","a","ab","abc"]

>>> inits []
[[]]

>>> take 5 $ inits [1..]
[[],[1],[1,2],[1,2,3],[1,2,3,4]]

inits1 :: [a] -> [NonEmpty a] Источник

Функция inits1 возвращает все непустые начальные сегменты аргумента, начиная с самого короткого.

Ленивость

Примеры

>>> inits1 "abc"
['a' :| "",'a' :| "b",'a' :| "bc"]

>>> inits1 []
[]

>>> take 3 $ inits1 [1..]
[1 :| [],1 :| [2],1 :| [2,3]]

С версии: base-4.21.0.0

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

\(\mathcal{O}(n)\). Функция tails возвращает все конечные сегменты аргумента, начиная с самого длинного.

Ленивость

>>> tails undefined
[*** Exception: Prelude.undefined

>>> drop 1 (tails [undefined, 1, 2])
[[1, 2], [2], []]

Примеры

>>> tails "abc"
["abc","bc","c",""]

>>> tails [1, 2, 3]
[[1,2,3],[2,3],[3],[]]

>>> tails []
[[]]

tails1 :: [a] -> [NonEmpty a] Источник

\(\mathcal{O}(n)\). Функция tails1 возвращает все непустые конечные сегменты аргумента, начиная с самого длинного.

Ленивость

>>> tails1 undefined
*** Exception: Prelude.undefined

>>> drop 1 (tails1 [undefined, 1, 2])
[1 :| [2],2 :| []]

Примеры

>>> tails1 "abc"
['a' :| "bc",'b' :| "c",'c' :| ""]

>>> tails1 [1, 2, 3]
[1 :| [2,3],2 :| [3],3 :| []]

>>> tails1 []
[]

С версии: base-4.21.0.0

isPrefixOf :: Eq a => [a] -> [a] -> Bool Источник

\(\mathcal{O}(\min(m,n))\). Функция isPrefixOf принимает два списка и возвращает True, если первый список является префиксом второго.

Примеры

>>> "Hello" `isPrefixOf` "Hello World!"
True

>>> "Hello" `isPrefixOf` "Wello Horld!"
False

>>> [0..] `isPrefixOf` [1..]
False

>>> [0..] `isPrefixOf` [0..99]
False

>>> [0..99] `isPrefixOf` [0..]
True

>>> [0..] `isPrefixOf` [0..]
* Hangs forever *

>>> isPrefixOf [] undefined
True

isSuffixOf :: Eq a => [a] -> [a] -> Bool Источник

Функция isSuffixOf принимает два списка и возвращает True, если первый список является суффиксом второго.

Примеры

>>> "ld!" `isSuffixOf` "Hello World!"
True

>>> "World" `isSuffixOf` "Hello World!"
False

>>> [0..] `isSuffixOf` [0..99]
False

>>> [0..99] `isSuffixOf` [0..]
* Hangs forever *

isInfixOf :: Eq a => [a] -> [a] -> Bool Источник

Функция isInfixOf принимает два списка и возвращает True, если первый список содержится целиком и полностью где-либо внутри второго.

Примеры

>>> isInfixOf "Haskell" "I really like Haskell."
True

>>> isInfixOf "Ial" "I really like Haskell."
False

>>> [20..50] `isInfixOf` [0..]
True

>>> [0..] `isInfixOf` [20..50]
False

>>> [0..] `isInfixOf` [0..]
* Hangs forever *

isSubsequenceOf :: Eq a => [a] -> [a] -> Bool Источник

Функция isSubsequenceOf принимает два списка и возвращает True, если все элементы первого списка встречаются, в порядке следования, во втором. Элементы не обязательно должны встречаться последовательно.

isSubsequenceOf x y эквивалентна x `elem` (subsequences y).

Примечание: isSubsequenceOf часто используется в инфиксной форме.

Примеры

>>> "GHC" `isSubsequenceOf` "The Glorious Haskell Compiler"
True

>>> ['a','d'..'z'] `isSubsequenceOf` ['a'..'z']
True

>>> [1..10] `isSubsequenceOf` [10,9..0]
False

>>> [0,2..10] `isSubsequenceOf` [0..]
True

>>> [0..] `isSubsequenceOf` [0,2..10]
False

>>> [0,2..] `isSubsequenceOf` [0..]
* Hangs forever*

С версии: base-4.8.0.0

elem :: (Foldable t, Eq a) => a -> t a -> Bool infix 4 Источник

Встречается ли элемент в структуре?

Примечание: elem часто используется в инфиксной форме.

Примеры

>>> 3 `elem` []
False

>>> 3 `elem` [1,2]
False

>>> 3 `elem` [1,2,3,4,5]
True

>>> 3 `elem` [1..]
True

>>> 3 `elem` ([4..] ++ [3])
* Hangs forever *

С версии: base-4.8.0.0

notElem :: (Foldable t, Eq a) => a -> t a -> Bool infix 4 Источник

notElem — это отрицание elem.

Примеры

>>> 3 `notElem` []
True

>>> 3 `notElem` [1,2]
True

>>> 3 `notElem` [1,2,3,4,5]
False

>>> 3 `notElem` [1..]
False

>>> 3 `notElem` ([4..] ++ [3])
* Hangs forever *

lookup :: Eq a => a -> [(a, b)] -> Maybe b Источник

\(\mathcal{O}(n)\). lookup key assocs ищет ключ в списке ассоциаций. Для того, чтобы результат был Nothing, список должен быть конечным.

Примеры

>>> lookup 2 []
Nothing

>>> lookup 2 [(1, "first")]
Nothing

>>> lookup 2 [(1, "first"), (2, "second"), (3, "third")]
Just "second"

find :: Foldable t => (a -> Bool) -> t a -> Maybe a Источник

Функция find принимает предикат и структуру и возвращает самый левый элемент структуры, удовлетворяющий предикату, или Nothing , если такого элемента нет.

Примеры

>>> find (> 42) [0, 5..]
Just 45

>>> find (> 12) [1..7]
Nothing

filter :: (a -> Bool) -> [a] -> [a] Источник

\(\mathcal{O}(n)\). filter, применённая к предикату и списку, возвращает список тех элементов, которые удовлетворяют предикату; т.е.,

filter p xs = [ x | x <- xs, p x]

Примеры

>>> filter odd [1, 2, 3]
[1,3]

>>> filter (\l -> length l > 3) ["Hello", ", ", "World", "!"]
["Hello","World"]

>>> filter (/= 3) [1, 2, 3, 4, 3, 2, 1]
[1,2,4,2,1]

partition :: (a -> Bool) -> [a] -> ([a], [a]) Источник

Функция partition принимает предикат и список, и возвращает пару списков элементов, которые удовлетворяют и не удовлетворяют предикату, соответственно; т.е.,

partition p xs == (filter p xs, filter (not . p) xs)

Примеры

>>> partition (`elem` "aeiou") "Hello World!"
("eoo","Hll Wrld!")

>>> partition even [1..10]
([2,4,6,8,10],[1,3,5,7,9])

>>> partition (< 5) [1..10]
([1,2,3,4],[5,6,7,8,9,10])

Эти функции рассматривают список xs как индексированную коллекцию, с индексами, изменяющимися от 0 до length xs - 1.

(!?) :: [a] -> Int -> Maybe a infixl 9 Источник

Оператор индекса списка (индекс), начиная с 0. Возвращает Nothing , если индекс вне границ

Это полная версия частичного оператора !!.

ПРЕДУПРЕЖДЕНИЕ: Эта функция работает за линейное время относительно индекса.

Примеры

>>> ['a', 'b', 'c'] !? 0
Just 'a'

>>> ['a', 'b', 'c'] !? 2
Just 'c'

>>> ['a', 'b', 'c'] !? 3
Nothing

>>> ['a', 'b', 'c'] !? (-1)
Nothing

(!!) :: HasCallStack => [a] -> Int -> a infixl 9 Источник

Оператор индекса списка (индекс), начиная с 0. Это пример более общей функции genericIndex, которая принимает индекс любого целочисленного типа.

ПРЕДУПРЕЖДЕНИЕ: Эта функция частична и должна использоваться только если вы уверены, что индексирование не завершится ошибкой. В противном случае используйте !?.

ПРЕДУПРЕЖДЕНИЕ: Эта функция работает за линейное время относительно индекса.

Примеры

>>> ['a', 'b', 'c'] !! 0
'a'

>>> ['a', 'b', 'c'] !! 2
'c'

>>> ['a', 'b', 'c'] !! 3
*** Exception: Prelude.!!: index too large

>>> ['a', 'b', 'c'] !! (-1)
*** Exception: Prelude.!!: negative index

elemIndex :: Eq a => a -> [a] -> Maybe Int Источник

Функция elemIndex возвращает индекс первого элемента в данном списке, который равен (по ==) запрошенному элементу, или Nothing , если такого элемента нет. Для того, чтобы результат был Nothing, список должен быть конечным.

Примеры

>>> elemIndex 4 [0..]
Just 4

>>> elemIndex 'o' "haskell"
Nothing

>>> elemIndex 0 [1..]
* hangs forever *

elemIndices :: Eq a => a -> [a] -> [Int] Источник

Функция elemIndices расширяет elemIndex, возвращая индексы всех элементов, равных запрошенному элементу, в порядке возрастания.

Примеры

>>> elemIndices 'o' "Hello World"
[4,7]

>>> elemIndices 1 [1, 2, 3, 1, 2, 3]
[0,3]

findIndex :: (a -> Bool) -> [a] -> Maybe Int Источник

Функция findIndex принимает предикат и список, и возвращает индекс первого элемента в списке, удовлетворяющего предикату, или Nothing , если такого элемента нет. Для того, чтобы результат был Nothing, список должен быть конечным.

Примеры

>>> findIndex isSpace "Hello World!"
Just 5

>>> findIndex odd [0, 2, 4, 6]
Nothing

>>> findIndex even [1..]
Just 1

>>> findIndex odd [0, 2 ..]
* hangs forever *

findIndices :: (a -> Bool) -> [a] -> [Int] Источник

Функция findIndices расширяет findIndex, возвращая индексы всех элементов, удовлетворяющих предикату, в порядке возрастания.

Примеры

>>> findIndices (`elem` "aeiou") "Hello World!"
[1,4,7]

>>> findIndices (\l -> length l > 3) ["a", "bcde", "fgh", "ijklmnop"]
[1,3]

zip :: [a] -> [b] -> [(a, b)] Источник

\(\mathcal{O}(\min(m,n))\). zip принимает два списка и возвращает список соответствующих пар.

zip является правым ленивым:

>>> zip [] undefined
[]
>>> zip undefined []
*** Exception: Prelude.undefined
...

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

Примеры

>>> zip [1, 2, 3] ['a', 'b', 'c']
[(1,'a'),(2,'b'),(3,'c')]

>>> zip [1] ['a', 'b']
[(1,'a')]

>>> zip [1, 2] ['a']
[(1,'a')]

>>> zip [] [1..]
[]

>>> zip [1..] []
[]

zip3 :: [a] -> [b] -> [c] -> [(a, b, c)] Источник

zip3 принимает три списка и возвращает список троек, аналогично zip. Она способна к слиянию списков, но ограничена своим первым аргументом списка и результирующим списком.

zip4 :: [a] -> [b] -> [c] -> [d] -> [(a, b, c, d)] Источник

Функция zip4 принимает четыре списка и возвращает список четверок, аналогично zip. Она способна к слиянию списков, но ограничена своим первым аргументом списка и результирующим списком.

zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a, b, c, d, e)] Source

Функция zip5 принимает пять списков и возвращает список пятеричных кортежей, аналогично zip. Она поддерживает слияние списков, но ограничена первым списком-аргументом и результатом.

zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [(a, b, c, d, e, f)] Source

Функция zip6 принимает шесть списков и возвращает список шестикортежей, аналогично zip. Она поддерживает слияние списков, но ограничена первым списком-аргументом и результатом.

zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [(a, b, c, d, e, f, g)] Source

Функция zip7 принимает семь списков и возвращает список семикортежей, аналогично zip. Она поддерживает слияние списков, но ограничена первым списком-аргументом и результатом.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] Source

\(\mathcal{O}(\min(m,n))\). Функция zipWith обобщает zip путём применения функции, заданной в качестве первого аргумента, вместо функции построения кортежа.

zipWith (,) xs ys == zip xs ys
zipWith f [x1,x2,x3..] [y1,y2,y3..] == [f x1 y1, f x2 y2, f x3 y3..]

zipWith является право-ленивой:

>>> let f = undefined
>>> zipWith f [] undefined
[]

zipWith поддерживает слияние списков, но ограничена первым списком-аргументом и результатом.

Примеры

>>> zipWith (+) [1, 2, 3] [4, 5, 6]
[5,7,9]

>>> zipWith (++) ["hello ", "foo"] ["world!", "bar"]
["hello world!","foobar"]

zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d] Source

\(\mathcal{O}(\min(l,m,n))\). Функция zipWith3 принимает функцию, которая комбинирует три элемента, а также три списка и возвращает список применённой функции к соответствующим элементам, аналогично zipWith. Она поддерживает слияние списков, но ограничена первым списком-аргументом и результатом.

zipWith3 (,,) xs ys zs == zip3 xs ys zs
zipWith3 f [x1,x2,x3..] [y1,y2,y3..] [z1,z2,z3..] == [f x1 y1 z1, f x2 y2 z2, f x3 y3 z3..]

Примеры

>>> zipWith3 (\x y z -> [x, y, z]) "123" "abc" "xyz"
["1ax","2by","3cz"]

>>> zipWith3 (\x y z -> (x * y) + z) [1, 2, 3] [4, 5, 6] [7, 8, 9]
[11,18,27]

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

Функция zipWith4 принимает функцию, которая комбинирует четыре элемента, а также четыре списка и возвращает список их точечной комбинации, аналогично zipWith. Она поддерживает слияние списков, но ограничена первым списком-аргументом и результатом.

zipWith5 :: (a -> b -> c -> d -> e -> f) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] Source

Функция zipWith5 принимает функцию, которая комбинирует пять элементов, а также пять списков и возвращает список их точечной комбинации, аналогично zipWith. Она поддерживает слияние списков, но ограничена первым списком-аргументом и результатом.

zipWith6 :: (a -> b -> c -> d -> e -> f -> g) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] Source

Функция zipWith6 принимает функцию, которая комбинирует шесть элементов, а также шесть списков и возвращает список их точечной комбинации, аналогично zipWith. Она поддерживает слияние списков, но ограничена первым списком-аргументом и результатом.

zipWith7 :: (a -> b -> c -> d -> e -> f -> g -> h) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [h] Source

Функция zipWith7 принимает функцию, которая комбинирует семь элементов, а также семь списков и возвращает список их точечной комбинации, аналогично zipWith. Она поддерживает слияние списков, но ограничена первым списком-аргументом и результатом.

unzip :: [(a, b)] -> ([a], [b]) Source

unzip преобразует список пар в список первых компонентов и список вторых компонентов.

Примеры

>>> unzip []
([],[])

>>> unzip [(1, 'a'), (2, 'b')]
([1,2],"ab")

unzip3 :: [(a, b, c)] -> ([a], [b], [c]) Source

Функция unzip3 принимает список троек и возвращает три списка соответствующих компонентов, аналогично unzip.

Примеры

>>> unzip3 []
([],[],[])

>>> unzip3 [(1, 'a', True), (2, 'b', False)]
([1,2],"ab",[True,False])

unzip4 :: [(a, b, c, d)] -> ([a], [b], [c], [d]) Source

Функция unzip4 принимает список четверок и возвращает четыре списка, аналогично unzip.

unzip5 :: [(a, b, c, d, e)] -> ([a], [b], [c], [d], [e]) Source

Функция unzip5 принимает список пятеричных кортежей и возвращает пять списков, аналогично unzip.

unzip6 :: [(a, b, c, d, e, f)] -> ([a], [b], [c], [d], [e], [f]) Source

Функция unzip6 принимает список шестикортежей и возвращает шесть списков, аналогично unzip.

unzip7 :: [(a, b, c, d, e, f, g)] -> ([a], [b], [c], [d], [e], [f], [g]) Source

Функция unzip7 принимает список семикортежей и возвращает семь списков, аналогично unzip.

lines :: String -> [String] Source

Разбивает аргумент на список строк, очищая их от завершающих \n символов. Символ \n является необязательным в последней непустой строке аргумента-строки.

Если аргумент-строка пустая или заканчивается символом \n, она может быть восстановлена, передав результат lines в функцию unlines . В противном случае, unlines добавляет недостающий завершающий символ \n. Это делает unlines . lines идемпотентной:

(unlines . lines) . (unlines . lines) = (unlines . lines)

Примеры

>>> lines ""           -- empty input contains no lines
[]

>>> lines "\n"         -- single empty line
[""]

>>> lines "one"        -- single unterminated line
["one"]

>>> lines "one\n"      -- single non-empty line
["one"]

>>> lines "one\n\n"    -- second line is empty
["one",""]

>>> lines "one\ntwo"   -- second line is unterminated
["one","two"]

>>> lines "one\ntwo\n" -- two non-empty lines
["one","two"]

words :: String -> [String] Source

Функция words разбивает строку на список слов, разделяемых пробелами (как определено isSpace). Функция обрезает все пробелы в начале и в конце.

Примеры

>>> words "Lorem ipsum\ndolor"
["Lorem","ipsum","dolor"]

>>> words " foo bar "
["foo","bar"]

unlines :: [String] -> String Source

Присоединяет символ \n к каждой строке входных данных, а затем конкатенирует результаты. Эквивалентно foldMap (s -> s ++ "\n").

Примеры

>>> unlines ["Hello", "World", "!"]
"Hello\nWorld\n!\n"

>>> unlines . lines $ "foo\nbar"
"foo\nbar\n"

unwords :: [Строка] -> Строка Исходный код

unwords объединяет слова, используя разделители (пробелы U+0020 SPACE).

unwords не является левым или правым обратным элементом для words:

>>> words (unwords [" "])
[]
>>> unwords (words "foo\nbar")
"foo bar"

Примеры

>>> unwords ["Lorem", "ipsum", "dolor"]
"Lorem ipsum dolor"

>>> unwords ["foo", "bar", "", "baz"]
"foo bar  baz"

nub :: Eq a => [a] -> [a] Исходный код

\(\mathcal{O}(n^2)\). Функция nub удаляет дублирующие элементы из списка. В частности, она сохраняет только первое вхождение каждого элемента. (Имя nub означает `сущность'.) Это частный случай функции nubBy, которая позволяет программисту задать собственное сравнение на равенство.

Если существует instance Ord a, то быстрее использовать nubOrd из пакета containers (ссылка на последнюю онлайн-документацию), что занимает только \(\mathcal{O}(n \log d)\) времени, где d — количество уникальных элементов в списке.

Другой подход для ускорения nub — использование map Data.List.NonEmpty.head . Data.List.NonEmpty.group . sort, что занимает \(\mathcal{O}(n \log n)\) времени, требует instance Ord a и не сохраняет порядок.

Примеры

>>> nub [1,2,3,4,3,2,1,2,4,3,5]
[1,2,3,4,5]

>>> nub "hello, world!"
"helo, wrd!"

delete :: Eq a => a -> [a] -> [a] Исходный код

\(\mathcal{O}(n)\). delete x удаляет первое вхождение x из своего аргумента-списка.

Это частный случай deleteBy, который позволяет программисту задать собственное сравнение на равенство.

Примеры

>>> delete 'a' "banana"
"bnana"

>>> delete "not" ["haskell", "is", "not", "awesome"]
["haskell","is","awesome"]

(\\) :: Eq a => [a] -> [a] -> [a] infix 5 Исходный код

Функция \\ — это разность списков (неассоциативная). В результате xs \\ ys, первое вхождение каждого элемента из ys в свою очередь (если есть) было удалено из xs. Таким образом, (xs ++ ys) \\ xs == ys.

Это частный случай deleteFirstsBy, который позволяет программисту задать собственное сравнение на равенство.

Примеры

>>> "Hello World!" \\ "ell W"
"Hoorld!"

>>> take 5 ([0..] \\ [2..4])
[0,1,5,6,7]

>>> take 5 ([0..] \\ [2..])
* Hangs forever *

union :: Eq a => [a] -> [a] -> [a] Исходный код

Функция union возвращает объединение двух списков. Это частный случай unionBy, который позволяет программисту задать собственное сравнение на равенство.

Примеры

>>> "dog" `union` "cow"
"dogcw"

>>> import Data.Semigroup(Arg(..))
>>> union [Arg () "dog"] [Arg () "cow"]
[Arg () "dog"]
>>> union [] [Arg () "dog", Arg () "cow"]
[Arg () "dog"]

>>> "coot" `union` "duck"
"cootduk"
>>> "duck" `union` "coot"
"duckot"

>>> [0, 2 ..] `union` [1, 3 ..]
[0,2,4,6,8,10,12..

intersect :: Eq a => [a] -> [a] -> [a] Исходный код

Функция intersect выполняет пересечение двух списков. Это частный случай intersectBy, который позволяет программисту задать собственное сравнение на равенство.

Примеры

>>> [1,2,3,4] `intersect` [2,4,6,8]
[2,4]

>>> import Data.Semigroup
>>> intersect [Arg () "dog"] [Arg () "cow", Arg () "cat"]
[Arg () "dog"]

>>> "coot" `intersect` "heron"
"oo"
>>> "heron" `intersect` "coot"
"o"

>>> intersect [100..] [0..]
[100,101,102,103...
>>> intersect [0] [1..]
* Hangs forever *
>>> intersect [1..] [0]
* Hangs forever *
>>> intersect (cycle [1..3]) [2]
[2,2,2,2...

sort :: Ord a => [a] -> [a] Исходный код

Функция sort реализует устойчивый алгоритм сортировки. Это частный случай sortBy, который позволяет программисту задать собственную функцию сравнения.

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

Аргумент должен быть конечным.

Примеры

>>> sort [1,6,4,3,2,5]
[1,2,3,4,5,6]

>>> sort "haskell"
"aehklls"

>>> import Data.Semigroup(Arg(..))
>>> sort [Arg ":)" 0, Arg ":D" 0, Arg ":)" 1, Arg ":3" 0, Arg ":D" 1]
[Arg ":)" 0,Arg ":)" 1,Arg ":3" 0,Arg ":D" 0,Arg ":D" 1]

sortOn :: Ord b => (a -> b) -> [a] -> [a] Исходный код

Сортировка списка по результатам применения функции ключа к каждому элементу. sortOn f эквивалентно sortBy (comparing f), но имеет преимущество в производительности, оценивая f только один раз для каждого элемента во входном списке. Это называется парадигмой декорирования-сортировки-рассортировки или трансформацией Шварца.

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

Аргумент должен быть конечным.

Примеры

>>> sortOn fst [(2, "world"), (4, "!"), (1, "Hello")]
[(1,"Hello"),(2,"world"),(4,"!")]

>>> sortOn length ["jim", "creed", "pam", "michael", "dwight", "kevin"]
["jim","pam","creed","kevin","dwight","michael"]

Примечания по производительности

>>> sortBy (comparing fst) [(3, 1), (2, 2), (1, 3)]
[(1,3),(2,2),(3,1)]

>>> (sortBy . comparing) fst [(3, 1), (2, 2), (1, 3)]
[(1,3),(2,2),(3,1)]

С момента: base-4.8.0.0

insert :: Ord a => a -> [a] -> [a] Исходный код

\(\mathcal{O}(n)\). Функция insert принимает элемент и список и вставляет элемент в список в первой позиции, где он меньше или равен следующему элементу. В частности, если список отсортирован до вызова, результат также будет отсортирован. Это частный случай insertBy, который позволяет программисту задать собственную функцию сравнения.

Примеры

>>> insert (-1) [1, 2, 3]
[-1,1,2,3]

>>> insert 'd' "abcefg"
"abcdefg"

>>> insert 4 [1, 2, 3, 5, 6, 7]
[1,2,3,4,5,6,7]

По соглашению, перегруженные функции имеют неперегруженный аналог, имя которого имеет суффикс `By'.

Часто удобно использовать эти функции вместе с on, например, sortBy (compare `on` fst).

Предполагается, что предикат определяет отношение эквивалентности.

nubBy :: (a -> a -> Bool) -> [a] -> [a] Source

Функция nubBy ведет себя точно так же, как nub, за исключением того, что она использует предоставленный пользователем предикат равенства вместо перегруженной функции (==).

Примеры

>>> nubBy (\x y -> mod x 3 == mod y 3) [1,2,4,5,6]
[1,2,6]

>>> nubBy (/=) [2, 7, 1, 8, 2, 8, 1, 8, 2, 8]
[2,2,2]

>>> nubBy (>) [1, 2, 3, 2, 1, 5, 4, 5, 3, 2]
[1,2,3,5,5]

deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a] Source

\(\mathcal{O}(n)\). Функция deleteBy ведет себя как delete, но принимает предоставленный пользователем предикат равенства.

Примеры

>>> deleteBy (<=) 4 [1..10]
[1,2,3,5,6,7,8,9,10]

>>> deleteBy (/=) 5 [5, 5, 4, 3, 5, 2]
[5,5,3,5,2]

deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] Source

Функция deleteFirstsBy принимает предикат и два списка и возвращает первый список с удаленным первым вхождением каждого элемента из второго списка. Это неперегруженная версия (\\).

(\\) == deleteFirstsBy (==)

Второй список должен быть конечным, но первый может быть бесконечным.

Примеры

>>> deleteFirstsBy (>) [1..10] [3, 4, 5]
[4,5,6,7,8,9,10]

>>> deleteFirstsBy (/=) [1..10] [1, 3, 5]
[4,5,6,7,8,9,10]

unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] Source

Функция unionBy — это неперегруженная версия union. Оба аргумента могут быть бесконечными.

Примеры

>>> unionBy (>) [3, 4, 5] [1, 2, 3, 4, 5, 6]
[3,4,5,4,5,6]

>>> import Data.Semigroup (Arg(..))
>>> unionBy (/=) [Arg () "Saul"] [Arg () "Kim"]
[Arg () "Saul", Arg () "Kim"]

intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] Source

Функция intersectBy — это неперегруженная версия intersect. Она продуктивна для бесконечных аргументов только в том случае, если первый является подмножеством второго.

groupBy :: (a -> a -> Bool) -> [a] -> [[a]] Source

Функция groupBy — это неперегруженная версия group.

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

>>> groupBy (\a b -> b - a < 5) [0..19]
[[0,1,2,3,4],[5,6,7,8,9],[10,11,12,13,14],[15,16,17,18,19]]

Часто предпочтительнее использовать Data.List.NonEmpty.groupBy, которая предоставляет гарантии на уровне типов, что внутренние списки непусты.

Примеры

>>> groupBy (/=) [1, 1, 1, 2, 3, 1, 4, 4, 5]
[[1],[1],[1,2,3],[1,4,4,5]]

>>> groupBy (>) [1, 3, 5, 1, 4, 2, 6, 5, 4]
[[1],[3],[5,1,4,2],[6,5,4]]

>>> groupBy (const not) [True, False, True, False, False, False, True]
[[True,False],[True,False,False,False],[True]]

Предполагается, что функция определяет полное упорядочение.

sortBy :: (a -> a -> Ordering) -> [a] -> [a] Source

Функция sortBy — это неперегруженная версия sort. Аргумент должен быть конечным.

Предполагается, что предоставленное отношение сравнения является рефлексивным и антисимметричным, в противном случае, например, для _ _ -> GT, упорядоченный список просто не существует. Также ожидается, что отношение является транзитивным: если это не так, sortBy может не найти упорядоченную перестановку, даже если она существует.

Примеры

>>> sortBy (\(a,_) (b,_) -> compare a b) [(2, "world"), (4, "!"), (1, "Hello")]
[(1,"Hello"),(2,"world"),(4,"!")]

insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a] Source

\(\mathcal{O}(n)\). Неперегруженная версия insert.

Примеры

>>> insertBy (\x y -> compare (length x) (length y)) [1, 2] [[1], [1, 2, 3], [1, 2, 3, 4]]
[[1],[1,2],[1,2,3],[1,2,3,4]]

maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a Source

Наибольший элемент непустого объекта относительно заданной функции сравнения. Порядок объекта используется для выбора в случае нескольких наибольших элементов; выбирается самый правый из них.

Примеры

>>> maximumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
"Longest"

minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a Source

Наименьший элемент непустого объекта относительно заданной функции сравнения. Порядок объекта используется для выбора в случае нескольких наименьших элементов; выбирается самый левый из них.

Примеры

>>> minimumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
"!"

Префикс `generic' указывает на перегруженную функцию, которая является обобщенной версией функции из Prelude.

genericLength :: Num i => [a] -> i Source

\(\mathcal{O}(n)\). Функция genericLength — перегруженная версия length. В частности, вместо возвращения Int, она возвращает любой тип, который является экземпляром Num. Однако она менее эффективна, чем length.

Примеры

>>> genericLength [1, 2, 3] :: Int
3
>>> genericLength [1, 2, 3] :: Float
3.0

>>> genericLength [1..200] :: Int8
-56

genericTake :: Integral i => i -> [a] -> [a] Source

Функция genericTake — перегруженная версия take, которая принимает любое целое число Integral в качестве количества элементов для взятия.

genericDrop :: Integral i => i -> [a] -> [a] Source

Функция genericDrop — перегруженная версия drop, которая принимает любое целое число Integral в качестве количества элементов для удаления.

genericSplitAt :: Integral i => i -> [a] -> ([a], [a]) Source

Функция genericSplitAt — перегруженная версия splitAt, которая принимает любое целое число Integral в качестве позиции разделения.

genericIndex :: Integral i => [a] -> i -> a Source

Функция genericIndex является перегруженной версией !!, которая принимает любое значение Integral в качестве индекса.

genericReplicate :: Integral i => i -> a -> [a] Source

Функция genericReplicate является перегруженной версией replicate, которая принимает любое значение Integral в качестве количества повторений.