Дмитрий Сошников — Введение в теорию функционального программирования с примерами на F#

Приветствую вас на завершающем докладе.

Представляю вам с удовольствием Дмитрия Сошникова, которого вы точно все знаете, потому что он давний наш гость и представитель Microsoft долгие годы был, евангелист технологический.

И сегодня он нам расскажет про очень интересную тему, которая нас всех расслабит, успокоит и наведет на полезные мысли.

Манады, да.

Спасибо.

Спасибо большое.

Ну, я действительно давно выступал на .NET, много раз, потому что я действительно работал в Microsoft долгое время и занимался .NET, а потом как-то так вышло, что я перестал заниматься .NET.

Но почему-то меня все равно зовут выступать на .NEXT.

И я каждый раз очень страдаю и думаю, о чем же мне рассказать интересном.

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

Я подумал, что, наверное, будет полезно

вам тоже чуть-чуть послушать про то, на чём основано функциональное программирование.

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

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

Поэтому он в программе называется «Введение».

Я подумал, что это не очень удачное название, поэтому, видите, никто не пришел.

Всем скучно слушать «Введение».

Это уже серьезная конференция.

Поэтому новая версия доклада – это «Математика функционального программирования».

И я попытаюсь...

Семестровый курс, который читаю, уместить в один час, коротко вам рассказать о том, что же стоит за функциональным программированием.

Вот, значит, слайды я потом выложу, у меня есть телеграм-канал, да, вот если вы на меня не подписаны, пожалуйста, feel free сфотографировать, подписаться, я туда выложу слайды.

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

Вот, значит, ну вот если мы думаем про программирование и математику, что приходит в голову?

Вот где вот этот стык?

Где нужна математика для программиста вообще?

Программирование игр, да, кстати, я об этом не подумал, я вообще как-то про игры редко думаю.

Значит, да, там вот очень нужны трехмерные всякие там, да, преобразования объектов, а еще где?

Что приходит в голову первым?

Финансы.

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

И там понятно, что дифференциальные уравнения, они описывают значительное количество процессов в окружающем мире, и компьютеры хорошо их решают.

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

Но это такие сугубо практические вещи, к которым компьютеры прилагаются.

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

И вот над этим начали думать...

соответственно, в середине 20 века, и Тьюринг, Алан Тьюринг придумал машину Тьюринга, известную всем, которая описывает понятие алгоритм.

И...

Но как раз в то время математики думали над неразрешимостью разных логических задач.

Как известно, логика предикатов, что она неразрешима, над этим они думали.

И для этого нужно было какое-то строгое определение того, что такое алгоритм.

И вот наиболее известное определение, которое все изучают в школе, в школе, в институте, это машина Тьюринга.

Вы знаете, да, машину Тьюринга?

Машина Тьюринга с точки зрения математики — это отвратительная математическая модель, правильно?

Потому что машина Тьюринга построена по принципу, как бы Тьюринг вдохновлялся тележкой, вот той, которая на слайде.

Нарисована тележка, которая ездит, читает на ленте какие-то символы и действует соответствующим образом.

Это для человека понятно, это некий простой такой исполнитель.

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

И получается, с точки зрения математики, конструкция некрасивая.

Но почему-то про неё рассказывают в школе.

А вот про, например, другие похожие модели,

Например, лямбдоисчисление, которое Чорч придумал несколькими годами до Тьюринга.

Говорят, мало.

Лямбдоисчисление — это такая очень красивая модель, которая как раз появилась как попытка формализовать математику.

Чтобы формализовать математику, можно пойти по пути логики, но там возникают проблемы разные.

Поэтому Чорч подумал так, что давайте мы будем математикой называть некие условно вычислимые подможества, заведомо вычислимые подможества.

функций.

И Чёрч, он, кстати, как я уже сказал, чуть-чуть до Тьюринга, в 30-е годы придумал это лямбдоисчисление.

Не совсем для программирования, тогда ещё не было компьютеров доступных, чтобы программировать на них.

Первые компьютеры – это 40-е годы.

Но, тем не менее, вот такую модель он придумал.

И на основе этой модели

Оказалось в дальнейшем, что можно строить языки программирования.

Все функциональные языки вдохновлены и построены лямбдоисчислением.

Лямбдоисчисление, наверное, у вас вызывает сразу лямбдовыражения, которые появились во всех языках программирования.

Да, действительно.

Но лямбдовыражение – это только одна из сторон лямбдоисчисления.

Вообще говоря, лямбдоисчисление – это формальное…

аксиоматическая система.

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

Вывод.

И в лямбдоисчислении есть как бы всего две операции.

Значит, одна операция называется... Я что-то здесь перепутал две надписи.

Аппликация абстракция местами.

Не знаю, зачем.

Но так вышло.

Чтобы вас запутать, наверное.

Вот это называется абстракция, а вот это называется аппликация.

Аппликация – это применение условно функции к аргументу.

Есть два каких-то выражения, мы их пишем просто рядом друг с другом.

Ну вот так не принято скобки использовать для вызова функции.

Просто мы пишем fx, это значит применить какую-то функцию к какому-то аргументу.

А вторая операция — это обратная операция, когда мы из выражения делаем функцию.

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

Мы хотим, например, описать идею прибавления к числу единички.

Мы, соответственно, можем написать в математике f от x,

равно x плюс 1, но это как бы неудобно, потому что здесь вот буква f означает идею прибавления к единичке.

Если мы хотим с ней сразу что-то начать делать, ну, первая нотация, которую придумали, было так, писать x плюс 1 с крышечкой.

И типа крышечка означает, что это вот не переменная, которая имеет какое-то значение, а это вот как бы функция по переменной x.

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

Лямбда – это такая крышечка, которая переехала в текст.

И стали писать лямбда икс, точка и какое-то выражение от икс.

И вот эта вот штука обозначает как бы функцию.

Ну, как бы зачем это все нужно?

Вот пример внизу.

Это некое такое выражение –

Но справедливости ради нужно сказать, что есть чистое лямбдоисчисление, где есть только символы лямбда, x, точка и разные переменные.

А есть прикладное, куда добавляют всякие еще вещи типа плюс.

Вот я здесь написал x плюс 1.

Но для понятности, наверное, это удобно использовать, потому что в чистом лямбдоисчислении там менее понятный текст, и я сразу вас не хочу утомлять.

Значит, идея такая, что вот, например, у нас есть такое выражение, λхх плюс 1, примененное к числу 5.

Ну, понятно, что это означает, да, функция, прибавляющая единичку к чему угодно, применяется к числу 5, должно получиться 6.

Значит, как это формально получить?

Мы используем такое правило, ну, понятное правило, что вот если здесь написано λхх плюс 1, и вот это λхх плюс 1 означает функцию, которая...

