Академия: Введение в функциональное программирование. Конспект шестой недели курса: рекурсия и стек
Всем привет. Я участвую в проекте Академия от @ontofractal и публикую конспекты курса Введение в функциональное программирование от Delft University of Technology. Сегодня я хотел бы рассказать о простом и очень выразительном средстве, позволяющем создавать циклические конструкции - рекурсивных функциях. Обычно эта тема воспринимается как некое эзотерическое знание, доступное лишь избранным ФП-ниндзям, но смею вас уверить, что это не так, и понять, как работает рекурсия, может каждый
Рекурсивные функции
Рекурсия - это прием, при котором функция в качестве результата вычисления возвращает саму себя. В качестве иллюстрации напишем функцию, вычисляющую степень заданного числа:
prod :: [Int] -> Intprod [] = 0prod [x] = xprod (x:xs) = x * prod xs Первая строка описывает случай, когда мы передаем функции пустой список. Вторая строка - это базовый случай; именно он определяет, когда прерывается цепочка вызовов функции. Ну и третья строка - это само рекурсивное определение функции. Обращу внимания на новый для нас элемент синтаксиса: двоеточие. Этот инфиксный оператор используется так: аргумент с левой стороны становится головой списка, правый - остатком. Запись 5 : [4,3,2] даста результат [5,4,3,2]
Теперь для лучшего понимания, предлагаю посмотреть, как наша функция будет вычисляться. Для этого мы будем подставлять получающиеся аргументы в рекурсивные вызовы и наглядно увидим, как получается итоговый результат (этот метод называется подстановочной моделью)
Как мы видим, все получилось довольно просто: мы вызываем функцию, подставляя в качестве аргументов первый элемент и остаток и откладываем вычисление функции до тех пор, пока не получим базовый случай (список из одного элемента). После этого мы подставляем результат последнего вычисления в отложенные вычисления и наконец получаем требуемый результат
Элиминация хвостового вызова
Модель вычислений, изображенная выше, проста для понимания, но в ней есть серьезный изъян: она предполагает выделение памяти под отложенные вычисления. Остановимся на этом моменте подробнее
Как известно, при выполении программ в памяти создается стек вызовов. Это специальная структура, которая хранит информация о выполняемых функциях. В упрощенном виде его работу можно представить так:
В этом примере у нас есть четыре функции, которые последовательно вызывают друг друга. При вызове каждой функции в стек загружаются ее параметры и локальные переменные. Вместе эти элементы называются фрейм стека
Теперь представим, что первая функция - рекурсивная, и все последующие вызовы, обозначенные цифрами 2-4 - это вызовы самой себя с новыми аргументами (как в нашей подстановочной модели). Тогда получится, что каждая итерация будет создавать новый стек, и, соответсвенно, занимать место в памяти. В таком случае, если мы дадим функции prod достаточно длинный список, это может привести к переполнению стека. К счастью, в реальности вычисление рекурсивных функций происходит совершенно иначе, благодаря технике, названной элиминация хвостового вызова
Суть этой техники в том, чтобы извлечь из старого фрейма информацию, которую нужно передать следующему вызову и удалить его, вместо создания нового фрейма под очередной вызов рекурсивной функции. Вот как это будет выглядеть на нашей схеме:
К сожалению, не все языки поддерживают эту технику, поэтому в императивных языках для создания циклов нужно использовать специальные конструкции, например for или while.
Несколько аргументов
В работе с рекурсивными функциями никто не ограничивает нас использованием только одного аргумента. Как пример предлагаю написать собственную реализацию стандартной функции zip, которая берет два списка и превращает его в один, состоящий из пар элементов исходных списков:
customZip :: [a] -> [b] -> [(a, b)]customZip [] _ = []customZip _ [] = []customZip (x:xs) (y:ys) = (x, y) : customZip (xs) (ys) И здесь все так же просто, как в предыдущем примере. Заметьте общий паттерн: создавая рекурсивные функции для работы со списками, мы разбиваем эти списки на начало и остаток, производим операции с началом и рекурсивно вызывает функцию, передавая ей остаток в качестве параметра. На мой взгляд, очень просто и удобно
Быстрая (на самом деле нет) сортировка
Если помните, в самом первом конспекте мы рассматривали пример реализации быстрой сортировки при помощи рекурсивной функции. Тогда он выглядел как китайская грамота, но теперь мы наконец можем понять все детали его реализации
quickSort :: Ord a => [a] -> [a]quickSort [] = []quickSort (x:xs) = quickSort ys ++ [x] ++ quickSort zs where ys = [y | y <- xs, y <= x] zs = [z | z <- xs, z > x]Здесь мы видим уже ставший привычным паттерн работы со списками: мы разбиваем их на начало и конец, начальный элемент ставим в серидину, а вокруг него располагаем списки из больших и меньших чем х элементов. При этом, к этим спискам мы тоже применяем функцию quickSort, и процесс повторяется, пока во всех ветках вызова quickSort не будет достигнут базовый случай (пустой список)
Сразу скажу, что эту реализацию алгоритма сложно назвать быстрой, потому что в реальных примерах никто не создает дополнительные списки. Однако, этот пример хорошо иллюстрирует принцип применения рекурсивных функций
Что показалось самым важным на этой неделе?
В этой части мы разобрали рекурсивные функции. В ФП это одна из важнейших тем, потому что в функциональных языках отсутствуют специальные конструкции для создания циклов. Но, как мы могли убедиться, это скорее преимущество, потому как рекурсия - это наиболее естественный и простой способ создания циклов, и единственная причина, по которой она не получила широкого применение - это отсутствие в популярных языках элиминации хвостового вызова - метода оптимизации, экономящего память и предотвращающего переполнение стека
Анонс следующей части
В конспекте следующей недели мы закончим знакомство с отдельными "строительными блоками" ФП, такими как списки и рекурсивные функции, и перейдем к изучению функций высшего порядка - механизма, позволяющего комбинировать эти блоки в полноценное строение