Изучай Haskell ради Добра! Функции высшего порядка

Изучай Haskell ради Добра! Функции высшего порядка

Функции высшего порядка

Функции в Хаскеле могут принимать другие функции как параметры и возвращать функции в качестве результата. Если некая функция делает что-либо из вышеперечисленного, ее называют функцией высших порядков (ФВП). ФВП не просто значительная часть присущего Хаскелю характера программирования, они по большей части и задают этот характер. Как оказывается, ФВП незаменимы если вы хотите программировать, определяя что вы хотите получить, вместо того чтобы определять последовательность шагов, описывая как это получить. Это очень мощный способ решения задач и размышлений о программах.

Каррированные функции

Каждая функция в Хаскеле официально может иметь только один параметр. Но мы определяли и использовали функции, которые принимали несколько параметров, как так может быть? Да, это хитрый трюк! Все функции, которые принимали несколько параметров, были каррированы. Что это значит? Легче всего объяснить на примере. Возьмем нашего старого друга, функцию max. Похоже что она принимает два параметра и возвращает максимальный из них. Если сделать вызов max 4 5, то вначале будет создана функция, которая принимает один параметр, и возвращает 4 или параметр, смотря что больше. Затем 5 передается в эту функцию, и мы получаем желаемый результат. Выглядит неудобоваримо, но на самом деле это очень крутая концепция. Следующие два вызова эквивалентны:

ghci> max 4 5

5

ghci> (max 4) 5

5

Пробел между двумя частями текста означает применение функции. Пробел это нечто вроде оператора языка, и он имеет наивысший приоритет. Давайте посмотрим на тип функции max.
max :: (Ord a) => a -> a -> a.
Это может быть записано как
max :: (Ord a) => a -> (a -> a)
Прочитать можно так - max принимает параметр типа a и возвращает (->) функцию, которая принимает тип a и возвращает тип a. Вот почему возвращаемый функцией тип и параметры функции просто разделяются стрелками.

Ну и чем это выгодно для нас? Проще говоря, если мы вызываем функцию и передаем ей не все параметры, в результате мы получаем новую функцию, результат частичного применения исходной функции. Новая функция принимает столько параметров, сколько мы пропустили при вызове оригинальной функции. Частичное применение (или вызов функции не со всеми параметрами, если хотите) это изящный способ для создания новых функций "на лету", мы можем передать их другой функции или передать им еще какие-нибудь параметры.

Посмотрим на эту до обидного простую функцию:

multThree :: (Num a) => a -> a -> a -> a

multThree x y z = x * y * z

Что происходит если мы вызываем multThree 3 5 9 или ((multThree 3) 5) 9? Первое, 3 применяется к multThree, так как они разделены пробелом. Это создает функцию, которая принимает один параметр и возвращает новую функцию, которая умножает на три. Затем 5 применяется к новой функции, что дает функцию, которая примет параметр и умножит его на 15. 9 применяется к этой функции и получается результат 135, или что-то около того. Вспомним, что тип этой функции может быть записан как multThree :: (Num a) => a -> (a -> (a -> a)). Перед a -> пишется параметр функции, после записывается что функция вернет. Таким образом наша функция принимает параметр типа а и возвращает функцию типа (Num a) => a -> (a -> a). Таким же образом, эта функция принимает а и возвращает функцию типа (Num a) => a -> a. На последней итерации функция принимает а и возвращает а. Посмотрите:

ghci> let multTwoWithNine = multThree 9

ghci> multTwoWithNine 2 3

54

ghci> let multWithEighteen = multTwoWithNine 2

ghci> multWithEighteen 10

180

Вызывая функции не со всеми параметрами, мы создаем новые функции "на лету". Что если нам нужно создать функцию, которая принимает число и сравнивает его с константой 100? Мы можем сделать это так:

compareWithHundred :: (Num a, Ord a) => a -> Ordering

compareWithHundred x = compare 100 x

