Haskell Language
Списки
Поиск…
Синтаксис
пустой конструктор списка
[] :: [a]
конструктор непустого списка
(:) :: a -> [a] -> [a]
head - возвращает первое значение списка
head :: [a] -> a
last - возвращает последнее значение списка
last :: [a] -> a
tail - возвращает список без первого элемента
tail :: [a] -> [a]
init - возвращает список без последнего элемента
init :: [a] -> [a]
xs !! i - вернуть элемент по индексу i в списке xs
(!!) :: Int -> [a] -> a
взять n xs - вернуть новый список, содержащий n первых элементов списка xs
take :: Int -> [a] -> [a]
map :: (a -> b) -> [a] -> [b]
filter :: (a -> Bool) -> [a] -> [a]
(++) :: [a] -> [a]
concat :: [[a]] -> [a]
замечания
- Тип
[a]
эквивалентен[] a
. -
[]
создает пустой список. -
[]
в определении функции LHS, напримерf [] = ...
, является пустым шаблоном списка. -
x:xs
создает список, в котором элементx
добавляется в списокxs
-
f (x:xs) = ...
является совпадением шаблонов для непустого списка, гдеx
- голова, аxs
- хвост. -
f (a:b:cs) = ...
иf (a:(b:cs)) = ...
- то же самое. Они соответствуют шаблону для списка, по меньшей мере, двух элементов, где первым элементом являетсяa
, второй -b
, а остальная часть списка -cs
. -
f ((a:as):bs) = ...
не совпадает сf (a:(as:bs)) = ...
Первый - это соответствие шаблону для непустого списка списков, гдеa
- голова головы,as
также хвост головы, аbs
- хвост. -
f (x:[]) = ...
иf [x] = ...
совпадают. Они соответствуют шаблону для списка только одного элемента. -
f (a:b:[]) = ...
иf [a,b] = ...
совпадают. Они соответствуют шаблону для списка ровно двух элементов. -
f [a:b] = ...
- соответствие шаблона для списка точно одного элемента, где элемент также является списком.a
- голова элемента, аb
- хвост элемента. -
[a,b,c]
совпадает с(a:b:c:[])
. Стандартное обозначение списка - это просто синтаксический сахар для конструкторов(:)
и[]
. - Вы можете использовать
all@(x:y:ys)
, чтобы ссылаться на весь список, какall
(или любое другое имя, которое вы выбираете), вместо повторения(x:y:ys)
.
Список литературы
emptyList = []
singletonList = [0] -- = 0 : []
listOfNums = [1, 2, 3] -- = 1 : 2 : [3]
listOfStrings = ["A", "B", "C"]
Конкатенация списка
listA = [1, 2, 3]
listB = [4, 5, 6]
listAThenB = listA ++ listB -- [1, 2, 3, 4, 5, 6]
(++) xs [] = xs
(++) [] ys = ys
(++) (x:xs) ys = x : (xs ++ ys)
Основы списка
Конструктор типов для списков в Haskell Prelude - []
. Объявление типа для списка, содержащего значения типа Int
, записывается следующим образом:
xs :: [Int] -- or equivalently, but less conveniently,
xs :: [] Int
Списки в Haskell являются однородными последовательностями , то есть все элементы должны быть одного типа. В отличие от кортежей, тип списка не зависит от длины:
[1,2,3] :: [Int]
[1,2,3,4] :: [Int]
Списки создаются с использованием двух конструкторов :
[]
создает пустой список.(:)
, произносится как «cons», добавляет элементы в список. Заканчиваяx
(значение типаa
) наxs
(список значений одного и того же типаa
) создает новый список, голова которого (первый элемент) равнаx
, а хвост (остальные элементы) -xs
.
Мы можем определить простые списки следующим образом:
ys :: [a]
ys = []
xs :: [Int]
xs = 12 : (99 : (37 : []))
-- or = 12 : 99 : 37 : [] -- ((:) is right-associative)
-- or = [12, 99, 37] -- (syntactic sugar for lists)
Обратите внимание: (++)
, который может использоваться для построения списков, определяется рекурсивно в терминах (:)
и []
.
Списки обработки
Для обработки списков мы можем просто сопоставить шаблон конструкторам типа списка:
listSum :: [Int] -> Int
listSum [] = 0
listSum (x:xs) = x + listSum xs
Мы можем сопоставить больше значений, указав более сложный шаблон:
sumTwoPer :: [Int] -> Int
sumTwoPer [] = 0
sumTwoPer (x1:x2:xs) = x1 + x2 + sumTwoPer xs
sumTwoPer (x:xs) = x + sumTwoPer xs
Обратите внимание, что в приведенном выше примере нам нужно было предоставить более исчерпывающее соответствие шаблонов для обработки случаев, когда в качестве аргумента приводится список нечетных длин.
Haskell Prelude определяет множество встроенных модулей для обработки списков, таких как map
, filter
и т. Д. По возможности, вы должны использовать их вместо написания собственных рекурсивных функций.
Доступ к элементам в списках
Доступ к n- му элементу списка (с нулевым основанием):
list = [1 .. 10]
firstElement = list !! 0 -- 1
Обратите внимание, что !!
является частичной функцией, поэтому определенные входы создают ошибки:
list !! (-1) -- *** Exception: Prelude.!!: negative index
list !! 1000 -- *** Exception: Prelude.!!: index too large
Там также Data.List.genericIndex
, перегруженная версия !!
, который принимает любое Integral
значение как индекс.
import Data.List (genericIndex)
list `genericIndex` 4 -- 5
Когда они выполняются в виде односвязных списков, эти операции занимают время O (n) . Если вы часто Data.Vector
к элементам по индексу, вероятно, лучше использовать Data.Vector
(из векторного пакета) или другие структуры данных.
Изменяется
Создание списка с 1 по 10 прост с использованием нотации диапазона:
[1..10] -- [1,2,3,4,5,6,7,8,9,10]
Чтобы указать шаг, добавьте запятую и следующий элемент после элемента start:
[1,3..10] -- [1,3,5,7,9]
Обратите внимание, что Haskell всегда делает шаг как арифметическую разницу между терминами и что вы не можете указать больше, чем первые два элемента и верхнюю границу:
[1,3,5..10] -- error
[1,3,9..20] -- error
Чтобы создать диапазон в порядке убывания, всегда указывайте отрицательный шаг:
[5..1] -- []
[5,4..1] -- [5,4,3,2,1]
Поскольку Haskell не является строгим, элементы списка оцениваются только в том случае, если они необходимы, что позволяет нам использовать бесконечные списки. [1..]
- это бесконечный список, начинающийся с 1. Этот список может быть привязан к переменной или передан как аргумент функции:
take 5 [1..] -- returns [1,2,3,4,5] even though [1..] is infinite
Будьте осторожны при использовании диапазонов с плавающей запятой, потому что он допускает переполнения до половины дельта, чтобы предотвратить проблемы округления:
[1.0,1.5..2.4] -- [1.0,1.5,2.0,2.5] , though 2.5 > 2.4
[1.0,1.1..1.2] -- [1.0,1.1,1.2000000000000002] , though 1.2000000000000002 > 1.2
Диапазоны работают не только с числами, но и с любым типом, который реализует класс Enum
. Учитывая некоторые перечислимые переменные a
, b
, c
, синтаксис диапазона эквивалентен вызову этих методов Enum
:
[a..] == enumFrom a
[a..c] == enumFromTo a c
[a,b..] == enumFromThen a b
[a,b..c] == enumFromThenTo a b c
Например, с Bool
это
[False ..] -- [False,True]
Обратите внимание на пробел после False
, чтобы это не анализировалось как квалификация имени модуля (т.е. False..
будет анализироваться как .
Из модуля False
).
Основные функции в списках
head [1..10] -- 1
last [1..20] -- 20
tail [1..5] -- [2, 3, 4, 5]
init [1..5] -- [1, 2, 3, 4]
length [1 .. 10] -- 10
reverse [1 .. 10] -- [10, 9 .. 1]
take 5 [1, 2 .. ] -- [1, 2, 3, 4, 5]
drop 5 [1 .. 10] -- [6, 7, 8, 9, 10]
concat [[1,2], [], [4]] -- [1,2,4]
foldl
Так реализуется левая складка. Обратите внимание, как порядок аргументов в шаговой функции перевернут по сравнению с foldr
(правая сфера):
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs -- = foldl f (acc `f` x) xs
Левая складка, foldl
, ассоциируется слева. То есть:
foldl (+) 0 [1, 2, 3] -- is equivalent to ((0 + 1) + 2) + 3
Причина в том, что foldl
оценивается следующим образом (посмотрите на индуктивный шаг foldl
):
foldl (+) 0 [1, 2, 3] -- foldl (+) 0 [ 1, 2, 3 ]
foldl (+) ((+) 0 1) [2, 3] -- foldl (+) (0 + 1) [ 2, 3 ]
foldl (+) ((+) ((+) 0 1) 2) [3] -- foldl (+) ((0 + 1) + 2) [ 3 ]
foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [] -- foldl (+) (((0 + 1) + 2) + 3) []
((+) ((+) ((+) 0 1) 2) 3) -- (((0 + 1) + 2) + 3)
Последняя строка эквивалентна ((0 + 1) + 2) + 3
. Это потому, что (fab)
совпадает с (a `f` b)
вообще, и поэтому ((+) 0 1)
в (a `f` b)
совпадает с (0 + 1)
.
foldr
Так реализуется правильная складка:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs) -- = x `f` foldr f z xs
Правая складка, foldr
, ассоциируется справа. То есть:
foldr (+) 0 [1, 2, 3] -- is equivalent to 1 + (2 + (3 + 0))
Причина в том, что foldr
оценивается следующим образом (посмотрите на индуктивный шаг foldr
):
foldr (+) 0 [1, 2, 3] -- foldr (+) 0 [1,2,3]
(+) 1 (foldr (+) 0 [2, 3]) -- 1 + foldr (+) 0 [2,3]
(+) 1 ((+) 2 (foldr (+) 0 [3])) -- 1 + (2 + foldr (+) 0 [3])
(+) 1 ((+) 2 ((+) 3 (foldr (+) 0 []))) -- 1 + (2 + (3 + foldr (+) 0 []))
(+) 1 ((+) 2 ((+) 3 0)) -- 1 + (2 + (3 + 0 ))
Последняя строка эквивалентна 1 + (2 + (3 + 0))
, так как ((+) 3 0)
совпадает с (3 + 0)
.
Преобразование с помощью `map`
Часто мы хотим преобразовать или преобразовать содержимое коллекции (список или что-то проходящее). В Haskell мы используем map
:
-- Simple add 1
map (+ 1) [1,2,3]
[2,3,4]
map odd [1,2,3]
[True,False,True]
data Gender = Male | Female deriving Show
data Person = Person String Gender Int deriving Show
-- Extract just the age from a list of people
map (\(Person n g a) -> a) [(Person "Alex" Male 31),(Person "Ellie" Female 29)]
[31,29]
Фильтрация с помощью `filter`
Учитывая список:
li = [1,2,3,4,5]
мы можем отфильтровать список с предикатом, используя filter :: (a -> Bool) -> [a] -> [a]
:
filter (== 1) li -- [1]
filter (even) li -- [2,4]
filter (odd) li -- [1,3,5]
-- Something slightly more complicated
comfy i = notTooLarge && isEven
where
notTooLarge = (i + 1) < 5
isEven = even i
filter comfy li -- [2]
Конечно, речь идет не только о цифрах:
data Gender = Male | Female deriving Show
data Person = Person String Gender Int deriving Show
onlyLadies :: [Person] -> Person
onlyLadies x = filter isFemale x
where
isFemale (Person _ Female _) = True
isFemale _ = False
onlyLadies [(Person "Alex" Male 31),(Person "Ellie" Female 29)]
-- [Person "Ellie" Female 29]
Распаковка и распаковка списков
zip принимает два списка и возвращает список соответствующих пар:
zip [] _ = []
zip _ [] = []
zip (a:as) (b:bs) = (a,b) : zip as bs
> zip [1,3,5] [2,4,6]
> [(1,2),(3,4),(5,6)]
Закрепление двух списков функцией:
zipWith f [] _ = []
zipWith f _ [] = []
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
> zipWith (+) [1,3,5] [2,4,6]
> [3,7,11]
Распаковка списка:
unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
> unzip [(1,2),(3,4),(5,6)]
> ([1,3,5],[2,4,6])