Comments 36
Хорошая статья. Костыли функционального подхода расписаны весьма добротно.
Компилятор, кстати, так и делает — когда он встречаем имя функции, то подставляет вместо него выражение, определённое в её теле.Нет, так он не делает: если он начнет так делать, то любая рекурсия приведет к исполнимому файлу бесконечного размера.
Распараллеливание мы получаем «из коробки», просто потому, что пишем на Haskell.И снова странное утверждение. Не слышал я про распаралеливающие трансляторы Хаскеля. Если бы такое делалось автоматически — зачем был бы нужен оператор `par`?
Haskell запоминает вычисленный однажды результат, и при повторном вызове функции с теми же аргументами не вычисляет его снова, а подставляет ранее вычисленный.
Так он тоже не делает. Кроме того, так как описанная оптимизация не является «чистой» (процесс вычисления функции может идти по-разному в зависимости от окружения, а при первом выполнении окружение изменяется), в «чистом» языке для реализации мемоизации нужны
В этой статье описываются дополнительные способы мемоизации. А вообще, когда вы в каком-то выражении используете «переменную», то она, благодаря ленивой природе языка, не вычисляется сразу, а сохраняется в виде так называемого thunk (отложенное вычисление). А переменная содержит ссылку на этот thunk. Другие переменные с тем же именем, содержат ссылку не на свой отдельный thunk, а на тот же. Когда thunk вычисляется, он заменяется вычисленным значением. А значит, другие переменные, ссылающиеся на него же, не должны вычислять его снова, а берут уже вычисленное значение.
В этом случае речь, скорее, об оптимизации вызовов вроде
Что кажется вполне естественным для «императивного» программиста: вызов факториала написали один раз, отложенные вычисления как-то прокинули этот вызов дальше из своих соображений, но в результате вызов функции всё равно должен получиться один.
Я почему-то из контекста статьи понял, что хаскель будет оптимизировать код такого вида:
Вычисляя factorial 999999 только один раз. А тут, как я понимаю, этого не случится.
factorial 0 = 1
factorial x = x * (factorial (x - 1))
square x = x * x
result = square (factorial 1000000)
Что кажется вполне естественным для «императивного» программиста: вызов факториала написали один раз, отложенные вычисления как-то прокинули этот вызов дальше из своих соображений, но в результате вызов функции всё равно должен получиться один.
Я почему-то из контекста статьи понял, что хаскель будет оптимизировать код такого вида:
factorial 0 = 1
factorial x = x * (factorial (x - 1))
result1 x = (factorial x) * (factorial (x - 1)) * x
result = result1 1000000
Вычисляя factorial 999999 только один раз. А тут, как я понимаю, этого не случится.
Возьмём вот эту строчку, и представим, что
У нас все переменные
P.S.: факториал понятнее и эффективнее выражается следующим уравнением:
x у нас является выражением типа (2 + 3) * 5: result1 x = (factorial x) * (factorial (x - 1)) * x
У нас все переменные
x будут ссылаться на thunk, содержащий это невычисленное выражение. Вычислено оно будет тогда, когда понадобится один из этих x. Как только один из иксов понадобится, выражение (2 + 3) * 5 будет заменено в памяти на 25. А поскольку на этот участок памяти ссылаются все иксы, то они автоматически будут ссылаться уже на 25. P.S.: факториал понятнее и эффективнее выражается следующим уравнением:
fac n = product [1..n] :)
Компилятор, кстати, так и делает — когда он встречаем имя функции, то подставляет вместо него выражение, определённое в её теле.
Нет, так он не делает: если он начнет так делать, то любая рекурсия приведет к исполнимому файлу бесконечного размера.
Работает так не компилятор, а сам код.
Компилятор же формирует код, который именно так и работает.
Substitution model, собственно.
Превосходная статья, большое спасибо!
Вы можете проверить это сами: сколько бы раз вы ни передавали этой функции в качестве аргументов значения 1, 2 и 4, вы всегда в качестве результата получите 7
Никакое количество экспериментов, подтверждающих предположение не доказывает, что это предположение всегда истинно. Миллиард раз вызванная функция
addThreeNumbers с аргументами 1, 2 и 4, которая миллиард раз вернула 7 не означает, что на следующий раз она вернет именно 7.
Спасибо за интересную статью, но хотелось бы больше практического применения. Не понятно как написать всё на чистых функциях, если нужно обращаться к базе данных на сервере, организовывать взаимодействие между пользователями. Очень интересно узнать как это решается на практике на Haskell.
Практическое применение простое, и в основном люди как раз жалуются, что они применяют монады, но не понимают их. Если очень кратко, то все монады можно условно разделить на 2 части.
Первая часть в качестве «чего-то ещё» содержит некоторый маркер, относящийся к «основным» вычислениям — он говорит на об успешности или неуспешности вычислений, о наличии или отсутствии ошибок в вычислении, о том, что у нас может быть 0 результатов или же очень много результатов. Т.е. в этих монадах мы не манипулируем с «чем-то ещё», а просто «смотрим» на него и, в зависимости от его значения, применяем одно или другое уравнение, описываемое оператором
Вторая часть предполагает «более материальное» «что-то ещё», которым мы можем манипулировать напрямую. У всех таких монад есть функции типа
Что касается чистых функций, то вы их просто применяете внутри
Первая часть в качестве «чего-то ещё» содержит некоторый маркер, относящийся к «основным» вычислениям — он говорит на об успешности или неуспешности вычислений, о наличии или отсутствии ошибок в вычислении, о том, что у нас может быть 0 результатов или же очень много результатов. Т.е. в этих монадах мы не манипулируем с «чем-то ещё», а просто «смотрим» на него и, в зависимости от его значения, применяем одно или другое уравнение, описываемое оператором
(>>=). Мы просто пишем код, как будто вычисления успешны (или у нас более нуля результатов вычислений), а неуспешные случаи вычислений обрабатываются автоматически. Грубо говоря, эти монады позволяют нам не писать кучу вложенных if then else и ручных манипуляций с разветвляющимися вычислениями. Вторая часть предполагает «более материальное» «что-то ещё», которым мы можем манипулировать напрямую. У всех таких монад есть функции типа
get и put (а также выводимая из этих функций функция modify). В разных монадах они могут называться по-разному, но суть их одна и та же: вы можете получить текущее значение внешнего окружения (состояния), произвести с ним какие-то манипуляции и заменить текущее значение новым его. В монаде IO, правда, функции get и put размножились, потому что мы можем хотеть получить строку или символ, хэндл, название директории и т.д., но суть их точно такая же. А работа с этими монадами заключается в реализации нужного вам алгоритма в do-блоке, в котором вы композируете эти функции и функции, работающие со значениями ваших основных вычислений, так, как вам нужно. Что касается чистых функций, то вы их просто применяете внутри
do-блока к значениям состояния и «основных» вычислений, которые вы «вытащили» из обёртки. Они производят вычисления, а затем возвращают результат обратно в вашу обёртку (в do-блок, откуда пришли их аргументы). 
1
В статье немало неполных ответов и сознательных упрощений. Если бы не они, получилось бы не статья, а книга, которая никогда бы не вышла по причине нехватки времени на её написание ;)). Я и так эту статью несколько месяцев рожал, пока, наконец, не собрался, и не дописал, выделив на это пару дней практически целиком.
В школе я не любил алгебру, но зато любил геометрию. Поэтому я люблю программировать на лиспе и использую безтиповое лямбда-исчисление как теоретическую основу. Спасибо за проделанную работу, но на мой взгляд эта статья мало отличается от огромного количества туториалов по монадам. До поры до времени текст усваивается хорошо, но потом внезапно ты осознаешь что автор пытается впихнуть в твою голову невпихуемое: у меня просто недостаточно кратковременной памяти чтобы осмыслить эту «простую» концепцию поданную в виде довольно большой алгебраической системы уравнений. Чтобы разобраться в концепции монад нужно как минимум «говорить на языке типов», т.е. основывать свои рассуждения о вычислениях на продвинутых типах хаскелля как базовых мыслительных конструкциях, а дойти до этого не программируя на хаскелле довольно трудно, и опыт программирования на ML этому особо не способствует. Жаль что никто не пытается выразить суть идеи монад в графическом виде, а не в алгебраическом, а то я уж было понадеялся что картинок будет больше после первых двух.
На большее количество картинок меня не хватило, увы. Но я бы посоветовал вам после прочтения этой статьи посмотреть вот эту презентацию: там картинок больше, и они, как говорится, в тему. Может, это позволит вам лучше понять хаскельные абстракции.
Я прочитал презентацию, очень хорошая. Вопрос: вы в своей практике использовали композицию монад, т.е. передачу функций-монадических-композиторов (bind, вроде) в другую функцию как параметр для связывания одной цепочки вычисления разными bind'ами? Если нет, то я подозреваю что монадическую абстракцию в лиспе выгоднее реализовать как синтаксическую, а не функциональную. (Первое что подумалось после прочтения презентации).
Вот в картинках:
http://www.slideshare.net/ScottWlaschin/railway-oriented-programming
http://www.slideshare.net/ScottWlaschin/railway-oriented-programming
Упс, не заметил ссылку на похожие слайды того же автора выше по треду.
Тогда, то же самое, в форме видео:
https://vimeo.com/97344498
Тогда, то же самое, в форме видео:
https://vimeo.com/97344498
По этой ссылке какой-то бред нарисован.
Там сравнивается испорченный постоянными проверками на ошибки императивный код с «чистым функциональным», где все проверки на ошибки вынесены в монады.
Но ведь эти два кода ничуть не эквивалентны! Первый код пытается подобрать как можно более точное сообщение об ошибке — в то время как второй позволяет техническим ошибкам «всплывать» в вызывающий код.
Точно так же в императивном коде можно было бы оставить все как есть, позволив исключениям уходить «наверх» — код был бы красивым и аккуратным. Что же до причины ошибки — ну, по стектрейсу пользователь все поймет :)
Там сравнивается испорченный постоянными проверками на ошибки императивный код с «чистым функциональным», где все проверки на ошибки вынесены в монады.
Две картинки
Но ведь эти два кода ничуть не эквивалентны! Первый код пытается подобрать как можно более точное сообщение об ошибке — в то время как второй позволяет техническим ошибкам «всплывать» в вызывающий код.
Точно так же в императивном коде можно было бы оставить все как есть, позволив исключениям уходить «наверх» — код был бы красивым и аккуратным. Что же до причины ошибки — ну, по стектрейсу пользователь все поймет :)
-Удалил, см. сообщение ниже-
Сначала я тоже был раздосадован этим моментом. В реальных случаях можно определить функцию MapError и передавать ей декоратор ошибки, пришедшей «снизу». Код при этом остаётся монадическим, а ошибки начинают не только пробрасываться, но и получают человекопонятное пояснение.
Что-же до функций validateRequest, canonicalizeEmail и т.д. — если их клеить не с помощью >> а с помощью FlatMap, то они смогут возвращать такие же человекопонятные ошибки, как и императивный код)
Что-же до функций validateRequest, canonicalizeEmail и т.д. — если их клеить не с помощью >> а с помощью FlatMap, то они смогут возвращать такие же человекопонятные ошибки, как и императивный код)
Собственно, механизм исключений — это и есть тот «запасный» путь, фактически та же монада, создаваемая компилятором. Причина ошибки, разумеется, передаётся не в стектрейсе, а в типе исключения. И да, исключения действительно упрощают императивный код, отчего и стали популярными. Однако,
1) в императивном программировании считается моветоном использовать исключения для управления потоком выполнения, т.е. часть некритических ошибок приходится обрабатывать if/return-ами, нарушая единообразие.
2) собственно ошибками дело и ограничивается, т.е. механизм заточен под единственную цель, и нет языковых средств создавать свои монады.
1) в императивном программировании считается моветоном использовать исключения для управления потоком выполнения, т.е. часть некритических ошибок приходится обрабатывать if/return-ами, нарушая единообразие.
2) собственно ошибками дело и ограничивается, т.е. механизм заточен под единственную цель, и нет языковых средств создавать свои монады.
Создать новую монаду в современных императивных языках не сильно-то и сложнее чем в функциональных. Действительно крутая вещь — do-синтаксис из Хаскеля на этих слайдах как раз и не показана (честно говоря, даже не знаю, есть ли что-то похожее в F#)
Тот же пример из слайдов мог бы выглядеть как
Кстати, в том же C# есть аналог do-синтаксиса (linq), только он заточен под монаду List и в других монадах выглядит несколько… странным.
Тот же пример из слайдов мог бы выглядеть как
public Either<string, Error> UpdateCustomerWithErrorHandling() {
return receiveRequest
.Bind(validateRequest)
.Bind(canonicalizeEmail)
.Bind(updateDbFromRequest)
.Bind(sendEmail)
.Bind(returnMessage);
}
Кстати, в том же C# есть аналог do-синтаксиса (linq), только он заточен под монаду List и в других монадах выглядит несколько… странным.
Полный аналог do-синтаксиса хаскеля в F# — computational expressions. Они даже несколько шире, т.к. позволяют вручную определять семантику (возможно, то же можно делать в Haskell).
Именно так у нас в проекте и сделано) Вот тут реализация, кому интересно: Result
Тот же пример из слайдов мог бы выглядеть как
Именно так у нас в проекте и сделано) Вот тут реализация, кому интересно: Result
Любите графическое представление, тогда есть довольно занятное чтиво с картинками http://thedeemon.livejournal.com/67392.html
Хорошая статья! Чем-то перекликается с habrahabr.ru/post/212955
А продолжение скоро?
Планирую выделить время на продолжение после НГ.
Наткнулся на статью в 2019 (спустя 4 года после написания).
Полез в публикации — второй части нет, хотя автор жив и публикуется.
Автор, уточните, после какого именно НГ вы собираетесь продолжить? )
Полез в публикации — второй части нет, хотя автор жив и публикуется.
Автор, уточните, после какого именно НГ вы собираетесь продолжить? )
Автор, присоединяюсь. Очень хочется увидеть продолжение.
Добавил статью в закладки в 2015. Понял только в 2019. Однако :)
Неистово плюсую. Читать было очень интересно.
Sign up to leave a comment.
«Страшные» абстракции Haskell без математики и без кода (почти). Часть I