Функции высших порядков

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

Мотивация

Всем известно, что дублирование кода – это зло. Всем известно, что очень похожие куски кода, отличающиеся только мелочами, стоит оформлять как функции, и просто вызывать эти функции. Например, пусть у вас есть две функции:

pow2 x = x^2

pow3 x = x^3

Разумеется, гораздо лучше будет даже в этом простейшем случае ввести и использовать вместо двух этих функций одну более универсальную:

pow x y = x^y

Давайте рассмотрим более сложный случай. Вот вам несколько функций, разберитесь (методом пристального взгляда, или методом ручной редукции выражений), что они делают:

foo [] = []

foo (x:xs) = x + 1 : foo xs

boo [] = []

boo (x:xs) = x * 2 : boo xs

moo :: [[a]] -> [a]

moo [] = []

moo (x:xs) = head x : moo xs

goo [] = []

goo (x:xs) | x < 0 = x+1 : goo xs

| otherwise = x : goo xs

hoo [] = []

hoo (x:xs) = sum xs : hoo xs

Первая функция увеличивает каждый элемент списка на единицу, вторая увеличивает каждый элемент в два раза. Третья функция составляет новый список из первых элементов каждого подсписка (например, moo ["Hello","World"] → "HW"), а четвертая функция увеличивает на единицу каждый отрицательный. Пятая функция создает список сумм из всех постфиксов переданного ей списка (например, hoo [1,2,3,4] →[9,7,4]).

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

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

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

Давайте попробуем привести и эти функции к как можно более общему виду, чтобы было очевидно, где у них общая часть, а где параметр:

foo [] = []

foo (x:xs) = (\t -> t+1) x : foo xs

boo [] = []

boo (x:xs) = (\t -> t*2) x : boo xs

moo [] = []

moo (x:xs) = (\t -> head t) x : moo xs

goo [] = []

goo (x:xs) =

(\t -> if t < 0 then t-1 else t) x : goo xs

hoo [] = []

hoo (x:xs) = sum xs : hoo xs

Пардон, если вы так боитесь лямбда-функций, давайте обойдемся без них:

foo [] = []

foo (x:xs) = process x : foo xs where process t = t+1

boo [] = []

boo (x:xs) = process x : boo xs where process t = t*2

moo [] = []

moo (x:xs) = process x : moo xs where process t = head t

goo [] = []

goo (x:xs) = process x : goo xs where

process t = if t < 0 then t-1 else t

hoo [] = []

hoo (x:xs) = sum xs : hoo xs

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