Каррирование
Еще на первой лекции было рассмотрено такое понятие как каррирование:
(max 1) 2 == 2
(+ 1) 2 == 3
(*) 2 3 == 6
Каррирование — это фактически частичное применение функции. Вспомним тип функции max:
max :: (Ord a) => a -> a -> a
Тип функции с N аргументами может быть интерпретирован также как тип функции с один аргументом, возвращающим функцию от (N−1) аргумента:
max :: (Ord a) => a -> (a -> a)
Таким образом явно видно, что max можно применить к одному аргументу и получить в результате частично примененную функцию.
Рассмотрим еще несколько примеров:
maxWithTwo :: (Num t) => t -> t
maxWithTwo = max 2
maxWithTwo 3 == 3
maxWithTwo 0 == 2
inc :: (Num t) => t -> t
inc = (+ 1)
inc 1 == 2
inc 4 == 5
Раз функция может быть возвращаемым значением другой функции, то наверняка она может быть и аргументом функции:
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)
applyTwice (+1) 2 == 4
applyTwice (applyTwice (*2)) 1 == 16
applyTwice (1:) [2] == [1, 1, 2]
applyTwice (++ ".") "Wow." == "Wow..."
Функции высшего порядка и каррирование позволяют делать действительно интересные вещи: чтобы передать в качестве параметра другую функцию не обязательно создавать новую функцию, можно использовать любую существующую, специализировав ее нужным количеством аргументов.
При работе со списками довольно часто используется функция zip:
zip :: [a] -> [b] -> [(a, b)]
zip [1, 2, 3, 4] [True, False, True, True] == [(1, True), (2, False), (3, True), (4, True)]
Но еще более часто используется аналог этой функции — функция zipWith,
которая вместо объединения в кортежи применяет к соответствующим элементам заданную функцию:
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith _ [] _ = [] -- если од из списков пуст,
zipWith _ _ [] = [] -- возвращаем пустой список
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith (+) [1, 2, 3, 4] [5, 6, 7, 8] == [6, 8, 10, 12]
zipWith max [1, 3, 5, 7] [6, 4, 2, 0] == [6, 4, 5, 7]
zipWith (++) ["a ", "the "] ["cat", "dog"] == ["a cat", "the dog"]
zipWith (*) (replicate 5 2) [1..] == [2, 4, 6, 8, 10]
При помощи функций высшего порядка в функциональных языках появляется возможность использовать
абстрактные шаблоны поведения. По сути, zipWith представляет собой такой шаблон для решения множества проблем.
В обычных, императивных языках программирования, обычно используются циклы каждый раз, когда нужно сделать что-то подобное zipWith.
Рассмотрим еще одну важную функцию:
flip :: (a -> b -> c) -> (b -> a -> c)
flip f x y = f y x
zipWith (flip div) [2, 2..] [10, 8, 6, 4, 2] == [5, 4, 3, 2, 1]
flip (zipWith div) [2, 2..] [10, 8, 6, 4, 2] == [5, 4, 3, 2, 1]
Другие важные функции высшего порядка — map и filter:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
fliter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
Последняя функция помогает легко реализовать, например, алгоритм «быстрой сортировки»:
quickSort :: (Ord a) => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = smallerSorted ++ [x] ++ biggerSorted
where
smallerSorted = quickSort (filter (< x) xs)
biggerSorted = quickSort (filter (>= x) xs)
При работе со списками (особенно со списками большой или бесконечной длины) применяются функции take и drop:
take :: Int -> [a] -> [a]
take 0 _ = []
take _ [] = []
take n (x:xs) = x : take (n - 1) xs
drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (_:xs) = drop (n - 1) xs
Рассмотрим их аналоги среди функций высшего порядка — функции takeWhile и dropWhile:
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ [] = []
takeWhile p (x:xs)
| p x = x : takeWhile p xs
| otherwise = []
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ [] = []
dropWhile p (x:xs)
| p x = dropWhile p xs
| otherwise = x:xs
Напишем функцию, возвращающую сумму нечетных квадратов, меньших N:
sumOfOddSquares :: (Num t) => t -> t
sumOfOddSquares n = sum (takeWhile (< n) (filter odd (map (^2) [1..])))
В некоторых случаях, функция, которую необходимо передать в качестве агрументов довольно тривиальна, но не может быть получена простым каррированием. В таких случаях обычно пользуются так называемыми лямбда-выражениями. Лямбда-выражение по сути представляет собой анонимную функцию с одним уравнением:
(\x -> x + 1)
(\x y -> x + y)
(\xs n -> length xs > n)
Лямбда-функция может иметь несколько параметров, как и обычная функция. Она также может быть каррирована, в левой части также могут быть применены образцы. Однако, поскольку лямбда функция имеет только одно уравнение, если сопоставление с образцом не пройдет, во время исполнения программа выведет ошибку. Далее мы будем иногда применять лямбда выражения для наглядности.
На практике функциональным программистам часто приходится работать со списками
или аналогичными структурами данных. В ряде случаев необходимо изменять элементы внутри
таких структур (map, filter, zip), в других случаях нужно «сворачивать» такие структуры
в одно значение (длина списка, размер структуры, сумма элементов и пр.).
Функции высшего порядка, инкапсулирующие такое поведение, называются функции-свёртки.
Рассмотрим базовую функцию свертки и ее применение:
-- «левая» свёртка
foldl :: (a -> b -> a) -> a -> [b] -> a
-- сумма элементов списка
sum :: (Num a) => [a] -> a
sum xs = foldl (\acc n -> acc + n) 0 xs
-- более простая реализация
sum = foldl (+) 0
product = foldl (*) 0
-- проверка, находится ли элемент в списке
elem :: (Eq a) => a -> [a] -> Bool
elem x xs = foldl (\acc y -> if x == y then True else acc) False xs
-- проверить, что среди элементов списка есть True
-- NB: это не совсем корректная реализация (читай ниже)
any :: [Bool] -> Bool
any = foldl (||) False
-- более простая и наглядкая реализация elem
elem x = any . map (== x)
По сути применение функции foldl (левая свертка) выглядит следующим образом:
foldl f x [a1, a2, ..., aN] = ((...((x `f` a1) `f` a2)...) `f` an)
Рассмотрим другую функцию свертки:
foldr f x [a1, a2, ..., aN] = (a1 `f` (a2 `f` (a3 `f` (... `f` (aN `f` x)...))))
map :: (a -> b) -> [a] -> [b]
map f xs = foldr (\x acc -> f x : acc) [] xs
-- корректная реализация
any :: [Bool] -> Bool
any = foldr (||) False
Свертки могут быть использованы для реализации любой функции, которая требует одного прохода по списку поэлементно и которая возвращает что-то, основываясь на этом проходе. Если вам нужно пройти по списку, чтобы получить что-то, скорее всего вам нужна свертка или функция, определённая через свёртку.
-- полезные вспомогательные функции
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f xs = foldl f (head xs) (tail xs)
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f xs = foldr f (head xs) (tail xs)
-- максимальный элемент в списке
maximum :: (Ord a) => [a] -> a
maximum = foldr1 max
-- разворот списка
reverse :: [a] -> [a]
reverse = foldl (flip (:)) []
-- фильтрация списка
filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr (\x acc -> if p x then x : acc else acc) []
-- голова списка, определённая через свёртку
head :: [a] -> a
head = foldr1 (\x _ -> x)
-- последний элемент списка, определённый через свёртку
last = [a] -> a
last = foldl1 (\_ x -> x)
Функции scanl и scanr работают как функции свертки, но сохраняют промежуточные результаты:
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanr :: (b -> a -> a) -> a -> [b] -> [a]
-- количество квадратов, меньших 1000
sqrtSums :: Int
sqrtSums = length (takeWhile (< 1000) (scanl1 (+) (map sqrt [1..]))) + 1
Еще несколько полезных функций:
-- применение функции с низшим приоритетом
($) :: (a -> b) -> a -> b
f $ x = f x
-- композиция функций
(.) :: (a -> b) -> (b -> c) -> a -> c
f . g = \x -> f (g x)
map (negate . abs) [1, -3, 5, 2, -6] == [-1, -3, -5, -2, -6]
map (sum . tail) [[1..5], [1..7], [3..6]] == [14, 27, 15]
-- найти первый куб, больший 1000
head . filter (> 1000) . map (^3) $ [1..] == 1331