Если мы вызовем функцию с 99, она вернет GT. Довольно просто. Обратите внимание, что х находится с правой стороны в обоих частях определения. Теперь подумаем, что вернет compare 100. Этот вызов вернет функцию, которая принимает параметр и сравнивает его с константой 100. Вау! Не этого ли мы хотели? Можно переписать функцию так:

compareWithHundred :: (Num a, Ord a) => a -> Ordering

compareWithHundred = compare 100

Объявление типа не изменилось, так как compare 100 возвращает функцию. Compare имеет тип (Ord a) => a -> (a -> Ordering) и вызов с параметром 100 вернет a (Num a, Ord a) => a -> Ordering. Еще один ограничитель типа проник сюда потому что 100 - это часть класса типов Num.

Йоу! Пожалуйста, убедитесь что вы понимаете как работает каррирование и частичное применение функций, потому что это очень важно!

Инфиксные функции могут быть частично применены используя секции. Для секционирования инфиксной функции просто поместите ее в круглые скобки и предоставьте параметр только с одной стороны. Это создаст функцию, которая принимает один параметр и применяет его к стороне с пропущенным операндом. Убийственно простой пример:

divideByTen :: (Floating a) => a -> a

divideByTen = (/10)

Вызов, скажем, divideByTen 200 эквивалентен как вызову 200 / 10, так и (/10) 200. Функция, которая проверяет находится ли переданный символ в верхнем регистре:

isUpperAlphanum :: Char -> Bool

isUpperAlphanum = (`elem` ['A'..'Z'])

Единственная особенность при использовании секций - использование знака "минус". По определению секций, (-4) это функция которая вычитает четыре из переданного числа. В то же время, для удобства, (-4) означает "минус четыре". Если вы хотите создать функцию которая вычитает четыре из своего аргумента, выполняйте частичное применение таким образом: (subtract 4).

Что произойдет, если мы попробуем просто выполнить multThree 3 4 в GHCI, вместо привязки к имени с помощью let, либо передачи другой функции?

ghci> multThree 3 4

<interactive>:1:0:

No instance for (Show (t -> t))

