Академия: Введение в функциональное программирование. Конспект первой недели курса
Всем привет. Недавно я заинтересовался проектом Академия и решил принять в нем участие. В качестве материала, о котором я буду рассказывать своим читателям, я решил выбрать курс от Delft University of Technology под названием Введение в функциональное программирование (Introduction to Functional Programming, fp101). Эта тема традиционно считается очень сложной для понимания, и я надеюсь, что этот курс в моем изложении сможет развенчать этот миф и показать, что с пониманием концепций ФП может справиться каждый.
К сожалению, я опоздал к окончанию экспериментального этапа, о котором совсем недавно сообщил @ontofractal. Тем не менее, я надеюсь, что мой пост все равно будет полезен читателям и проекту Академия
Почему Хаскель?
Изложение концепций ФП ведется с использованием примеров, написанных на хаскеле, вследствие чего у некоторых читателей может сложиться мнение, что знания, полученные в ходе прохождения курса будет сложно применить на практике. Однако, в самом начале лектор заостряет внимание на том факте, что одна из ключевых концепций ФП, называемая функции первого класса (first order functions) сегодня присутствует во всех популярных языках, таких как С++ или Javascript, поэтому приемы ФП можно легко использовать в повседневной деятельности, а не только при написании кода на чистых функциональных языках.
Хаскель же выбран лишь потому, что он является чистым функциональным языком, свободным от императивных конструкций, поэтому в нем характерные особенности ФП видны особенно явно.
Что такое ФП?
На этот вопрос до сих пор не существует однозначного ответа, но в широком смысле можно утверждать, что ФП - это набор техник программирование, в основе которых лежит стремление оперировать в первую очередь выражениями (expressions), а не присваиваниями (statements). Чтобы лучше понять эту мысль, обратимся к простому примеру, в котором нам нужно получить сумму чисел от одного до десяти. Сначала напишем кусок кода комбинируя разные присваивания:
let total = 0;
for(let i=1; i<=10; i++) {
total += i
}
A теперь попробуем переписать этот код, поставив во главе угла комбинирование выражений, а не присваиваний:
sum(range(1,10))
Код получилось в разы короче. В чем же дело? Все дело в том, что оперируя присваиваниями, мы вынуждены сконцентрировать внимание на том как получить результат, а не на том, что нужно получить. И в самом деле, нам ведь не нужна ни переменная total
, ни переменная i
- нас интересует лишь полученный результат. Таким образом, комбинируя присваивания мы пишем код в императивном стиле, то есть, указываем каждый шаг, ведущий нас к результату.
А теперь присмотримся ко второму примеру. Если разобрать его дословно, то мы делаем следующее:
- Мы говорим: "мне нужна последовательность чисел от одного до десяти", вызывая функцию
range
с аргументами 1 и 10 - Мы говорим: "мне нужна сумма всех элементов этой последовательности", передавая результат
range
функцииsum
Таким образом, оперируя выражениями, мы думаем по большей части о том, что мы хотим получить, а детали того, как это сделать скрыты от нас под слоем абстракций.
Конечно, мало какую реальную задачу можно решить столь малым количеством кода, однако, в дальнейшем мы с вами рассмотрим более серьезные примеры и сможем наглядно увидеть, что фунциональный подход, основанный на декларативном стиле написания кода, позволяет заметно упростить решение.
Краткий курс истории ФП(б)
Итак, мы разобрались с вопросом о том, что же такое ФП, но прежде чем перейти к собственно написанию кода (чего вы наверняка с нетерпением ждете), стоит сказать пару слов об истории этой парадигмы.
1. Создание лямбда-счисления
В основе всех функциональных языков лежит формальная система, изобретенная математиком Алонзо Черчем в 1930-х годах и названная лямбда-счислением. Целью этой системы стало создание формализма, способного описать любые возможные вычисления. По своей природе лямбда-счисление довольно просто устроено, и по большей части сводится к единственному правилу трансформации (подстановке переменных) и единственной схемой определения функций. Однако, несмотря на простоту, при помощи лямбда-счисления действительно можно выразить любую вычислимую функцию, что делает его эквивалентным машине Тьюринга.
Пример синтаксиса лямбда-выражений
2. Создание Лиспа
Следующей вехой в развитии ФП стало появление первого функционального языка, названного Лисп (Lisp, от англ. LISt Processor). В основу концепции этого языка легла мысль о том, что имея несколько простых операторов, таких как cons, car, cdr и нескольких других, можно построить Тьюринг-полный язык. И, действительно, несмотря на столь ограниченный набор встроенных конструкций, Лисп обладает огромной выразительной силой, о чем говорит широта области применения его диалектов: от создания элементов искусственного интеллекта с помощью Common Lisp до автоматизации задач в CAD-программах с AutoLisp.
3. Создание ISWIM
Созданный в 1960-х, ISWIM стал первым чисто функциональным языком; то есть, в нем в принципе не использовались императивные конструкции
4. Создание ML
Этот функциональный язык был создан с целью автоматизировать написание математических доказательств. Его создание положило начало двум концециям современного программирования: выводу типов и обобщенному программированию. Под первой понимается возможность компилятора самостоятельно определять тип переменной без его явного указания. Под обобщенным программированием же понимается написание функций, которые способны работать с разными типами данных без изменения описания функции
5. Создание SASL, KRC и Miranda
Все эти языки, созданные Дэвидом Тернером, использовали кардинально новую концепцию, названной ленивые вычисления. Суть этого стиля в том, что в нем вычисление выражения не происходит до тех пор, пока его результат не понадобится где-то в коде программы.
6. Создание Хаскеля
В 1987 году группа исследователей начала разработку языка, названного Haskell. Главной его целью было создание экосистемы для экспериментов с созданием новых языков. Однако, новый язык получился очень удачным, и в 2003 году был опубликован документ, названный Haskell 98 Report, в котором описывался стандарт языка, делающий его пригодным для повседневного использования.
Вывод
Итак, как мы могли убедиться, ФП - это очень старый стиль программирования, превосходящий по возрасту такие популярные парадигмы, как например ООП.
Привет, мир!
Наконец настало время закончить с теорией и посмотреть, как ФП можно использовать на практике. В качестве первого примера в лекции используется одна из наиболее популярных ФП техник - рекурсия. Давайте же посмотрим, как выглядит алгоритм быстрой сортировки с использованием рекурсии:
f[] = []
f(x:xs) = f ys ++ [x] ++ f zs
where
ys = [a | a <- xs, a <= x]
zs = [b | b <- xs, b > x]
При создании рекурсивных функций первым шагом мы всегда определяем базовый случай: в данном примере, если в качестве аргумента функция принимает пустой список, то она возвращает пустой список - звучит логично!
Затем мы рассматриваем вариант, когда функция получает непустой список, начинающийся с элемента x
. В этом случае мы берем все элементы, которые меньше или равны x
и добавляем их в список ys
. После этого мы берем все элементы, которые больше x
и добавляем их в список zs
. Наконец, после всего этого мы рекурсивно вызываем нашу функцию f
со списками ys
и zs
, тем самым сортируя их, и, в конце концов "склеиваем" наши списки, ставя x
в середину
Другой пример использования рекурсивных функций. В этом случае функция factorial
рекурсивно вызывает саму себя, уменьшая аргумент n
на 1 пока не будет достигнут базовый случай
Выводы и мое впечатление
На этом заканчивается первая неделя курса. На мой взгляд, курс получается довольно удачным как с точки зрения содержания, так и с точки зрения организации. Кому-то изложение может показаться слишком теоретизированым, однако, смею вас уверить, что уже со второй недели начинается собственно работа с кодом. Забегая вперед скажу, что к материалу лекций добавится также множество самостоятельных заданий, довольно простых, но в то же время полезных для понимаий концепций ФП.
Что я мог бы посоветовать сообществу Голоса после изложения первой недели? Разумеется, присоединяться к проекту и вместе изучать премудрости ФП. Как я уже говорил в начале поста, основные приемы ФП доступны сегодня в большинстве языков, поэтому полученные знания наверняка окупятся даже в повседневной деятельности по написанию кода
На этом у меня все, если вам понравился этот пост - подписывайтесь на мой блог и совсем скоро мы с вами продолжим совместно изучение функционального программирования