GHC.Список

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

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' исчерпает память (расходится).

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

Если вам нужен строгий правый сгиб с постоянной памятью, вам нужна структура, которая поддерживает доступ к правому элементу быстрее, чем \(\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 Source

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 Source

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

foldl1 :: HasCallStack => (a -> a -> a) -> [a] -> a Source

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 Source

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

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

length :: [a] -> Int Source

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

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 Source

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 Source

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 Source

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 Source

Функция 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 Source

Функция 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 Source

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 Source

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 Source

Применяемая к предикату и списку, 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 Source

Применяемая к предикату и списку, 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 Source

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

concat :: [[a]] -> [a] Source

Конкатенация списка списков.

Примеры

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

>>> concat []
[]

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

concatMap :: (a -> [b]) -> [a] -> [b] Source

Карта функции, возвращающей список, над списком, и конкатенация результатов. 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] Source

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

(++) конкатенирует два списка, т.е.,

[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] Source

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

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

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

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

ВНИМАНИЕ: Эта функция частичная. Рассмотрите использование unsnoc вместо этого.

Примеры

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

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

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

tail :: HasCallStack => [a] -> [a] Source

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

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

ВНИМАНИЕ: Эта функция частичная. Рассмотрите использование unsnoc вместо этого.

Примеры

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

>>> init [1]
[]

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

uncons :: [a] -> Maybe (a, [a]) Source

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

Since: base-4.8.0.0

unsnoc :: [a] -> Maybe ([a], a) Source

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

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

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

Since: base-4.19.0.0

(!?) :: [a] -> Int -> Maybe a infixl 9 Source

Оператор индекса списка (подстрочный индекс), начиная с 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 Source

Оператор индекса списка (подстрочный индекс), начиная с 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] Source

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

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

\(\mathcal{O}(n)\). Жесткая версия функции scanl.

scanr :: (a -> b -> b) -> b -> [a] -> [b] Source

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

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

Функция 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] Source

Функция iterate' — это строгая версия функции iterate.

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

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

repeat :: a -> [a] Source

Функция 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] Source

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

Примеры

>>> replicate 0 True
[]

>>> replicate (-1) True
[]

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

cycle :: HasCallStack => [a] -> [a] Source

Функция 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] 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 возвращает кортеж, где первый элемент — это префикс длиной 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]

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

reverse :: [a] -> [a] Source

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

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

zip3 берёт три списка и возвращает список троек, аналогично 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]

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

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