Кортеж - это структура данных, которая представляет упорядоченный набор фиксированной длины, состоящий из элементов, как правило, разных типов
В Haskell кортеж представляется с помощью круглых скобок, например, ("Haskell", 2010) или (1, True, "Third", 4.0, '5'). При этом такие кортежи имеют тип, который описывает типы находящихся в них элементах
ghci> :t ("Haskell", 2010)
("Haskell", 2010) :: Num b => (String, b)
ghci> :t (1, True, "Third", 4.0, '5')
(1, True, "Third", 4.0, '5')
:: (Fractional d, Num a) => (a, Bool, String, d, Char)
В кортеже символ запятой , - это оператор a -> b -> (a, b), который берет два типа и возвращает кортеж, поэтому кортежи можно создавать так:
(,) "Haskell" 2010
(,,,,) 1 True "Third" 4.0 '5'
Если кортеж состоит из двух элементов, то к нему можно применить функции fst и snd для возврата первого и второго элементов соответственно:
ghci> fst ("Haskell", 2010)
"Haskell"
ghci> snd ("Haskell", 2010)
2010
Кортежи используются в функции каррирования - преобразования функции от многих аргументов в набор вложенных функций, каждая из которых является функцией от одного аргумента (процесс назван в честь математика Хаскелла Брукса Карри)
В Haskell функция curry позволяет превратить функцию от двух аргументов в функцию от одного, которая принимает еще один аргумент
ghci> :t curry
curry :: ((a, b) -> c) -> a -> b -> c
С помощью curry можно вызвать функцию без скобок:
ghci> curry fst "Haskell" 2010
"Haskell"
А с помощью обратной функции uncurry, которая выполняется декаррирование, можно выполнить обратное преобразование, чтобы передать аргументы как кортеж:
ghci> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c
ghci> uncurry div (3, 2)
1
Пример использования каррирования - пусть есть функции hasAccess и checkRequest с разными сигнатурами:
hasAccess :: String > String -> Bool
hasAccess role page
| role = "admin" = True
| role = "user" && page = "moin" = True
| otherwise - Falsa
request = ("admin", "dashboard")
checkRequest :: (String, String) -> Bool
checkRequest принимает кортеж, а hasAccess - 2 аргумента. Здесь есть 3 способа, чтобы вызвать hasAccess в checkRequest:
-- 1: через функции `fst` и `snd`
checkRequest request = hasAccess (fst request) (snd request)
-- 2: через декаррирование
checkRequest request = uncurry hasAccess request
-- или в бесточечном стиле
checkRequest = uncurry hasAccess
-- 3: сопоставление с образцом
checkRequest :: (String, String) -> Bool
checkRequest (role, page) = hasAccess role page
Список - это односвязная структура данных, которая представляет упорядоченный набор элементов одного типа
В Haskell список создается с помощью квадратных скобок:
myList = [1, 2, 3, 4]
myList здесь имеет тип [Int]. Также в Haskell тип строки String - это список символов [Char]
Для работы со списками есть два правоассоциативных оператора:
: - добавление элемента в голову списка, например:
ghci> 1 : 2 : 3 : 4 : []
[1,2,3,4]
++ - конкатенация двух списков:
ghci> [1] ++ [2] ++ [3, 4]
[1,2,3,4]
Списки в Haskell хранятся как односвязный список - узлы помимо значения хранят ссылку на следующий узел. Поэтому, если есть список [2, 3, 4], то добавление в начало 1 не клонирует весь список, а возвращает ссылку на список [1, 2, 3, 4]:
ghci> a = [2, 3, 4]
ghci> b = 1 : a
ghci> a
[2,3,4]
ghci> b
[1,2,3,4]
С другой стороны, оператор ++ изменяет ссылки в существующих узлах, что нарушило бы иммутабельность объектов, поэтому при конкатенации первый список копируется, из-за чего временная сложность операции ++ получается O(n), где n - длина первого списка:
ghci> a = [3, 4]
ghci> b = [1, 2]
ghci> c = b ++ a
ghci> a
[3,4]
ghci> b
[1,2]
ghci> c
[1,2,3,4]
Также есть другие функции для работы со списками:
head возвращает голову списка:
ghci> head [10, 20, 30]
10
tail возвращает список, который расположен после головы:
ghci> tail [10, 20, 30]
[20,30]
!! позволяет вернуть элемент из списка по индексу:
ghci> [10, 20, 30] !! 1
20
null возвращает истину, если список пуст:
ghci> null []
True
length возвращает длину списка (эта функция работает за O(n)):
ghci> length [10, 20, 30]
3
Функции head, tail и !! являются частичными, что означает, что они не определены для некоторых аргументов. Так, head и tail бросают исключение, если список пуст, а !! не работает, если индекс больше длины списка или отрицательный
Со списками также можно использовать сопоставление образцов:
sum' :: [Int] -> Int
sum' [] = 0
sum' (x:xs) = x + sum' xs
Здесь в функции sum' список разделяется на две части: на один элемент x и хвост xs, что позволяет рекурсивно вычислять сумму. Аналогично, можно выделять больше элементов:
sum' :: [Int] -> Int
sum' [] = 0
sum' (x1:x2:xs) = x1 + x2 + sum' xs
Однако здесь при исполнении выброситься ошибка, так как список из одного элемента не сможет обработаться
Рассмотрим другие основные функции:
Функция map, которая преобразует элементы списка:
map :: (a -> b) -> [a] -> [b]
-- если список пуст, то возвращаем его
map _ [] = []
-- если не пуст, то рекурсивно применяет функцию `f` к элементу
map f (x:xs) = f x : map f xs
Функция filter, которая возвращает элементы, удовлетворяющие предикату:
filter :: (a -> Bool) -> [a] -> [a]
-- если список пуст, то возвращаем его
filter _ [] = []
-- если не пуст, то от результата предиката решаем, что вернуть
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
Функцию filter можно также использовать с лямбда-функциями:
ghci> filter (\x -> x `mod` 2 == 0) [1, 2, 3, 10, 11]
[2,10]
В лямбда-функциях аргументы обозначаются с помощью обратного слеша \
Функция take, возвращающая префикс списка:
ghci> let arr = [42, 1, 4, 3, 42]
ghci> take 2 arr
[42,1]
Функция drop, возвращающая суффикс списка:
ghci> let arr = [42, 1, 4, 3, 42]
ghci> drop 2 arr
[4,3,42]
Функция all, возвращающая истину, если все элементы удовлетворяют предикату:
ghci> let arr = [42, 1, 4, 3, 42]
ghci> all (> 5) arr
False
Функция all, возвращающая истину, если один из элементов удовлетворяют предикату:
ghci> any (> 5) arr
True
ghci> any (> 5) [6, undefined]
-- функция any прекратит выполнение на 6,
-- таким образом не перебирая все значение
-- из-за чего не выкидывается ошибка на обработке undefined
True
Рассмотрим еще раз функцию sum':
sum' :: [Int] -> Int
sum' [] = 0
sum' (x:xs) = x + sum' xs
Здесь мы можем выделить начальное значение 0 (так называемый аккумулятор, к которому мы прибавляем элементы списка) и операцию +. Если мы параметризуем эти значения, то мы получим функцию правой свертки:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr op accumulator [] = accumulator
foldr op accumulator (x:xs) = x `op` (foldr op accumulator xs)
Функция foldr сворачивает список, начиная справа, в один элемент. Пример применения:
ghci> foldr (+) 0 [1, 2, 3] -- сумма элементов
6 -- 1 + (2 + (3 + 0))
ghci> foldr (+) 10 [1, 2, 3]
16
ghci> foldr (*) 1 [4, 5, 7] -- произведение
140 -- 4 * (5 * (7 * 0))
ghci> foldr (:) [0] [1, 2, 3, 4] -- конкатенация (добавление в конец списка)
[1,2,3,4,0] -- 1 : (2 : (3 : (4 : [0])))
Аналогично, есть левая свертка:
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl op accumulator [] = accumulator
foldl op accumulator (x:xs) = foldl op (accumulator `op` x) xs
С помощью нее можно инвертировать список:
ghci> foldl (\acc x -> x : acc) [] [1, 2, 3]
[3,2,1] -- ((([] : 1) : 2) : 3) = [3, 2, 1]
Рассмотрим производительность операций сверток. С помощью инструкции :set +s в интерпретаторе можно узнать, сколько времени и памяти заняло исполнение строки код:
ghci> a = [1 .. 200000]
(0.04 secs, 15,016 bytes)
ghci> foldr (+) 0 a
20000100000
(0.03 secs, 32,347,024 bytes)
ghci> foldl (+) 0 a
20000100000
(0.14 secs, 32,275,808 bytes)
ghci> foldl' (+) 0 a
20000100000
(0.01 secs, 17,656,664 bytes)
Как видно, в среднем foldl работает медленнее, чем foldr. Связано это с выполнением ленивых вычислений в Haskell, из-за чего сначала строится дерево вычислений, которое в конце вычисляется. Альтернативная функция левой свертки foldl' позволяет принудительно совершать вычисления (из-за чего работает быстрее и использует меньше памяти), но работает не со всеми операциями
Также существенно понимать различия в порядке обхода. foldr обрабатывает элементы слева направо, из-за чего может прекратить обработку, не доходя до конца списка:
ghci> foldr (&&) True (False : undefined)
-- = False && foldr (&&) True undefined
False
ghci> foldr (\x acc -> x = 5 || acc) False [1 ..] -- бесконечный список😈
True
foldl же нужно добрать до конца списка, из-за чего могут возникнуть ошибки:
ghci> foldl (&&) True (False : undefined)
-- = foldl (&&) (True && False) undefined
*** Exception: Prelude.undefined
ghci> foldl (\acc x -> acc || x = 5) False [1 ..]
-- выполнение не останавливается
Подробнее об различиях левой и правой сверток: https://blog.haskell.org/foldl-and-foldr/
Haskell позволяет задавать списки с помощью генераторов. Генератор не создает все элементы списка, а хранит только правилам, по которым можно создать следующий элементы
Генератор задается через .., например:
ghci> [1 .. 5]
[1,2,3,4,5]
ghci> [1, 3 .. 10]
[1,3,5,7,9]
ghci> [10, 9 .. 7]
[10,9,8,7]
Также можно создать бесконечные списки, не указывая верхней границы:
ghci> [10, 9 .. ]
[10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,-12,-13,-14,-15,-16,-17,-18,-19,-20,-21 -- ну и еще триллион чисел
Бесконечные списки могут иметь смысл с функцией take
ghci> take 6 [10, 9 .. ]
[10,9,8,7,6,5]
Также можно задавать другие правила:
ghci> [n * n | n <- [1..10]]
-- ^ результат ^ исходный список
-- квадраты чисел от 1 до 10
[1,4,9,16,25,36,49,64,81,100]
ghci> take 6 [n | n <- [1 ..], even n]
-- ^ фильтр
-- первые 6 четных чисел
[2,4,6,8,10,12]
ghci> take 6 [(n, n * n) | n <- [1 ..], even n]
-- кортежи первые 6 четных чисел и их квадратов
[(2,4),(4,16),(6,36),(8,64),(10,100),(12,144)]
ghci> [(a, b) | a <- [1 .. 3], b <- [4 .. 5]]
-- декартово произведение
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]