значит, что-то делает с x, то, чтобы применить это к 5, нужно 5 подставить вместо x. Вот это правило называется бета-редукция, потому что оно укорачивает выражение, упрощает, и в результате мы получаем 5 плюс 1.

А дальше делаем еще какой-нибудь шаг редукции, получаем 6.

Вот что можно делать с помощью лямбда-исчисления.

Можно написать большое-большое выражение и его постепенно упрощать.

Там возникает много интересных моментов, а как его упрощать, а вдруг можно в нескольких местах применить редукцию.

Но об этом сейчас не будем.

Подробнее, если интересно, про чистое прикладное лямбдоисчисление ссылочка есть, и про то, как в чистом лямбдоисчислении определяются числа.

То есть на самом деле на основе чистого лямбдоисчисления, где есть только лямбда, f и разные буковки, можно описать...

как бы ввести понятие «чисел».

Так же, как в классической математике Axiom и Peano вводят числа в логике предикатов, так можно на MD-исчисления определить числа и поверх них уже дальше построить целиком язык программирования.

Но мы будем считать, как будто бы числа у нас есть.

Какое это отношение имеет к программированию?

Вот у нас есть язык F-sharp, например.

Раз мы .NET, мы должны говорить про язык F-sharp.

Язык F-sharp позволяет писать практически на лямбдоисчисления.

Если мы пишем лямбдовыражение функции из x в x плюс 1, применённое к 5, мы получим 6.

Еще в F-sharp можно использовать то, что называется переменная.

Например, написать let incur равно функции от x в x плюс 1 в выражении incur 5.

Это означает, что нужно вот это вот fun x, x плюс 1 подставить сюда вместо слова incur.

А что значит подставить?

Это очень похоже на применение лямбда выражения на бета-редукцию.

То есть, в принципе, любой let может быть заменен просто вот на такую форму.

как бы аппликацию и абстракцию.

То есть let — это такой синтаксический сахар, это на самом деле не переменная, это просто вот другой способ записи такого выражения.

Ну и, например, если мы пишем что-то типа let f от x равно x плюс 1, let t равно 5, f от t. Понятно, что это то же самое, что x плюс 1, тоже тот же самый, запись того же самого, что было раньше, числа 6.

Но вот если мы встречаем такое...

мы можем это транслировать просто в лямбда-выражение большое и дальше его редуцировать, редуцировать, редуцировать.

Это я к чему рассказываю?

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

Он берет большое лямбда-выражение, нашу программу, и дальше его начинает упрощать.

Возникает единственная проблема.

Какая, как вы думаете?

Можно ли все что угодно, что мы обычно пишем в программе, таким образом представить?

Возникает на самом деле проблема с рекурсией.

Понятно, что если мы таким образом что-то пишем и что-то упрощаем, упрощаем, упрощаем, нам мы не можем, раз нет переменных, мы не можем написать цикл.

Принципиально, потому что нет переменных, которые меняют значение.

Вот здесь вот я пытался показать то, что несмотря на то, что я пишу let f от x равно x плюс 1, в конечном итоге-то я все это свожу к одному выражению, где переменных... Ну не то, что нет, но вот есть только эти переменные внутри лямбда выражений.

Переменная, которая что-то помнит, какое-то значение, ее нет.

И получается, что...

Если нет переменных, нет циклов.

Если нет циклов, мы не можем ничего хорошего посчитать.

И поэтому единственный способ сделать цикл было бы использовать рекурсию.

Но в лямбдоисчислении, в том виде, в котором я пока что про него рассказал, непонятно, как использовать рекурсию.

Потому что нет уже имен функций.

Чтобы была рекурсия, нужно имя функции указать.

Поэтому с рекурсией проблема.

Но давайте на секунду от этой проблемы отвлечемся.

Просто посмотрим пример.

Я же обещал введение функционального программирования.

Я покажу...

Пример.

Мы попробуем написать такую задачку.

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

И мы на Паскале тогда писали функция, вычисляющая факториал, функция, вычисляющая x степени n, и функция, вычисляющая ряд Тейлора.

Вот как мы то же самое делали бы на функциональном языке?

Ну, для начала давайте поймем, как мы будем делать циклы.

Например, мы хотим напечатать числа от А до Б, например.

Значит, как нам мы это напишем с помощью рекурсии?

Ну, с помощью рекурсии я сразу скажу, что нужно написать слово «рек», чтобы было понятно, что это рекурсия.

Если мы хотим напечатать числа от А до Б, мы делаем что?

Мы говорим, если А меньше или равно Б, то, значит, печатаем...

printf%d пробел a, печатаем первое число и дальше вызываем рекурсивно print a плюс 1.

Если вам будет очень скучно, пожалуйста, мне об этом скажите.

Я тут простые вещи сейчас пока показываю вначале.

Вот.

Может быть, вам будет скучно.

Издавайте скучающее мычание, если вам скучно.

Так, скучно.

Ладно.

Давайте попробуем, как это будет.

Да, вот я услышу и буду ускоряться.

Ну, значит, само по себе мы цикл какой-то уже научились делать, это хорошо.

Понятно, что печатать числа неинтересно, поэтому интересно что-то вообще такое произвольно другое делать.

Поэтому мы можем описать конструкцию цикла, раз у нас нету встроенного фор, мы можем описать свой фор.

Я его назову «для», потому что «for» — это ключевое слово.

Значит, A, B, и как бы здесь вместо печати я говорю, а что мне делать нужно?

Мне нужно какую-то функцию F просто вызвать на вот этом моем числе A. И получается вот такая функция.

Ой, пардон, я что-то не то сделал.

Да, F от A. И здесь нужно вместо print вызвать «для».

а плюс 1, b, f. И тогда для печати чисел от 1 до 10 я говорю для 1, 10, функция от x, printf, процент d, x. И получаю тот же самый эффект.

Но есть еще...

Смотрите, какая интересная штука.

Функции в функциональном программировании устроены очень интересно.

Предположим, я хочу описать функцию для сложения двух чисел.

Например, let плюс xy равно x плюс y. Как такая функция устроена?

На самом деле, если ее переписать в виде лямбда выражения, здесь будет лямбда x, лямбда y.

И вот эта функция плюс будет складывать мне два числа.

Плюс 1, 2 будет давать 3.

Но как она будет вычисляться?

В лямбдовыражении есть вот эта вот аппликация и абстракция.

Значит, если я пишу плюс 1, 2, то первое, что происходит, я должен применить плюс к единичке.

Если я применяю плюс к единичке, то что получается?

Если я двойку уберу, получается некоторая функция.

которая, наверное, вы догадались, что делает, она прибавляет к чему угодно единичку.

