Миран Липовача - Изучай Haskell во имя добра!
zipWith' :: (a –> b –> c) –> [a] –> [b] –> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
Посмотрите на объявление типа. Первый параметр – это функция, которая принимает два значения и возвращает одно. Параметры этой функции не обязательно должны быть одинакового типа, но могут. Второй и третий параметры – списки. Результат тоже является списком. Первым идёт список элементов типа a, потому что функция сцепления принимает значение типа a в качестве первого параметра. Второй должен быть списком из элементов типа b, потому что второй параметр у связывающей функции имеет тип b. Результат – список элементов типа c. Если объявление функции говорит, что она принимает функцию типа a –> b –> c как параметр, это означает, что она также примет и функцию a –> a –> a, но не наоборот.
ПРИМЕЧАНИЕ. Запомните: когда вы создаёте функции, особенно высших порядков, и не уверены, каким должен быть тип, вы можете попробовать опустить объявление типа, а затем проверить, какой тип выведет язык Haskell, используя команду :t в GHCi.
Устройство данной функции очень похоже на обычную функцию zip. Базовые случаи одинаковы. Единственный дополнительный аргумент – соединяющая функция, но он не влияет на базовые случаи; мы просто используем для него маску подстановки _. Тело функции в последнем образце также очень похоже на функцию zip – разница в том, что она не создаёт пару (x, y), а возвращает f x y. Одна функция высшего порядка может использоваться для решения множества задач, если она достаточно общая. Покажем на небольшом примере, что умеет наша функция zipWith':
ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]
[6,8,7,9]
ghci> zipWith' max [6,3,2,1] [7,3,1,5]
[7,3,2,5]
ghci> zipWith' (++) ["шелдон ", "леонард "] ["купер", "хофстадтер"]
["шелдон купер","леонард хофстадтер"]
ghci> zipWith' (*) (replicate 5 2) [1..]
[2,4,6,8,10]
ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]] [[3,4,6],[9,20,30],[10,12,12]]
Как видите, одна-единственная функция высшего порядка может применяться самыми разными способами.
Реализация функции flip
Теперь реализуем ещё одну функцию из стандартной библиотеки, flip. Функция flip принимает функцию и возвращает функцию. Единственное отличие результирующей функции от исходной – первые два параметра переставлены местами. Мы можем реализовать flip следующим образом:
flip' :: (a –> b –> c) –> (b –> a –> c)
flip' f = g
where g x y = f y x
Читая декларацию типа, мы видим, что функция принимает на вход функцию с параметрами типов a и b и возвращает функцию с параметрами b и a. Так как все функции на самом деле каррированы, вторая пара скобок не нужна, поскольку символ –> правоассоциативен. Тип (a –> b –> c) –> (b –> a –> c) – то же самое, что и тип (a –> b –> c) –> (b –> (a –> c)), а он, в свою очередь, представляет то же самое, что и тип (a –> b –> c) –> b –> a –> c. Мы записали, что g x y = f y x. Если это верно, то верно и следующее: f y x = g x y. Держите это в уме – мы можем реализовать функцию ещё проще.
flip' :: (a –> b –> c) –> b –> a –> c
flip' f y x = f x y
Здесь мы воспользовались тем, что функции каррированы. Когда мы вызываем функцию flip' f без параметров y и x, то получаем функцию, которая принимает два параметра, но переставляет их при вызове. Даже несмотря на то, что такие «перевёрнутые» функции обычно передаются в другие функции, мы можем воспользоваться преимуществами каррирования при создании ФВП, если подумаем наперёд и запишем, каков будет конечный результат при вызове полностью определённых функций.
ghci> zip [1,2,3,4,5,6] "привет"
[(1,'п'),(2,'р'),(3,'и'),(4,'в'),(5,'е'),(6,'т')]
ghci> flip' zip [1,2,3,4,5] "привет"
[('п',1),('р',2),('и',3),('в',4),('е',5),('т',6)]
ghci> zipWith div [2,2..] [10,8,6,4,2]
[0,0,0,0,1]
ghci> zipWith (flip' div) [2,2..] [10,8,6,4,2]
[5,4,3,2,1]
Если применить функцию flip' к zip, то мы получим функцию, похожую на zip, за исключением того что элементы первого списка будут оказываться вторыми элементами пар результирующего списка, и наоборот. Функция flip' div делит свой второй параметр на первый, так что если мы передадим ей числа 2 и 10, то результат будет такой же, что и в случае div 10 2.
Инструментарий функционального программиста
Как функциональные программисты мы редко будем обрабатывать одно значение. Обычно нам хочется сразу взять набор чисел, букв или значений каких-либо иных типов, а затем преобразовать всё это множество для получения результата. В данном разделе будет рассмотрен ряд полезных функций, которые позволяют нам работать с множествами значений.
Функция map
Функция map берёт функцию и список и применяет функцию к каждому элементу списка, формируя новый список. Давайте изучим сигнатуру этой функции и посмотрим, как она определена.
map :: (a –> b) –> [a] –> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
Сигнатура функции говорит нам, что функция map принимает на вход функцию, которая вычисляет значение типа b по параметру типа a, список элементов типа a и возвращает список элементов типа b. Интересно, что глядя на сигнатуру функции вы уже можете сказать, что она делает. Функция map – одна из самых универсальных ФВП, и она может использоваться миллионом разных способов. Рассмотрим её в действии:
ghci> map (+3) [1,5,3,1,6]
[4,8,6,4,9]
ghci> map (++ "!") ["БУХ", "БАХ", "ПАФ"]
["БУХ!","БАХ!","ПАФ!"]
ghci> map (replicate 3) [3..6]
[[3,3,3],[4,4,4],[5,5,5],[6,6,6]]
ghci> map (map (^2)) [[1,2],[3,4,5,6],[7,8]]
[[1,4],[9,16,25,36],[49,64]]
ghci> map fst [(1,2),(3,5),(6,3),(2,6),(2,5)]
[1,3,6,2,2]
Возможно, вы заметили, что нечто аналогичное можно сделать с помощью генератора списков. Вызов map (+3) [1,5,3,1,6] – это то же самое, что и [x+3 | x <– [1,5,3,1,6]]. Тем не менее использование функции map обеспечивает более читаемый код в случаях, когда вы просто применяете некоторую функцию к списку. Особенно когда применяются отображения к отображениям (map – к результатам выполнения функции map): тогда всё выражение с кучей скобок может стать нечитаемым.
Функция filter
Функция filter принимает предикат и список, а затем возвращает список элементов, удовлетворяющих предикату. Предикат – это функция, которая говорит, является ли что-то истиной или ложью, – то есть функция, возвращающая булевское значение. Сигнатура функции и её реализация:
filter :: (a –> Bool) –> [a] –> [a]
filter _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
Довольно просто. Если выражение p x истинно, то элемент добавляется к результирующему списку. Если нет – элемент пропускается.
Несколько примеров:
ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]
[5,6,4]
ghci> filter (==3) [1,2,3,4,5]
[3]
ghci> filter even [1..10]
[2,4,6,8,10]
ghci> let notNull x = not (null x) in filter notNull [[1],[],[3,4],[]]
[[1],[3,4]]
ghci> filter (`elem` ['а'..'я']) "тЫ СМЕЕШЬСя, ВЕДЬ я ДрУГой"
"тяярой"
ghci> filter (`elem` ['А'..'Я']) "я Смеюсь, Ведь ты такОЙ же"
"СВОЙ"
Того же самого результата можно достичь, используя генераторы списков и предикаты. Нет какого-либо правила, диктующего вам, когда использовать функции map и filter, а когда – генераторы списков. Вы должны решить, что будет более читаемым, основываясь на коде и контексте. В генераторах списков можно применять несколько предикатов; при использовании функции filter придётся проводить фильтрацию несколько раз или объединять предикаты с помощью логической функции &&. Вот пример:
ghci> filter (<15) (filter even [1..20])
[2,4,6,8,10,12,14]
Здесь мы берём список [1..20] и фильтруем его так, чтобы остались только чётные числа. Затем список передаётся функции filter (<15), которая избавляет нас от чисел 15 и больше. Вот версия с генератором списка:
ghci> [ x | x <- [1..20], x < 15, even x]
[2,4,6,8,10,12,14]
Мы используем генератор для извлечения элементов из списка [1..20], а затем указываем условия, которым должны удовлетворять элементы результирующего списка.
Помните нашу функцию быстрой сортировки (см. предыдущую главу, раздел «Сортируем, быстро!»)? Мы использовали генераторы списков для фильтрации элементов меньших (или равных) и больших, чем опорный элемент. Той же функциональности можно добиться и более понятным способом, используя функцию filter:
