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

Всем привет. Недавно я заинтересовался проектом Академия и решил принять в нем участие. В качестве материала, о котором я буду рассказывать своим читателям, я решил выбрать курс от 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 - нас интересует лишь полученный результат. Таким образом, комбинируя присваивания мы пишем код в императивном стиле, то есть, указываем каждый шаг, ведущий нас к результату.

А теперь присмотримся ко второму примеру. Если разобрать его дословно, то мы делаем следующее:

1. Мы говорим: "мне нужна последовательность чисел от одного до десяти", вызывая функцию  range с аргументами 1 и 10
2. Мы говорим: "мне нужна сумма всех элементов этой последовательности", передавая результат 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 пока не будет достигнут базовый случай

Выводы и мое впечатление

На этом заканчивается первая неделя курса. На мой взгляд, курс получается довольно удачным как с точки зрения содержания, так и с точки зрения организации. Кому-то изложение может показаться слишком теоретизированым, однако, смею вас уверить, что уже со второй недели начинается собственно работа с кодом. Забегая вперед скажу, что к материалу лекций добавится также множество самостоятельных заданий, довольно простых, но в то же время полезных для понимаий концепций ФП. 

Что я мог бы посоветовать сообществу Голоса после изложения первой недели? Разумеется, присоединяться к проекту и вместе изучать премудрости ФП.  Как я уже говорил в начале поста, основные приемы ФП доступны сегодня в большинстве языков, поэтому полученные знания наверняка окупятся даже в повседневной деятельности по написанию кода

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