А дальше вот эту функцию, которая получилась, я применяю потом к двойке.

То есть вот любая функция нескольких аргументов, она применяется как бы последовательно ко всем своим аргументам.

Это называется коррирование.

По имени математика Хаскелекари.

Это означает, что я могу любую функцию в функциональном языке, например, у меня есть функция «плюс», которая умеет складывать два числа.

Могу написать вместо «один плюс два» «плюс один два».

Я могу вместо нее написать, например, функцию плюс 1, это будет функция, прибавляющая единичку.

Вот, это, значит, мне в частности позволяет вот эту запись упростить.

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

Красивая.

Беспременно.

Ну и вообще можно разные штуки делать без переменных.

Вот смотрите, например, я хочу вычислить функцию f от x равно 2x плюс 1.

Как мне такую функцию записать без переменных?

Идея вот этой функции, она состоит в чем?

Что мне нужно сначала x умножить на 2, то есть я говорю умножить,

на 2, а потом композиция функций плюс 1.

И вот это вот будет функция f 2x плюс 1.

Но я не призываю вас так писать на практике, конечно, хотя можно было бы так писать, никто потом не понял, что вы написали, и вас бы никогда не уволили.

Но вы сами, что самое обидное, не поймете через неделю.

Поэтому так совсем этим злоупотреблять не надо, но идея в чем?

Смотрите, вот здесь вот это f – это функция, хотя никаких аргументов вроде бы нет.

Это прикольно.

Значит, давайте дальше перейдем к демонстрации.

Значит, вот для того, чтобы писать вот это самое e в степени x, мне по-хорошему нужна функция, вычисляющая factorial, функция, вычисляющая x в степени n и функция, вычисляющая всю сумму.

Я бы мог их, вот если бы я писал на паскрале, я бы эти три функции написал бы как отдельные функции.

И каждый раз писал бы for i от 1 до n и так далее.

А здесь, поскольку мне хочется красиво написать, я могу сделать одну функцию для цикла.

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

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

Но давайте я такую функцию назову итер.

Она будет принимать функцию f, которая показывает операцию, которую нужно делать на каждом шаге цикла.

Начальное значение i и вот эти два границы различных значений a и b. И она будет устроена так, что если a меньше или равно b, то я что делаю?

Я вызываю итер, но в качестве начального значения я передаю f, примененное к...

к i и к a. И в качестве второго начального значения вместо a я делаю a плюс 1 и b. А в противном случае я просто возвращаю вот этот самый аккумулятор.

Давайте я вместо i напишу аккумулятор, чтобы было понятнее.

Аккумулятор.

А здесь у меня начальное значение аккумулятора.

Вот.

Вот эта вот функция, она уже может делать какие-то вещи, типа вычислять сумму чисел от 1 до 100.

Как мне это сделать?

Я скажу итер...

Значит, операция у меня будет плюс на каждом шаге.

Я должен складывать аккумулятор с очередным значением.

Начальное значение 0 и от 1 до 10.

И я должен получить 50-50.

Это сумма чисел от 1 до 100.

А, это до 10, да.

До 100 будет 50-50.

Если, кстати, быстро, то вы тоже издавайте мычание на какое-нибудь другое, что ли, я не знаю.

Вдруг я быстро показываю.

Просто руку поднимаете и говорите «А, мне плохо, я не понимаю».

Значит, можно сказать, что вот это у меня сумма чисел от А до Б. Значит, сумма чисел от А до Б – это итер плюс ноль от А до Б. Ну и, наверное, внимательный служитель уже понял, что я могу А и Б убрать и написать вот так вот.

Сумма – это итер плюс ноль.

Это сумма чисел от А до Б. А как мне сделать факториал?

Факториал n равно итер.

Очевидно, что нужно вместо плюса делать умножение.

Начальное значение единичка.

И от 1 до n. Давайте посмотрим.

Факториал 5.

120.

Ну и опять же, здесь n можно убрать.

Получится факториал.

А как мне сделать сумму x степени n?

Пау n, x n.

Значит, тоже итер.

И мне на каждом шаге от 1 до n нужно умножать число на x. Значит, я говорю, функция, которая принимает аккумулятор и и, я умножаю аккумулятор на x. В качестве этого можно подчерк использовать.

И начальное значение у меня 1.

Я делаю от 1 до n. Соответственно, n отсюда я могу убрать.

Давайте тоже посмотрим по n. 2 восьмой чему будет равно?

2 восьмой 256.

Вроде все правильно.

Вот.

Ну и как бы, собственно, теперь можно сам ряд Тейлора запрограммировать.

Значит, myexp от x. Это будет итер.

Значит, цикл у меня будет, ну, например, там от 0 до 8.

Значит, функция, которая аккумулятор и, аккумулятор плюс, значит, дальше x в степени n, по n x и, да, делить на факториал и. Вот, кажется так.

Давайте посмотрим.

Значит, смотрите, в чем здесь получилась проблема.

Здесь f-шарп по умолчанию думает, что

Все числа у меня... Да, я же не написал начальное значение.

Начальное значение 0 должно быть.

И хочу это повторять от 0 до 8 или до 7, чтобы не переполнился факториал.

Если я так напишу, то все будет хорошо.

Это у меня функция...

из integer в integer, правда, получилось.

То есть, если я напишу, например, myexp 1, должно получиться число e. Число e равно 2.

Ну, в принципе, правильно, да?

Если у нас все integer, то действительно 2.

Но нам не хочется, чтобы integer, нам хочется, чтобы это был floating point.

А что для этого нужно сделать?

Вот здесь мы нигде типа не указывали, вот то, что...

Все эти типы здесь появляются.

Это мне Visual Studio Code подсказывает, какие типы там должны быть.

F-Sharp сам понимает, какие типы должны быть.

Если я, например, скажу 0 с точкой, видите, он поменял на float.

Как бы он понял, что все должно стать float.

Это очень удобно.

Типы писать не надо, а F-Sharp их понимает.

Единственная проблема возникла, что вот factorial, вот эта функция pown, кстати, она может принимать float x, потому что почему бы и нет.

Или не может?

Не может.

Потому что начальное значение здесь единичка.

Мне нужно ее поменять тоже на float.

А factorial мне нужно к float явно привести.

Я примью такой прекрасный оператор в fsharp, который называется конвейер мой оператор, когда я говорю, что я вычислил факт, и результат передам в еще одну функцию, которая будет приведение типов.

Ну и вот теперь у меня должно получиться...

Так, что здесь не так?

Значит, pow n 2 в восьмой.

А, я забыл переопределить функцию, наверное, pow n. Да, вот теперь все получается.

И e в степени 1 получается 2,71.

