Изучай 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: