Через тернии к Haskell (перевод). 2/2

Поздравляю! Вы добрались реально далеко. А теперь начнется треш, угар и содомия :).

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

• Что делать с побочными эффектами?
• Зачем понадобился такой странный синтаксис для работы с вводом-выводом (IO)?

Готовьтесь, ответы могут быть не самыми простыми. Но польза от них будет несомненна.

Типичная функция, работающая с IO выглядит практически как императивная программа:

• Для присвоения значения объекту мы используем <- .
• В этом примере типом выражения в каждой строке является IO * ;
  • action1 :: IO b
  • action2 x :: IO ()
  • action3 :: IO c
  • action4 x y :: IO a
  • x :: b , y :: c

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

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

  Что мы хотим получить?

  Поведение этой программы должно быть очевидно. Но давайте пристально посмотрим на типы.

  Вы заметили, что каждое выражение в блоке do имеет тип IO a ?

  Также обратите внимание на поведение символа <- .

  Если something :: IO a , то x :: a .

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

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

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

  Арррггхххх! Дьявольское сообщение об ошибке и падение программы! Тогда первым шагом нам надо сделать так, чтобы сообщение об ошибке было легко читаемо.

  Для того, чтобы это сделать, мы должны понять что что-то пошло не так. Один из способов — использовать тип Maybe . Этот тип очень часто используется в программах на Haskell.

  Что это за штука? Maybe это тип, принимающий один параметр. Вот его определение:

  Это хороший способ понять, произошла ли ошибка при попытке создания\вычисления значения. Функция maybeRead — прекрасный пример подобного подхода. Эта функция похожа на функцию read (что очень похоже на javascript функцию eval , которая обрабатывает JSON-строку.), но если что-то пойдет не так, результатом будет Nothing . А если результат будет правильным, она возвратит Just <значение> . Не пытайтесь глубоко вникнуть в эту функцию. Код в ней более низкого уровня чем использует read ; .

  Теперь, когда код стал более читаемым, напишем функцию, которая делает следующее: если строка пришла в неверном формате, она вернет Nothing . В остальных случаях, например для “1,2,3”, она вернет Just [1,2,3] .

  А теперь протестируем наш код используя функцию main.

  В случае ошибки, мы показываем симпатичное сообщение об ошибке.

  При этом тип каждого выражения в do-блоке функции main остается в виде IO a . Единственная странная вещь — это error . Функция error msg просто принимает на вход любой тип ( IO () в нашем случае).

  Обратите внимание на очень важную вещь — типы всех функций определены заранее. Существует только одна функция, с типом IO и это: main . Это значит, что main не является чистой функцией. Но она использует чистую функцию getListFromString . Просто глядя на объявленные типы функций мы можем отличить чистые функции от функций с побочными эффектами.

  Почему важны чистые функции? Я могу забыть некоторые вещи, но вот три основных причины:

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

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

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

  Первая часть останется без изменений:

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

  Тип этой функции IO [Integer] . Это значит, что мы получили результат типа [Integer] используя IO действия. Некоторые люди объясняют это так:

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

  В итоге, наша функция main получилась гораздо проще:

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

  • в блоке do каждое выражение должно иметь тип IO a . У вас есть достаточно ограниченный набор возможных выражений: getLine , print , putStrLn , и т.п.
  • Постарайтесь по максимуму использовать чистые функции.
  • тип IO a означает следующее — IO действие, которое возвращает результат типа a . IO тип для представления действий, а IO a — это тип функции. Если вам все еще интересно — читайте следующий раздел.

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

  • Напишите программу, которая суммирует все свои аргументы. Подсказка: воспользуйтесь функцией getArgs .
  Объяснение трюка с IO

  Чтобы отличать чистые функции, main определена как функция, которая меняет состояние мира

  Функции с этим типом гарантированно будут иметь побочные эффекты. Посмотрите на типичную main-функцию:

  В этом примере много временных значений ( w1 , w2 и w3 ) которые используются для передачи данных следующему действию.

  Мы пишем функцию bind или (>>=) . Благодаря bind нам больше не понадобятся именованные временные значения.

  Бонус: Haskell припас для нас синтаксический сахар:

  Зачем нужен такой странный синтаксис, и что из себя представляет тип IO ? Пока все это выглядит как какая-то магия.

  Забудем на некоторое время о чистых функциях. Сконцентрируемся на побочных эффектах:

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

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

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

  В Haskell-е состояние мира задается явно. Мы четко говорим, что функция main потенциально может изменить состояние мира. И ее тип будет выглядеть примерно так:

  Но эта переменная доступна не всем функциям. Функции, работающие с этой переменной не чистые. Функции, которые не используют ее — являются чистыми(Из этого правила есть опасные исключения. Но в реальных программах оно вам не понадобится. Разве что в случае глубокой отладки).

  Haskell считает, что мир — это входной параметр функции main . Но реальный тип этой функции больше похож на

  (Для тех, кому интересно, тип выражения — data IO a = IO (# State# RealWorld, a #)> . Все # связаны с оптимизацией, и в примере я поменял местами несколько полей. Но в целом, идея не поменялась.)

  Тип () — это пустой тип. Пустота.

  Давайте перепишем нашу функцию, не забывая о :

  Во-первых, все функции с побочными эффектами должны иметь определенный тип:

  Где a — тип результата. Например, функция getChar должна иметь тип World -> (Char,World) .

  Другая неочевидная вещь — порядок вычисления функций. В Haskell, если вы попытаетесь вычислить f a b , у вас будет несколько вариантов:

  • вычислить a , потом b потом f a b
  • сначала вычислить b , потом a и в завершение f a b .
  • параллельно вычислить a и b , а затем f a b

  Поскольку язык функционально чистый — такие фокусы реальны.

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

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

  • напечатать что-то на экране
  • изменить идентификатор мира
  • вернуть в качестве результата ((),новый_идентификатор_мира) .

  Теперь main выглядит просто ужасно. Давайте проделаем то же самое с функцией askUser :

  Похоже, но уродливо. Вы только посмотрите на эти корявые переменные w* .

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

  К счастью, есть более прямой подход к решению этой проблемы. Мы видим паттерн. Каждая строка представлена как:

  Даже если первый параметр x не нужен, результатом будет пара (answer, newWorldValue) . Каждая функция f должна иметь тип, похожий на:

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

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

  Например, мы могли бы написать:

  И, естественно, actionN w :: (World) -> (a,World) .

  ВАЖНО! есть только два паттерна, на которые стоит обратить внимание:

  А теперь будет небольшой фокус. Мы заставим “исчезнуть” переменную, хранящую состояние мира. Мы свяжем ( bind ) две строки. Для этого напишем функцию bind . Ее тип поначалу выглядит странным:

  Не забывайте о том, что (World -> (a,World)) это тип для IO действия. Давайте для простоты его переименуем:

  getLine это IO действие, которое получает мир в качестве параметра и возвращает пару (String,World) . Можно сказать, типом getLine будет IO String . Также мы можем ее воспринимать как IO действие, которое вернет нам String “заключенную внутрь IO” .

  Функция print тоже достаточно интересна. Она принимает на вход параметр, который потом отобразит. Но на самом деле она принимает два параметра. Первым параметром идет значение, которое будет отображаться, вторым — состояние мира. В качестве результата она возвращает пару ((),World) . То есть она изменяет состояние мира, но не возвращает каких-либо данных.

  Этот тип позволит упростить нам определение типа для функции bind :

  bind принимает 2 IO действия в качестве аргументов и возвращает еще одно IO действие.

  Теперь освежим в памяти важные паттерны. Первый был таким:

  Обратите внимание на типы:

  Выглядит знакомо, не правда ли?

  Основная идея заключается в том, чтобы спрятать параметр World при помощи этой функции. Поехали! Вот приблизительно то, что мы хотим получить:

  А теперь, задействуем функцию bind :

  Поскольку print имеет тип (World -> ((),World)) , мы знаем, что res = () (null type). Если вы не видите здесь особой уличной магии, попробуем написать программу из трех строк.

  Что аналогично следующему:

  А теперь заметили? Да, больше никаких временных переменных World! Это МА.ГИ.Я

  Но мы можем воспользоваться другим синтаксисом. Давайте заменим bind на (>>=) . (>>=) это инфиксная функция, такая же, как (+) ; напоминаю 3 + 4 ⇔ (+) 3 4

  Хо хо хо! Всех с новым годом! Haskell припас для нас синтаксический сахар:

  Можно заменить на:

  Вы можете использовать x в action2 и x с y в action3 .

  Но что насчет строк, которые не используют <- ? Легко! У нас есть функция blindBind :

  Я специально не упрощал это выражение. Конечно, если мы хотим сделать код проще, мы можем использовать оператор (>>) .

  И таким образом

  Кстати, вот еще одна достаточно полезная функция:

  Это стандартный способ запихивать чистые значения в “IO контекст”. Обычно putInIO называют return . Такое название функции очень путает при изучении Haskell-а. return очень отличается от аналогов в других языках.

  Напоследок, давайте перепишем наш пример:

  Можно переписать как:

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

  А теперь, давайте представим, как бы все это выглядело без (>>) и (>>=) .

  Монады

  А теперь раскроем секретный секрет: IO — это монада. Использование монады значит, что вы можете использовать синтаксический сахар do нотации. Но самое главное — это паттерн проектирования, который позволит писать более чистый и понятный код.

  • Монады не обязательно связаны с побочными эффектами! Существует множество чистых монад.
  • Суть монад — в композиции вычислений

  В терминах языка Haskell — Monad это класс типов. Чтобы стать экземпляром этого класса, вам необходимо определить функции (>>=) и return . Функция (>>) будет создана автоматически на основе (>>=) . Вот (почти полное)определение класса Monad :

  • ключевое слово class это не то, что вы думаете. Класс в Haskell это не класс из ООП. Класс в Haskell больше похож на интерфейс в Java или C#. Лучше было бы его назвать typeclass . Что значит множество классов. Чтобы тип мог принадлежать этому классу, тип должен реализовать все функции класса.
  • В данном конкретном случае тип m должен быть типом, который может принимать аргумент. например IO a , а также Maybe a , [a] , и т.д.
  • Чтобы быть полезной монадой, ваша функция должна соблюдать некоторые законы. Если ваша функция будет нарушать эти законы, будут происходить странные вещи:

  Maybe — это монада

  Существует много типов, которые являются экземпляром Monad . Самый простой пример — Maybe . Если у вас есть набор Maybe значений, вы можете воспользоваться монадами для работы с ними. В частности это может быть полезно, чтобы избавиться от вложенных if..then..else.. .

  Представьте себе сложную банковскую операцию вы можете претендовать на бонус 700€ только если у вас есть история операций без ухода в минус.

  А теперь наведем порядок в этом коде используя Maybe и ее Monad-ическую сущность:

  Уже неплохо, но можно сделать еще лучше:

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

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

  Можете переписать этот код, используя определение (>>=) для Maybe :

  Монада Maybe доказала свою полезность даже в таком маленьком примере. Мы также видели использование монады IO . Но есть и более интересный пример — списки.

  Монада списков

  Монада списка позволяет нам моделировать недетерминированные вычисления. Например:

  Для монады списка тоже есть синтаксический сахар:

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

  • IO,
  • недетерминированных вычислений,
  • генерации псевдослучайных чисел,
  • хранения конфигурации,
  • работы с состояниями,
  • …

  Если вы вы добрались до этого места, мои поздравления! Теперь и вы знаете кунг-фу монады! (Конечно, вам понадобится практика чтобы к ним привыкнуть. Напишите парочку своих. Но вы уже сделали огромный шаг в этом направлении)

  Приложение

  Этот раздел не относится напрямую к изучению Haskell. Мы просто уделим большее внимание некоторым деталям.

  Еще кое-что по поводу бесконечных деревьев

  В разделеБесконечные структуры мы разобрали пару простых бесконечных структур. К сожалению, наше дерево лишилось двух свойств:

  1. отсутствие дубликатов в узлах дерева
  2. упорядоченное дерево

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

  Для начала давайте создадим список из набора псевдослучайных чисел:

  Чтобы освежить память, продублируем реализацию treeFromList

  Посмотрим на результат:

  Ура! Заработало! Но оно будет работать только в том случае, если вам есть что добавить в ветку.

  будет выполняться бесконечно. Это происходит потому, что код пытается получить голову выражения filter (<1) [2..] . Но filter не настолько умен, чтобы понять, что результатом выражения будет пустой список.

  Тем не менее это хороший пример того, что могут делать нестрогие программы.

  Упражнение для читателя:

  • Докажите существование такого числа n , что treeTakeDepth n (treeFromList shuffle) упадет в бесконечный цикл.
  • Найдите верхнюю границу для n .
  • Докажите, что не существует такого shuffle списка, выполняя который, программа завершится.

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

  Первая проблема — нехватка случайных числе в нашей реализации shuffle . Мы сгенерировали только 4331 различных чисел. Улучшим нашу функцию shuffle .

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

  Строго говоря, мы не можем сказать, пустой ли список filter (<x) xs . Чтобы решить эту проблему, я немного поломаю нашу реализацию двоичного дерева. В новой реализации для некоторых узлов не будет выполняться следующее условие:

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

  В новой версии treeFromList мы просто заменили filter на safefilter .

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

  Запустим же программу и возрадуемся:

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

  Даже если увеличить глубину поиска с 8 до 100 , функция будет работать, и при этом не сожрет всю оперативную память!

  Упражнение для читателя:

  • Даже для больших значений deep и nbTry , функция работает нормально.Но в самом худшем случае нас может ожидать экспоненциальный рост. Найдите наихудший возможный вариант списка для treeFromList . подсказка: подумайте о ( [0,-1,-1. -1,1,-1. -1,1. ] ).
  • Сначала я пытался реализовать safefilter следующим образом:

  Благодарности (от автора, не переводчика)

  Спасибо /r/haskell и /r/programming . Ваши комментарии неоценимы.

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

  📎📎📎📎📎📎📎📎📎📎