То есть мы научились вычислять e в степени x. Но это такая была короткая демонстрация на самом деле.

Просто чтобы вы почувствовали, каково оно писать в функциональном стиле.

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

Получилось красивее.

Теперь давайте вернемся к лямбдоисчислению.

Как же все-таки рекурсия-то работает?

Давайте подумаем.

Для этого мы сделаем такую хитрую математическую штуку.

Я написал факториал отдельно, в данном случае без цикла, просто написал факториал.

Значит, это можно переписать таким образом, сказать, что let red factorial равно функции от n, если n равно 1, то 1, иначе n на factorial n минус 1.

Это я просто чуть-чуть переписал все.

А теперь я делаю такую хитрую штуку.

Это уже не код на языке F-sharp, это просто некое такое выражение.

Значит, я говорю, а давайте... Значит, что мне вот в этом предыдущем выражении не нравится?

Мне не нравится, что у меня справа есть слово «факториал».

Вот оно мне мешает, правильно?

Потому что в лямбда-выражении не может быть имя функции, его не должно там быть.

И я делаю такую хитрую штуку.

Я говорю, давайте я не буду писать прямо там слово factorial, давайте я здесь напишу f какой-то, а потом сделаю это абстракцией по f, а потом применю это все к factorial.

Значит, это я сделал эквивалентное преобразование.

То есть на самом деле...

Ну, понимаете, когда я применю к этому бета-преобразование, бета-редукцию, этот факториал заменится сюда вместо f и получится ровным счетом то, что сверху.

То есть это я эквивалентным образом переписал.

Мое утверждение выше.

И что получилось?

Получилось, что у меня такое уравнение, что факториал-функция – это некая функция f, вот эта функция f, примененная к факториалу.

А что это означает?

Если я применяю функцию к чему-то, это что-то не меняется.

В математике такая штука называется неподвижной точкой функции.

Fixed point.

Получается, что я таким образом описываю уравнение.

У меня факториал является решением уравнения для нахождения неподвижной точки функции F'.

И оказывается чудесным образом, что я могу написать на лямбдоисчислении некоторое выражение, которое будет вычислять для произвольного другого выражения неподвижную точку.

Это чудо, на самом деле, как это происходит.

Но я не буду сейчас в это вдаваться в подробности.

Вы, если интересно, посмотрите.

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

Но идея вот в том, что мы теперь можем написать, что факториал – это неподвижная точка функции f большое.

И избежать рекурсии.

И это работает.

Давайте посмотрим.

Я здесь приготовил, правда, пример уже готовый.

Я бы не успел его, наверное, писать с нуля.

Значит, вот.

Это мой пример с факториалом.

Теперь я сначала описываю вот этот оператор, фикс-поинт-оператор.

Фикс-поинт-оператор на f-шарпе, он, конечно, не совсем как лямбда-исчисление описывается каким-то безрекурсивным выражением.

Здесь есть то в рекурсе, но выглядит он почти как определение.

Мы говорим, что фикс f от x – это такое значение, для которого f от фикс f от x. То есть, грубо говоря, применение функции вот этой к f ничего не меняет.

Я могу сделать f от f от x, останется то же самое.

И теперь я могу написать вот так, лет факториал равно фикс от функции f большое.

Если я это сделаю, факториал 5 по-прежнему равен 120.

То есть вот как таковой рекурсии я избавился.

Я свел рекурсию вот в одну эту штуку с надписью фикс.

Да, теперь я могу писать все нерекурсивно.

Ну вот эта маленькая штука, она в данном случае рекурсивна, но в лямбдоисчислении можно выписать ее выражение, которое без рекурсии.

Теперь идем еще чуть-чуть подальше.

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

Можно ли обойтись только одной операцией?

Оказывается, можно обойтись всего одной операцией аппликация.

Если мы введем некоторые базовые функциональные блоки,

Ну, такие строительные блоки, какие-то очень простые функции, которые называются комбинаторами.

Вот комбинатор — это такое как бы лямбда выражения беспеременных.

Вот, например, один комбинатор — это комбинатор k стандартный.

Он вот так описывается.

let kxy равно x. То есть он, например, какое-то число 5 превращает в функцию, которая всегда возвращает 5 вне зависимости от аргумента.

Ну вот такое действие делает.

А есть, например, оператор композиции умный S. Он выглядит так.

Две функции передаются f и g и x. И он сначала применяет функцию g от x, а дальше ко всему этому применяет функцию f от x и от g от x. Это называется как бы вот дистрибьютор, как-то называется дистрибьютор.

Ну и так далее.

Вот функция c, она просто меняет местами аргументы.

Вот есть какая-то функция f от ab, а я хочу поменять местами аргументы.

Ну и еще я заодно оператор if тоже напишу в виде некой такой функции cond.

И она будет так выглядеть.

Если p от x, то f от x, иначе g от x. Вот, предположим, я введу такие простые какие-то комбинаторы.

И как мой факториал преобразится с помощью этих комбинаторов?

Ну...

Вначале, понятно, я просто записываю вместо if вот этот cont.

Здесь мне понадобится комбинатор k, потому что здесь же f от x, а мне нужно для любого x вернуть единичку.

Поэтому k от единички я здесь пишу.

И получается вот такое определение.

А дальше...

Дальше интересно.

Вот мне хочется избавиться от переменных.

Вот здесь вот эта вот функция от f, от cont.

Это вот cont, на самом деле нам кажется, что у него три аргумента, но это же коррированное cont, он постепенно применяет аргументы.

Поэтому я могу заменить вот это выражение на вот такое.

Я могу f перенести дальше, ближе к концу и заменить на композицию.

То есть я говорю cont равно 1k1, композиция вот эта.

Это по-прежнему вычисляет факториал.

Ну и, наконец, еще несколько шагов, я их здесь пропущу.

Я могу как бы свести все вообще к записи без переменных.

И получается, что факториал выглядит вот так.

Это по-прежнему учисляет факториал.

Ну, в чем здесь мораль?

Я, опять же, не призываю вас так писать.

Но видите, что здесь красиво?

Это язык программирования, основанный на математике.

И мы математически понимаем, что мы можем все что угодно вычислить без...

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

И вот этот пример.

Вот они, наши комбинаторы.

И действительно, мы пишем некоторый набор этих комбинаторов, правильно сочлененных вместе, и оно работает, оно вычисляет факториал.

Здесь, кстати, комбинаторов слишком много.

Можно обойтись, в принципе, только двумя.

Базис из двух комбинаторов достаточно, чтобы все что угодно вычислить.

Это как бы мораль...

Подробнее можно почитать про комбинатор неподвижной точки и про комбинаторную логику.

Это аналог лямбда-исчисления без абстракции.

