Data.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

(++) :: [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)\). Функция intersperse принимает элемент и список и «вставляет» этот элемент между элементами списка.

Ленивость

>>> 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 возвращает конъюнкцию элементов типа Bool контейнера. Чтобы результат был 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 возвращает дизъюнкцию элементов типа Bool контейнера. Чтобы результат был 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] Исходный код

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]

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

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

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

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

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

\(\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]] Источник

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

Начиная с: 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

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)] Источник

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

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

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

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

Функция zip7 принимает семь списков и возвращает список семёрок, аналогично 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]

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

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

zipWith5 :: (a -> b -> c -> d -> e -> f) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] Источник

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

zipWith6 :: (a -> b -> c -> d -> e -> f -> g) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] Источник

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

zipWith7 :: (a -> b -> c -> d -> e -> f -> g -> h) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [h] Источник

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

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

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

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

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

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

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

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

unzip7 :: [(a, b, c, d, e, f, g)] -> ([a], [b], [c], [d], [e], [f], [g]) Исходный код

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

lines :: String -> [String] Исходный код

Разбивает аргумент на список строк, удаляя завершающие символы \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] Исходный код

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

Примеры

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

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

unlines :: [String] -> String Исходный код

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

Примеры

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

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

unwords :: [String] -> String Исходный код

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

Функция 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] Исходный код

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

Функция 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] Исходный код

Функция 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] Исходный код

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

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

Функция 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] Исходный код

Функция 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] Исходный код

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

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

Примеры

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

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

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

Примеры

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

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

genericLength :: Num i => [a] -> i Исходный код

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

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

genericDrop :: Integral i => i -> [a] -> [a] Исходный код

Функция genericDrop является перегруженной версией drop и принимает любое значение типа Integral в качестве количества пропускаемых элементов.

genericSplitAt :: Integral i => i -> [a] -> ([a], [a]) Исходный код

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

genericIndex :: Integral i => [a] -> i -> a Исходный код

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

genericReplicate :: Integral i => i -> a -> [a] Исходный код

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