Миран Липовача - Изучай Haskell во имя добра!

ПРИМЕЧАНИЕ.Удостоверьтесь в том, что вы поняли, как работает каррирование и частичное применение функций, поскольку эти понятия очень важны.

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

applyTwice :: (a –> a) –> a –> a

applyTwice f x = f (f x)

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

ПРИМЕЧАНИЕ.Отныне мы будем говорить, что функция принимает несколько параметров, вопреки тому что в действительности каждая функция принимает только один параметр и возвращает частично применённую функцию. Для простоты будем говорить, что a –> a –> aпринимает два параметра, хоть мы и знаем, что происходит «за кулисами».

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

ghci> applyTwice (+3) 10

16

ghci> applyTwice (++ " ХА-ХА") "ЭЙ"

"ЭЙ ХА-ХА ХА-ХА"

ghci> applyTwice ("ХА-ХА " ++) "ЭЙ"

"ХА-ХА ХА-ХА ЭЙ"

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, потому что функция сцепления принимает значение типа 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' :: (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, то получаем функцию, которая принимает два параметра, но переставляет их при вызове. Даже несмотря на то, что такие «перевёрнутые» функции обычно передаются в другие функции, мы можем воспользоваться преимуществами каррирования при создании ФВП, если подумаем наперёд и запишем, каков будет конечный результат при вызове полностью определённых функций.