Значит, мораль.

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

И вообще, рассуждая над программой, мы всегда как над некоторой функцией, которая что-то применимает на вход и что-то выдает на выход.

И внутри себя представляет композицию более простых функций.

Значит, идем дальше.

Вот F-Sharp известен своей богатой системой типов.

Но на самом деле в функциональном программировании есть, по сути дела, три основных строительных конструкции для типов.

Первая называется tuple, когда у нас набор разных элементов.

То есть два множества, из них пары значений.

Это очень полезно.

Например, хотим описать книгу.

Можем сказать, что книга описывается автором, названием и годом издания.

То есть string на string на int.

И так называемый второй констроительный блок – это так называемая прямая сумма.

По сути дела это такой юнион, но размеченный юнион.

Discriminated union это называется по-английски.

Например, предположим, мы пишем какую-то работу научную, и у нас в списке литературы может быть либо книга, либо ссылка на интернет-источник.

И вот я говорю, что у меня источник – это либо букт,

и тогда в нее вложен вот этот тип-бук.

Либо URL, и тогда в нее вложена строка с адресом интернет-ресурса.

Вот.

Ну и как бы третий строительный блок – это функции.

Я говорю, например, функция для того, чтобы скачать источник, она принимает на вход источник, а на выход она выдает… Ну, этот источник либо может скачать, если это интернет-ресурсы, тогда она выдает на выходе текст, либо она его не может скачать, тогда она выдает на выходе «none», «не могу скачать».

И вот это специальный опциональный тип, он на самом деле такой же, «discriminated union», только это либо «none», либо как бы «string».

Вот, значит, почему я назвал это алгеброй типов здесь в заголовке?

Потому что вот это умножение, а вот это сложение, это discriminated union, это прямая сумма еще по-русски называется.

Это означает, что, например, если у меня вот это есть тип option t,

то, ну вот это option t, да, он так примерно выглядит, то он в некотором смысле аналогичен, можно написать его как 1 плюс t. То есть вот у меня есть значение типа t, none – это некоторое одно выделенное значение, или значение типа t.

А если у меня есть такой тип string на option int, то есть, например, это книга, в которой год издания может быть неизвестен, то у него будет обозначение b, вот этот тип букв, это будет s string умножить на 1 плюс i.

И вот дальше начинается интересно.

А вот это же выражение s умножить на 1 плюс i. Если взять это как математику, то я могу раскрыть.

Это будет s плюс s умножить на i. А если я запишу тип, который соответствует s плюс s умножить на i, как он будет выглядеть?

Это у меня будет как бы стринг.

Либо string, например, title of string, либо string и год.

То есть я могу сделать discriminated union с двумя вариантами, либо одна строка, либо строка плюс год.

И он идеологически будет эквивалентен предыдущему варианту как раз.

Но он будет чуть-чуть по-другому к нему обращаться, конечно, менее удобно, но...

Идеологически это то же самое, хранится то же самое множество значений.

То есть получается, что с типами работают всякие законы дистрибутивности, привычные нам для сложения и умножения.

Это как бы алгебра в хорошем смысле этого слова.

Если вы знаете слово «алгебра» в математическом понятии,

Дальше ещё интереснее.

Вот есть разные рекурсивные типы.

Например, список.

Список как описывается в функциональных языках?

Это либо пустой список, либо конструктор из элемента типа T плюс ещё один список типа T — хвост.

Значит, если это написать в виде выражения, получится L равно 1 плюс T умножить на L.

А что это вообще такое?

Оказывается, если мы это раскроем, мы же можем написать это как?

l равно 1 плюс t умножить, а дальше 1 плюс t умножить на l. Если мы подставим сюда l каждый раз, получится вот такое бесконечное выражение.

Если мы раскроем скобочки, получится единица плюс t, плюс t умножить на t, плюс t умножить на t умножить на t. То есть вот, что из себя список представляет.

Это либо пустой список, либо один элемент, либо пара элементов, либо тройка элементов.

То есть получится такое эквивалентное представление списков.

Подробнее об этом можно почитать.

На самом деле здесь есть еще совсем интересный момент, связанный с типами.

Вообще говоря...

Вся теория типов очень похожа на некую логику.

Вот этот процесс вывода типов очень похож на логический вывод.

Есть целое семейство языков, которые основаны как раз на этой идее.

Например, такой есть язык КОК.

Он используется для автоматического доказательства, для написания программ, которые автоматически доказываются.

Есть некоторое количество предметных областей, где очень важно, чтобы...

программа была корректна.

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

Есть реальные теоремы, которые доказывали не целиком вручную, а писали, формулировали на языке кок, и дальше доказатель

Доказывал, например, теорему о четырёх красках, о том, что можно раскрасить граф.

Она таким образом доказывалась.

И это соответствие между типами и вычислениями называется изоморфизмом Карри Ховарда.

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

Если интересно, это тоже целое большое направление, очень любопытное.

Иду дальше.

Как теперь можно применить вот эти знания на практике?

Во-первых, язык F-Sharp очень замечательен тем, что в нем вообще популярен так называемый domain-driven development, когда мы берем какую-то предметную область и из этой предметной области быстро начинаем моделировать ее с помощью каких-то структур данных.

Почему?

Потому что есть такая система типов удобная.

Например, мне нужно HTML-документ смоделировать.

Я могу сказать, окей, у меня будет body,

Внутри body будет список элементов.

Значит, дальше элемент может быть либо хедером, либо параграфом, либо табличкой.

А табличка будет состоять из строк, и внутри строк таблички будут отдельные айтемы.

Значит, ну вот видите, такой форматированный документ.

Можно легко, описав несколько типов, с ним начать работать.

Ну а работать, понятно, его можно обойти, преобразовать в HTML, там еще что-то сделать.

А вот теперь представьте себе такую задачу.

Вот нам нужно...

Например, пройтись и вот все цены в долларах преобразовать в рубли, умножив их на 8, на какой-то курс там на 100.

Значит, ну вот для этого...

Нужно как-то обычно писать такую операцию обхода нетривиальную.

А как бы сделать так, чтобы мы могли отделить понятие, как бы сделать такой элемент, который указатель, который будет указывать внутрь этого элемента.

Вот для этого в функциональном программировании придумали специальную абстракцию, которая называется линзы.

Значит, как выглядит линза?

Я покажу пример.

Значит, вот у меня есть этот тип, который описывает документ.

Значит, это либо body, либо collection, либо paragraph и так далее.

Значит, это вот тип, описывающий такой богато отформатированный документ.

И вот пример, который вы видели на слайде.

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

Это значит, у меня есть два действия, getter и setter.