arising from a use of `print' at <interactive>:1:0-12

Possible fix: add an instance declaration for (Show (t -> t))

In the expression: print it

In a 'do' expression: print it

GHCI сообщает нам, что выражение порождает функцию типа a -> a, но не знает, как вывести её на экран. Функции не являются сущностями класса типов Show, так что мы не можем получить аккуратное строковое представление функций. Когда мы вводим, скажем, 1 + 1 в терминале GHCI, он сначала вычисляет результат, 2, а затем вызывает show для 2, чтобы получить текстовое представление этого числа. Текстовое представление 2 - это строка "2", которая и выводится на наш экран.

Немного высоких материй

Функции могут принимать функции как параметры и возвращать функции. Чтобы проиллюстрировать это, мы собираемся создать функцию, которая принимает функцию, а затем дважды применяет её к чему нибудь!

applyTwice :: (a -> a) -> a -> a

applyTwice f x = f (f x)

Прежде всего обратите внимание на объявление типа. Раньше мы не нуждались в скобках, потому что -> обладает правой ассоциативностью. Однако здесь они обязательны. Они показывают, что первый параметр это функция, которая принимает параметр некоторого типа и возвращает результат такого же типа. Второй параметр - имеет тот же тип что и аргумент функции, как и возвращаемый результат. Мы можем прочитать данное объявление в каррированом стиле, но чтобы избежать головной боли, мы просто скажем, что функция принимает два параметра и возвращает результат. Первый параметр это функция (она имеет тип a -> a), второй параметр имеет тот же тип а. Функция может быть Int -> Int или String -> String, или еще какого-нибудь. Но второй параметр обязательно должен совпадать по типу с типом результата функции.

Примечание: Отныне мы будем говорить что функция принимает несколько параметров, вопреки тому что в действительности каждая функция принимает только один параметр и возвращает частично-примененную функцию. Так продолжается до тех пор, пока мы не получим функцию возвращающую фиксированное значение. Для простоты мы будет говорить, что a -> a -> a принимает два параметра, хоть мы и знаем, что происходит "под капотом".

Тело у нашей новой функции будет достаточно простое. Мы используем параметр f как функцию, применяя её к параметру x (для этого мы разделяем их пробелом), после чего передаем результат снова в f. Давайте поиграемся с функцией:

ghci> applyTwice (+3) 10

16

ghci> applyTwice (++ " HAHA") "HEY"

"HEY HAHA HAHA"

ghci> applyTwice ("HAHA " ++) "HEY"

"HAHA HAHA HEY"

ghci> applyTwice (multThree 2 2) 9

144

ghci> applyTwice (3:) [1]

[3,3,1]

Красота и полезность частичного применения очевидна. Если наша функция требует передать ей функцию одного аргумента, мы можем частично применить функцию-параметр таким образом, чтобы оставался неопределенным всего один параметр, и затем передать её нашей функции.

Теперь мы собираемся применить ФВП для реализации очень полезной функции из стандартной библиотеки. Она называется zipWith. Эта функция принимает функцию и два списка, а затем соединяет списки, применяя переданную функцию для соответствующих элементов. Вот как мы её реализуем:

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]

zipWith' _ [] _ = []

zipWith' _ _ [] = []

zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

Посмотрите на объявление типа. Первый параметр - это функция, которая принимает два значения и возвращает одно. Параметры этой функции не обязательно должны иметь одинаковый тип, но могут. Второй и третий параметры - списки. Результат тоже является списком. Первым идет список элементов типа а, потому что функция соединения принимает a в качестве первого параметра. Второй должен быть списком из элементов типа b, потому что второй параметр у связывающей функции имеет тип b. Результат - список элементов типа c. Если объявление функции говорит, что она принимает функцию типа a -> b -> c как параметр, то это означает, что она также примет и функцию a -> a -> a, но не наоборот. Запомните, когда вы создаете функции, особенно высоких порядков, и не уверены каким должен быть тип, вы может попробовать опустить объявление типа, а затем проверить, какой тип выведет Хаскель, используя :t.

Устройство данной функции очень похоже на обычный 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' (++) ["foo ", "bar ", "baz "] ["fighters", "hoppers", "aldrin"]

["foo fighters","bar hoppers","baz aldrin"]

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]]

Как вы видите, одна-единственная функция высшего порядка может применяться очень разными способами. Императивное программирование обычно использует механизмы вроде циклов for и while, переменных и проверки их состояния, и так далее для того чтобы достичь некоторого поведения, а затем оборачивает его в некий интерфейс навроде функции. Функциональное программирование использует ФВП для того чтобы абстрагироваться от деталей при реализации общеупотребимых шаблонов программирования, вроде проверки двух списков попарно и выполнения некоторых действий над результатом, или получения множества решений и отбрасывания тех решений, которые вам не нужны.

Теперь реализуем еще одну функцию из стандартной библиотеки, 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> flip' zip [1,2,3,4,5] "hello"

[('h',1),('e',2),('l',3),('l',4),('o',5)]

ghci> zipWith (flip' div) [2,2..] [10,8,6,4,2]

[5,4,3,2,1]

Отображения и фильтры

map берет функцию и список, применяет функцию к каждому элементу списка, формируя новый список. Давайте посмотрим на сигнатуру этой функции и как она определена.

map :: (a -> b) -> [a] -> [b]

map _ [] = []

map f (x:xs) = f x : map f xs

Сигнатура функции говорит нам, что map принимает функцию которая вычисляет a по b, список элементов типа a и возвращает список элементов типа b. Интересно, что только глядя на сигнатуру функции, вы можете сказать, что она делает. map это одна из самых универсальных ФВП и она может использоваться миллионом разных способов. Вот она в действии:

ghci> map (+3) [1,5,3,1,6]