GHC.List

data List 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-internal-0.10.0

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

foldr, применённая к бинарному оператору, начальному значению (обычно правой нейтральной по этому оператору) и списку, свёртывает список с помощью бинарного оператора справа налево:

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

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

foldr' — это вариант foldr, который начинает свёртку списка с последнего элемента и строго вычисляет аккумулятор при раскрутке стека обратно к началу списка. Входной список должен быть конечным, иначе foldr' исчерпает память (зациклится).

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

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

Использование этой функции указывает на то, что структура [] может плохо подходить для данной задачи. Если порядок объединения элементов не имеет значения, используйте вместо неё foldl'.

>>> foldr' (+) [1..4]  -- Use foldl' instead!
10
>>> foldr' (&&) [True, False, True, True] -- Use foldr instead!
False
>>> foldr' (||) [False, False, True, True] -- Use foldr instead!
True

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

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

>>> foldr1 (+) [1..4]
10
>>> foldr1 (+) []
*** Exception: Prelude.foldr1: empty list
>>> foldr1 (-) [1..4]
-2
>>> foldr1 (&&) [True, False, True, True]
False
>>> foldr1 (||) [False, False, True, True]
True
>>> force $ foldr1 (+) [1..]
*** Exception: stack overflow

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

foldl, применённая к бинарному оператору, начальному значению (обычно левой нейтральной по этому оператору) и списку, свёртывает список с помощью бинарного оператора слева направо:

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

Список должен быть конечным.

>>> foldl (+) 0 [1..4]
10
>>> foldl (+) 42 []
42
>>> foldl (-) 100 [1..4]
90
>>> foldl (\reversedString nextChar -> nextChar : reversedString) "foo" ['a', 'b', 'c', 'd']
"dcbafoo"
>>> foldl (+) 0 [1..]
* Hangs forever *

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

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

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

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

>>> foldl1 (+) [1..4]
10
>>> foldl1 (+) []
*** Exception: Prelude.foldl1: empty list
>>> foldl1 (-) [1..4]
-8
>>> foldl1 (&&) [True, False, True, True]
False
>>> foldl1 (||) [False, False, True, True]
True
>>> foldl1 (+) [1..]
* Hangs forever *

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

\(\mathcal{O}(1)\). Проверяет, пуст ли список.

>>> null []
True
>>> null [1]
False
>>> null [1..]
False

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

\(\mathcal{O}(n)\). length возвращает длину конечного списка в виде Int. Это частный случай более общего genericLength, тип результата которого может быть любым числовым типом.

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

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

elem — предикат проверки наличия элемента в списке, обычно записываемый в инфиксной форме, например x `elem` xs. Чтобы результат был False, список должен быть конечным; однако True получается, если элемент, равный x, найден по конечному индексу в конечном или бесконечном списке.

Примеры

>>> 3 `elem` []
False

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

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

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

>>> 3 `elem` [4..]
* Hangs forever *

notElem :: Eq a => a -> [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..]
* Hangs forever *

maximum :: (Ord a, HasCallStack) => [a] -> a Источник

maximum возвращает наибольшее значение из списка, который должен быть непустым и конечным, а его элементы должны принадлежать упорядоченному типу. Эта функция эквивалентна foldr1 max, а её поведение для списков с несколькими максимальными значениями зависит от соответствующей реализации max. В реализации max по умолчанию порядок элементов списка используется для разрешения равенства: если максимальных значений несколько, выбирается самое правое (это эквивалентно maximumBy compare).

>>> maximum []
*** Exception: Prelude.maximum: empty list
>>> maximum [42]
42
>>> maximum [55, -12, 7, 0, -89]
55
>>> maximum [1..]
* Hangs forever *

minimum :: (Ord a, HasCallStack) => [a] -> a Источник

minimum возвращает наименьшее значение из списка, который должен быть непустым и конечным, а его элементы должны принадлежать упорядоченному типу. Эта функция эквивалентна foldr1 min, а её поведение для списков с несколькими минимальными значениями зависит от соответствующей реализации min. В реализации min по умолчанию порядок элементов списка используется для разрешения равенства: если минимальных значений несколько, выбирается самое левое (это эквивалентно minimumBy compare).

>>> minimum []
*** Exception: Prelude.minimum: empty list
>>> minimum [42]
42
>>> minimum [55, -12, 7, 0, -89]
-89
>>> minimum [1..]
* Hangs forever *

sum :: Num a => [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 *

product :: Num a => [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 *

and :: [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,True,True,True...
False

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

or :: [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,False,False,False...
True

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

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

Для заданных предиката и списка функция any определяет, удовлетворяет ли предикату хотя бы один элемент списка. Чтобы результат был False, список должен быть конечным; однако True получается, если предикат возвращает значение True для элемента с конечным индексом в конечном или бесконечном списке.

Примеры

>>> 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 :: (a -> Bool) -> [a] -> Bool Источник

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

Примеры

>>> 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 *

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

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

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

Объединяет список списков.

Примеры

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

>>> concat []
[]

>>> concat [[42]]
[42]

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

Применяет к списку функцию, возвращающую список, и объединяет результаты. concatMap можно рассматривать как композицию concat и map.

concatMap f xs == (concat . map f) xs

Примеры

>>> concatMap (\i -> [-i,i]) []
[]

>>> concatMap (\i -> [-i, i]) [1, 2, 3]
[-1,1,-2,2,-3,3]

>>> concatMap (replicate 3) [0, 2, 4]
[0,0,0,2,2,2,4,4,4]

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]

(++) :: [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]

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]

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"

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

(!?) :: [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

Начиная с: base-4.19.0.0

(!!) :: 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

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"

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"

scanl' :: (b -> a -> b) -> b -> [a] -> [b] Исходный код

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

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

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]

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

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] Исходный код

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]) Исходный код

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] Исходный код

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] Исходный код

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]

span :: (a -> Bool) -> [a] -> ([a], [a]) Исходный код

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]) Исходный код

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],[])

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 *

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. Поддерживает слияние списков, но эта возможность ограничена первым аргументом-списком и результирующим списком.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] Исходный код

\(\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] Исходный код

\(\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]

unzip :: [(a, b)] -> ([a], [b]) Исходный код

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

Примеры

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

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

unzip3 :: [(a, b, c)] -> ([a], [b], [c]) Исходный код

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

Примеры

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

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

errorEmptyList :: HasCallStack => String -> a Исходный код

augment :: (forall b. (a -> b -> b) -> b -> b) -> [a] -> [a] Исходный код

Производитель списка, который можно объединить с foldr. Эта функция представляет собой лишь

   augment g xs = g (:) xs

однако упрощатель GHC преобразует выражение вида foldr k z (augment g xs), которое может возникнуть после встраивания, в g k (foldr k z xs), избегая создания промежуточного списка.

build :: (forall b. (a -> b -> b) -> b -> b) -> [a] Исходный код

Производитель списка, который можно объединить с foldr. Эта функция представляет собой лишь

   build g = g (:) []

однако упрощатель GHC преобразует выражение вида foldr k z (build g), которое может возникнуть после встраивания, в g k z, избегая создания промежуточного списка.