Значит, getter по некоторому элементу типа t возвращает значение типа a, а setter берет на вход некое начальное значение типа t, новое значение типа a, которое я хочу туда вставить, в это место, и возвращает новое значение типа t.

Вот это вот как бы линза, это пара функций.

Тип как бы линза, это пара функций.

И теперь я могу описать некоторые базовые линзы.

Например, линза body, она будет брать на себя документ и из него возвращать body, содержимое.

Но будет устроено очень просто.

Это будет функция, которая будет убирать body вокруг x и возвращать x. Это getter, а setter, чтобы я не передал на вход, я новые body возвращаю.

Вот это как бы линза для body.

Дальше линза для параграфа, линза для таблицы, для строки таблицы.

Еще такая хитрая линза env для n-ного элемента списка.

Значит, чем линзы прекрасны?

Да, ну вот я могу описать операции view и set, которые, собственно, применяют линзу к объекту.

Например, у меня есть список списков, да, 1, 2, 3, 4, 5, 6, и я хочу применить, как бы написать view ns1, то есть n-ный первый элемент списка посмотреть.

Если я это выполняю, я получаю 4, 5, 6.

Вот он мой первый элемент списка.

Если я хочу нулевой элемент списка заменить на 0, например, я говорю set ns0, значит, изменить элемент на 0.

И вот он заменяется на 0.

Но это все как бы само по себе не очень пока интересно.

А интересно то, что мы можем эти линзы...

между собой композировать.

То есть мы можем описать операцию композиции двух линз, вот такая вот точка-стрелочка.

Каким образом?

Если есть две линзы,

соответственно, линза x с двумя функциями xget, xset и линза yget, yset, то я могу построить линзу, например, которая сначала извлекает из x нужный объект, а потом из него извлекает объект уже какой-то еще более внутренний.

Это getter будет так устроен.

А setter будет устроен чуть посложнее, но он как бы сначала извлекает объект из y, потом заменяет его нужную часть.

И получается, что если я определил композицию, например, я могу сказать так, хочу взять сначала первый элемент по строкам, а потом первый элемент уже внутри строки.

И получу число 5 для этой матрицы.

То есть я беру сначала первый элемент, первую строку, потом из него еще раз первый элемент.

Ну и как бы сеттер тоже я могу сделать такой же.

И тогда в документе я могу делать следующее.

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

И получится, что я добрался до вот этой вот первой строки «$2».

Могу ее на что-нибудь заменить.

То есть смотрите, какая интересная абстракция.

Вот эта вот штука, она указывает нужное место внутри документа.

И позволяет мне с этим элементом все что угодно делать.

Ну и, например, я еще могу писать, естественно, апдейт.

Если мне нужно все цены перевести, например, в доллары, то я что буду делать?

Я...

Значит, вот опишу функцию преобразования, но там нужно некие арифметические операции совершить, добавить слово рубль.

Вот, и...

Сама операция будет такая, что вот я беру 0,1, это значит строчка 0 и строчка 1.

И для каждого элемента таблицы применяю соответствующую линзу, и на выходе получается табличка с преобразованными значениями.

Но подробнее, просто у меня времени чуть-чуть уже мало остается.

Я надеюсь, идею вы поняли.

Линзы — это простейший вариант.

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

Это называется оптика.

Все вместе это такая хитрая абстракция, которая, в принципе, кроме функциональных программистов, до нее, по-моему, мало додумался.

Кто в обычных языках?

И эти самые алгебратические типы данных, они позволяют вот такие хитрые конструкции конструировать.

Наконец, переходим к третьим.

У меня из трех больших частей доклад, вот две мы уже прослушали.

Осталась последняя, самая интересная.

Как раз она отсылает нас назад к той песне, которая вначале была про монады.

Я хочу вам рассказать, почему монада –

маноид в категории эндофункторов.

А для этого нужно чуть-чуть рассказать про то, что такое категории.

Вот в математике, оказывается, есть такой замечательный раздел, который называется теория категории.

И он такой как бы очень абстрактный, вообще непонятно, зачем он нужен так на первый взгляд.

Значит, теория категории, как она выглядит?

Значит, мы говорим, что у нас есть такое вот обширное понятие категория, которое состоит из каких-то объектов, неважно каких.

И между объектами есть стрелочки.

которые называются морфизмами.

Но кажется, что это очень на граф похоже.

Граф вершины со стрелочками.

Но у графа между вершинами может быть только одна стрелочка.

А здесь может быть много стрелочек.

И эти стрелочки должны удовлетворять некоторым еще ограничениям.

Например, для любого объекта категории есть стрелочка с названием id, которая в него же указывает.

Это аналог тождественной функции.

А для любых двух стрелочек

есть третья стрелочка, которая называется композицией этих стрелочек.

Вот здесь есть функция стрелочка F и стрелочка G. Значит, можно нарисовать такую стрелочку, которая будет обозначаться композицией F и G. И эта композиция обладает...

Двумя полезными свойствами.

Во-первых, ассоциативностью.

Ну, то есть, как бы, если я делаю F композиция G и потом композиция H, то же самое, что я делаю F композиция G композиция H. Ну, ассоциативность, она почему полезна?

В реальной жизни очень многие операции, они ассоциативны, иначе как бы не бывает.

Поэтому вот от категории требуют такого свойства.

И второе, это то, что единичная функция ничего не меняет.

То есть, если я делаю композицию F с единичной функцией или единичной функцией с F, то получается тоже F.

Но вот это на графике рисуется вот такими диаграммами.

Можно сказать, что вот у меня есть A. Если я применяю и D, A, я получаю тоже A. И потом применяю F. Получится B. Это то же самое, что я сразу применю F вот сюда.

Значит, вот такие диаграммы позволяют понимать, что происходит.

Но вот пока вроде бы все очень абстрактно.

Где это может применяться?

Ну вот, например, у нас есть разные люди, там Вася, Аня, Оля, и стрелочка означает, что они могут помочь.

Что вот Вася может помочь Ане там сделать, например, понять, что такое монады, да, например.

А Аня может помочь Оле.

Что это означает?

Это означает, наверное, что как бы Вася тоже может помочь Оле.

Ну вот, как бы такой жизненный пример.

И есть еще, например, кто-то, кто может помочь всем.

Ну, предположим, это Бог, который способен помочь каждому.

Вот этот объект называется начальным объектом, потому что это объект, из которого исходят стрелочки во все другие объекты, но в него никакие стрелочки не заходят, Богу никто помочь не может.

И точно так же есть терминальный объект, в который входят только стрелочки.

Предположим, это антибог, его можно имбецилом назвать.

Он не может никому помочь, а ему все могут помочь.

Начальный терминальный объект.

