Академия: Введение в функциональное программирование. Конспект седьмой недели курса: функции высшего порядка

Всем привет. Я участвую в проекте Академия от @ontofractal и публикую конспекты курса  Введение в функциональное программирование от Delft University of Technology. Как и обещал, сегодня мы закончим разбирать отдельные техники, вроде рекурсии и генераторов списков, и наконец узнаем, как они комбинируются для создания полноценных скриптов. Для этого мы разберем технику, называемую функции высшего порядка

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

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

sumTwo a = \ b -> a + b

Противоположный пример - это стандартная функция map, которая принимает в качестве аргументов функцию и список, а затем применяет эту функцию ко всем элементам списка 

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

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

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

Теперь перейдем от теории к практике и попробуем найти общие моменты в функциях, используемых для работы со списками. Для начала давайте переопределим встроенную функцию map. Чтобы получить нужный функционал, мы можем пойти двумя путями:

1. map с использованием генераторов списков

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

comprehensiveMap f [] = []

comprehensiveMap f xs = [f x | x <- xs]

2. map с использованием рекурсии

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

recursiveMap f [] = []

recursiveMap f (x:xs) = f x : recursiveMap f xs

На первый взгляд эти варианты не сильно отличаются, но описание map с помощью рекурсии имеет важное преимущество: оно позволяет увидеть тот самый повторяющийся паттерн. Чтобы вы убедились в этом, напишем свою версию функции filter:

customFilter :: (a -> Bool) -> [a] -> [a]

customFilter p [] = []

customFilter p (x:xs)

	| p x = x : customFilter xs

	| otherwise customFilter p xs

Заметили сходство? В обоих случаях мы производим какие-то операции с начальным элементом, а затем рекурсивно вызываем функцию, передавая ей в качестве аргумента остаток списка. Подобная абстрация описывается стандартной функцией fold, которой мы пользовались, когда писали свою реализацию функции product:

customProduct [] = 0  

customProduct xs = foldl (*) 1 xs 

Именно в этой функции воплощен описанный выше общий признак рекурсивной обработки 

Еще несколько примеров того, как в функциях, работающих со списками, используется общий рекурсивный паттерн

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

Функция foldr начинает обработку списка справа; первым аргументом передаваемой ей функции становится текущий элемент списка, вторым - стартовое значение (его еще называют аккумулятором, так как в нем накапливается результат проделанной работы)

В качестве примера посмотрим, как с помощью foldr реализуется функция map:

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

foldMap f xs = foldr (\ x acc -> f x : acc) [] xs

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

Таким же образом как и map, работают и остальные функции для списков: filter, product, sum, reverse

Композиция функций

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

(f ° g) (x) = f (g (x)) 

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

В Хаскеле эта операция работает точно также, но записывается немного иначе:

f . g x = f (g x)

Оператор . реализован следующим образом:

(.) :: (b -> c) -> (a -> b) -> (a -> c)

f . g = \x -> f (g x)

Например, напишем функцию, которая принимает список чисел и делает их отрицательными:

map (\x -> negate (abs x)) xs

То же самое можно записать с помощью композиции:

map (negate . abs) xs

Согласитесь, такая запись выглядит гораздо проще. Еще более явно эта простота появляется в тех случаях, когда необходимо скомбинировать 4-5 функций

Что показалось самым важным на этой неделе

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