Что интересно, вот если мы нарисуем такую категорию, мы можем все стрелочки повернуть в другую сторону.

Правильно?

Все свойства ассоциативности останутся.

Получится другая категория, которая называется двойственной к первой.

Только стрелочка будет означать «не может помочь», а наоборот «может получить помощь от».

И в этом случае как бы начальный объект станет терминальным, терминальный станет начальным, а все стрелочки поменяются.

Почему это важно?

Что можно все свойства доказывать только как бы для одной категории, а дальше они сразу становятся верными для двойственной.

А как это все, какое это вообще отношение имеет к программированию?

Вот в языках программирования категории очень часто обозначают, объекты в категории часто обозначают типы.

Вот, например, есть тип «строка», есть тип «целое число».

И стрелочки — это функция.

То есть, например, есть функция, которая длину строки вычисляет.

Она будет идти из типа «стр» в тип «лен».

Есть функция, которая строку переворачивает, она будет идти из типа str в тип str, вот эта вот функция ref.

Есть функция, которая к целому числу прибавляет единичку, она будет идти из int в int.

Есть функция, которая прибавляет 13, она будет тоже идти из int в int.

То есть бесконечное множество функций будут идти из int в int.

Что в этом случае у нас будет объектами начальными и терминальными?

Начальный объект — это будет объект, из которого стрелочки идут во все другие объекты, то есть функция из него существует, много функций из него в любой объект, но в него ни одной стрелочки нет, то есть не существует функция, которая вернет этот объект.

Вот такая функция, она называется в функциональных языках void, но это не совсем то же самое, что void в C, потому что void в C его можно вернуть, его функции возвращают, которые ничего не возвращают.

А здесь это принципиальный объект, который невозможно вернуть.

Его вообще как бы не существует, но он как бы в теории есть.

А вот объект, который можно вернуть...

Тут, естественно, должна же быть еще вот такая стрелочка.

То есть из любого типа идет стрелочка в этот объект, причем одна.

Вот для терминального объекта должна быть как бы только одна стрелочка в него.

Вот этот тип называется unit.

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

Существует только одна функция из любого типа в unit.

Ну, unit в C-sharp обозначается двумя скобочками такими, значение вот этого типа unit, которое возвращается.

И вот все функции в C-sharp, которые ничего не возвращают, они как раз возвращают unit в явном виде.

Вот.

Значит, к чему это все нам нужно, да?

Вот почему такая очень полезная абстракция?

Вот представим себе, что есть у нас эта самая функция из strvint.

А теперь нам нужно, например, у нас есть список строк, и мы хотим к каждой строке применить эту функцию вычисления длины.

И для этого используется, вы, наверное, знаете, мап.

В языках программирования, во всех в питоне, там есть мап.

Передаем ему функцию и список.

Вот оказывается, мы можем...

Вот эти конструкции.

Можем сказать, что для любого типа, например, для типа str есть понятие список строк.

Для типа int существует тип список int.

И вообще для любого типа существует понятие список этого типа.

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

Вот такая конструкция называется функтором.

Еще пример функтора, кроме списка, это, например, опциональный тип, который, ну вот, помните, либо число, либо none.

Его тоже можно поднять, любую функцию обычную поднять туда.

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

Но для того, чтобы быть функтором, естественно, нужно удовлетворять некоторым свойствам.

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

Вот тогда это будет кошерный функтор хороший.

Ну и мэп от единичной функции должен быть тоже единичной функцией.

То есть если мы применяем мэп к списку, и там функция ничего не меняет, свои элементы, то список тоже не меняется.

Вот.

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

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

То есть функтор — это что-то, где есть мэп.

Зачем это все нужно?

Вот, предположим, у нас есть список источников, например, книга и ссылка.

Я хочу, например, взять эти все источники, скачать их и суммаризировать с помощью ChatGPT.

Как мне это можно сделать?

Я, например, могу сказать, что я сначала применяю мэп, который...

Из URL он извлекает адрес и делает опциональный адрес.

А если это book, она заменяет его на num, потому что книгу нельзя скачать.

Вот эта функция justURL делает это.

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

Идет на сайт и скачивает.

В этом случае я делаю сначала list.map, чтобы каждому элементу применить эту операцию, но каждый элемент у меня опциональный тип, поэтому я делаю еще один вот этот вот fmap для опционального типа и скачиваю значение.

Дальше я делаю конкатенацию всего и суммаризацию с помощью chartGPT.

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

Например, скачать.

Значит, как бы я нам протаскиваю через всю операцию.

Ну и благодаря свойству функторов я еще могу здесь упростить вот эту вот запись.

Поскольку два мапа, идущих подряд, композиция двух мапов то же самое, что мапа от композиции.

Это свойство функторов, поэтому я могу все чуть-чуть упростить.

Вот такая интересная абстракция.

То есть здесь идея какая, что вот у меня есть исходные как бы базовые значения, это строки, адреса сайтов и содержимое сайтов.

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

Но на практике обычно бывает как, что... Ну, если я, например, хочу там скачивать сайт, то я обычно знаю его адрес.

Но на выходе может получиться либо ошибка, либо не ошибка.

Для этого случая обычно используется такая более...

Ну, другая конструкция, которая называется monad.

Вот, например, предположим, наша функция http, мы ее определили так, что она учится отлавливать ошибки.

То есть, например, мы ей передаем наш адрес сайта, и она возвращает либо none, если не удалось скачать, либо строку.

В этом случае, ну вот наша функция http.

А предположим, дальше я хочу суммаризировать только те тексты, в которых входит слово функциональное программирование.

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

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

Вот в этот вот хитрый тип функторный.

Монадический я даже буду его здесь называть.

И вот на практике я хочу вот эти функции научиться объединять в цепочке.

Но вот для этого существует специальная операция, которая называется bind.

И bind устроена как?

Она берет вот такое вот хитрое упакованное значение и строит его композицию с такой вот неупакованной функцией.

Ну и в данном случае, значит, вот есть у меня...

Книжки и какие-то адреса.

Я для каждого элемента сначала преобразую его в строку, потом применяю HTTP, потом применяю grep, и на выходе конкатинирую и получаю ответ.

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

Я вам, естественно, могу то же самое написать обычным циклом.

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

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

Поэтому получается все сильно проще.

Еще один пример про монады.

Типичный пример монад, как они появились в F-Sharp, например, такой самый часто используемый пример, это асинхронные вычисления.

Как устроены асинхронные вычисления?

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

То есть у меня, получается, есть вот эта функция скачивания F,

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

То есть вот в этих синхронных вычислениях есть как бы три таких возможных изветвления.

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

Значит, каждая операция у меня выглядит вот так.

Я получаю некий тип A, применяю функцию F, она возвращает мне вот этот обогащенный тип с тремя хендлерами.

Дальше, чтобы записать, мне же уже не хочется вникать в детали, что делать с канцелом.

У меня, опять же, есть функция, которая принимает уже правильные значения.

И если первая операция завершилась успешно, то она как бы...

выполняет следующую в цепочке.

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

Это еще раз я просто повторяю, что делает функция bind.

И вообще, чтобы определить монаду, есть две функции, которые в ней есть.

Есть функция return, которая берет обычное значение, поднимает его до этого монадического типа, и bind принимает на вход монадический тип и функцию.

И вот если она эту функцию может выполнить, она ее выполняет и возвращает монадический результат m от b.

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

А красивые свойства, да, да, еще прежде чем об этом говорить, вот покажу пример просто, да, как это все красиво пишется на F-sharp.

Предположим, я хочу скачать из интернета изображения, их как бы заресайзить и куда-то записать на диск.

Вот в этом случае я могу написать такой код.

Вот у меня есть список адресов.

Я для каждого списка строю асинхронное выражение.

Это вот как бы монадическое как раз выражение.

И в двух местах у меня здесь используется операция bind.

Вот там, где восклицательный знак, что она означает?

Вот, предположим, HTTP async — это как раз операция такого скачивания асинхронного.

Она возвращает асинхронное значение.

Вот из трех этих штук, да?

Но когда я пишу let восклицательный знак, оно распаковывается в обычное значение и применяется как бы здесь неявная операция bind.

Мы ее не видим, она применяется.

И на самом деле вот что здесь происходит?

Когда завершается скачивание, вызывается весь остаток этого кода.

Но вот так вот красиво в F-Sharp можно упаковать в обычную почти что запись, на самом деле достаточно сложную логику.

Ну и то же самое вот этот do-восклицательный знак save, здесь еще как бы один такой невидимый баинт.

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

Есть fish operator g. Он что делает?

Он строит просто композицию двух функций.

То есть он берет одну такую функцию f, которая из обычного типа в монадический, вторую функцию g, которая из обычного типа в монадический.

Первая функция из a в m от b, вторая из b в m от c, и строит из них композицию из a в m от c. Очень логично и красиво.

И какими свойствами этот оператор должен обладать?

Понятно, что операция return, которая...

поднимает обычное значение x до монадического типа.

Если я ее строю, вот композицию с f, получается f. Правильно?

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

Если я сначала делаю f...

вот эта вот хитрая композиция g, композиция h, то это то же самое, что я сначала g и h склеиваю вместе, а потом приклеиваю к ним f. И вот на что это похоже, вот эти вот три правила?

Они похожи, ну, например, ой, простите, они похожи, например, на правила в арифметике.

0 плюс x равно x, x плюс 0 равно x, и a плюс b плюс c равно a плюс b плюс c. Вот такая конструкция в математике, которая...

представляет собой одну операцию, типа плюс единичный элемент, который ноль, и операция ассоциативная, вот эта штука называется маноидом.

Ну, просто вот так называется.

Маноиды бывают, вот это вот маноид для сложения, если мы возьмем умножение с единичным элементом единицы, получится точно такой же маноид для умножения.

И вот здесь мы видим то же самое.

Есть единичный элемент, это функция return, и есть ассоциативная операция, это стрелка Клейсли.

И, по сути дела, это вот моноид, но оперирует он как бы в категории эндофункторов.

То есть вот этих функторов, которые... Ну, функторов, которые описываются монадическим типом.

Вот поэтому как бы и говорят, что монада — это моноид в категории эндофункторов.

То есть на самом деле вот свойства вот эти, они как бы представляют собой свойства моноида.

Вот, подробнее.

Вообще теория категории очень полезная...

такое вот изменение сознания способно принести.

Поэтому есть хороший такой набор текстов, который называется «Теория категории для программистов».

Некто Барта Шмелевский написал такую серию статей, она прямо из трех больших частей состоит, там, по-моему, порядка 30 статей.

Есть первые, там, шесть из них переведены на русский язык на Хаббре, а остальные на английском.

Поэтому здесь ссылка и на русский, и на английский.

Вот я очень рекомендую их почитать, и там...

Ну вот мне это не очень как расстраивается, что он примеры приводит еще и на обычных языках, там типа то ли C-sharp, то ли Java.

Но для вообще нормальных людей, наверное, это скорее плюс, чем минус.

То есть он говорит, а как это вообще, почему это полезно, почему думать в таких терминах полезно.

Я, к сожалению, не смог это донести достаточно быстро до вас.

Я думаю, ну тут таким галопом мне по всему пришлось пройтись.

Но я очень надеюсь, что это было полезно.

И в целом функциональное программирование позволяет по-другому смотреть на предметные области.

Нам не нужен объектно-ориентированный подход.

Очень часто проще без него.

Потому что представьте себе, мы захотели бы эту идею с монадами сделать объектно-ориентированной, с асинхронностью.

Нам пришлось бы, например, в C-Sharp, в нем же не сделали ничего, чтобы внедрить туда асинхроны.

Сделали отдельное ключевое слово async на уровне языка.

Пришлось менять стандарты языка.

А в F-Sharp ничего делать не пришлось.

Там уже была конструкция monad, и этот async добавили просто как элемент библиотеки.

Вот.

Поэтому если бы мы захотели асинхронность нормально реализовать на библиотеке классов, мы бы, ну, плохо было бы.

Нам пришлось бы дописывать класс для этого асинхронного значения с разными полями, функция там .compose.

Ну, в принципе, конечно, как бы не так плохо все выглядело бы на выходе.

Написать несколько раз .compose, .compose, .compose.

Но намного вот лучше так думать изначально.

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

Использовать их можно как бы и на обычных языках, но, конечно, лучше всего для развития мозга, да, вот есть такая книжка «Изучите Хаскель во имя добра», поэтому изучите Хаскель во имя добра, и будет вам счастье.

F-Sharp тоже очень хороший язык, но как бы он в меньшей степени сломает мозг, чем Хаскель.

Вот, на этом я, наверное, заканчиваю.

У нас, по-моему, не осталось времени на вопросы.

Но зато у нас есть дискуссионная зона, где вопросы можно позадавать.

И ссылка на мой телеграм-канал, где тоже можно вопросы позадавать.

Да, спасибо большое.

Спасибо.

Размяли мозг.

Я хочу сейчас всем объявить.

Сейчас в дискуссионной зоне можно будет Дмитрию задать любые вопросы, которые вас интересуют.

Также у нас в 18.40 будет закрытие, которое по желанию вы можете посетить.

Но если у вас есть вопросы, то, конечно, можете остаться в дискуссионной зоне.

Спасибо.

Спасибо.