20090918

(Новичковые) ужасы Хаскеля

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

1. Ламбда-функции


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


Вообще-то, именно поэтому я и выучил Хаскель. Мне было просто любопытно, что означают все эти лямбды. Очень помогла в самом начале статья Пола Худака Conception, evolution, and application of functional programming languages (PDF также здесь). Возможно, есть введения и получше, но я начинал с него.

Ламбда-выражение — самая суть «функций» — это выражение вида
\lambda x \;.\; \text{expression with $x$}
Значением этого выражения является пока ещё безымянная функция одного аргумента (x), что-то с ним вычисляющая (а именно, выражение справа от точки). С лямбда-функциями связана серьёзная математическая теория, но с точки зрения программирования можно считать \lambda ключевым словом для определения функций. Действительно, когда я и до этого уже пользовался лямбдами в Питоне (и почти во всех других современных языках они тоже есть). В Питоне они выглядят вот так:
lambda x: expression with x
Ими было очень удобно пользоваться в filter() и reduce(). И вообще, почти везде, где в качестве аргумента требуется имя функции. Однако у лямбда-функций нет имён, и именно поэтому их ещё называют анонимными (безымянными) функциями. В пайтоне иногда я давал им имена прямо на лету:
add_42 = lambda x: x + 42
Теперь имя add_42 указывает на функцию. Точно такой же результат можно было получить, записав определение функции как обычно:
def add_42(x):
return x+42
А что же насчёт Хаскеля? Да почти то же самое. Символ \ заменяет \lambda, -> служит вместо точки. Всё вместе записывается так:
\x -> выражение с x
И мы даже можем давать имена таким безымянным функциям, так же как и в Питоне:
add_42 = \x -> x + 42
Согласитесь, очень похоже.

Однако тут есть одна тонкость. Как только я начал читать о Хаскеле, я увидел лямбда-выражения, которые поначалу казались немного странными:
\x -> \y -> выражение с x и y
Что означают все эти «стрелочки»? Ответ оказался очень прост и очень полезен в дальнейшем освоении языка.

В Хаскеле все функции являются функциями одного аргумента. Поначалу это может показаться ограничением, но на деле это очень удобная и практичная идея. Любую функцию n аргументов можно представить как функцию одного аргумента, возвращающую другую функцию n–1 аргементов. И по науке это азывается каррированием. Эта идея, в частности, позволяет передавать функции только часть аргументов.

Узнав об этом, мы теперь можем читать любые выражение с множеством «стрелок»:
\x -> (\y -> выражение с x и y)
Значением такого выражения будет фукнция, берущая один аргумент и производящая другую функцию, которая берёт ещё один аргумент. Такое выражение в целом ведёт себя как функция двух аргументов. Например, мы можем вычислить такую функцию двух аргументов в интерпретаторе Хаскеля ghci:
ghci> (\x -> \y -> x + y ) 3 4
7
Конечно, есть более краткий способ записи функций двух аргументов (обратите внимание, что список аргументов брать в скобки совсем не нужно):
ghci> (\x y -> x + y) 3 4
7
Однако знать, что на самом деле все функции нескольких аргументов являются функциями одного аргумента очень полезно. Например, это помогает читать описания типов функций. Например, тип функции map выглядит так:
map :: (a -> b) -> [a] -> [b]
Я обычно читаю это следующим образом: «функция map принимает два аргумента, первый — функцию преобразующую a в b, второй — список элементов типа a, а возвращает список элементов типа b». Но иногда гораздо естественнее записать тот же самый тип так:
map :: (a -> b) -> ([a] -> [b])
«Функция, которая берёт функцию, преобразующую a в b, и возвращает функцию, преобразующую список a в список b».

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

2. Знак равенства


— Ну что, если тут нет смысла, — сказал Король, — тогда у нас гора с плеч: нам незачем пытаться его найти! Сэкономим кучу работы! И все же...


По-моему, знак равенства (=) — самый важный символ в Хаскеле. Понять его важно для понимания языка. И мне кажется, смысл равенства недостаточно подчёркивается во всевозможных учебниках. Например, это единственное ключевое слово, отсутствующее в списке ключевых слов Хаскеля в его вики.

В отличии от большинства императивных языков, где = означает присваивание (то есть действие), в Хаскеле он означает, что левая часть равна правой (то есть описывает свойство).

Дополнение: в комментариях уточняют, «равно» в Хаскеле — связывание имени слева с определением справа.


«Равна» — не значит «становится». Это означает, что нечто равно чему-то ещё. Всегда. Как в математике. a = b в Хаскеле означает, что a равно b по определению, a эквивалентно b.

Таким образом, = в Хаскеле служит для записи определений. «Равно» может определять самые разные вещи, но определяет их статично. Оно не зависит от порядка выполнения операций. На него можно положиться.

Пользователям функциональных языком это покажется слишком уж очевидным, но именно в смысле знака равенства самое важное изменение для тех, кто раньше пользовался императивными языками. Теперь, кстати, мы можем давать имена нашим безымянным функциям:
add = \x -> \y -> x + y
Признаю, что читается это плохо, поэтому в большинстве случаев функции в Хаскеле определяются так:
add x y = x + y
Но и это по-прежнему определение функции add.

3. Классы типов


Significant benefits arise from sharing a common type system, a common toolset, and so forth. These technical advantages translate into important practical benefits such as enabling groups with moderately differing needs to share a language rather than having to apply a number of specialized languages. — приписывается Б. Страуструпу


Система типов в Хаскеле просто прекрасна. В ней очень легко и естественно выражаются многие идеи. И возможно, именно классы типов — это наименее чуждая концепция для тех, кто приходит в Хаскель из процедурного и объектно-ориентированного мира. Во всяком случае, мне так показалось. Однако классы типов — это совсем не то же самое, что классы в Си++ или в Джаве. Гораздо больше они похожи на абстрактные шаблоны классов в Си++, потому что классы типов
  • определяют только абстрактный интерфейс
  • позволяют создавать несколько независимых реализаций интерфейса (таким образом, для любого типа можно определить экземпляр класса, если предоставить реализацию его методов)
  • полиморфны по своей природе и поддерживают наследование
  • не могут иметь переменных состояния

Как только мы привыкнем, что типы классов — это не классы Си++, а абстрактные интерфейсы, и экземпляры классов это не «объекты», а конкретные реализации абстрактных интерфейсов, Хаскель сразу станет привычным и уютным.

Я очень советую почитать вики-статью OOP vs type classes, которая гораздо более детально сравнивает объектно-ориентированный подход и классово-типовой.


4. Монады


И так как всякое настоящее состояние простой субстанции, естественно, есть следствие ее предыдущего состояния, то настоящее ее чревато будущим, — Лейбниц, «Монадология»


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

Но вот что я понял: изучать абстрактную математику совсем не обязательно, чтобы монады использовать, а они и правда очень изящная программистская техника. Вначале они казались мне немного странными, но понять раз и навсегда монады гораздо легче, чем запоминать (и правильно применять!) бесчисленные шаблоны ОО-проектирования. Монады логичней.

Поскольку тьюториалов по монадом огромное множество, я не буду их здесь повторять и ожидаю, что вы их уже прочитал парочку. Что же не так с монадами? Для человека, привыкшему к императивным языка, испорченному годами объектно-ориентированного мышления монады кажутся странными. Они выглядят как абстрактный класс-контейнер с загадочным методом >>=:
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
fail :: String -> m a
Хорошо, если return — конструктор, то почему такое чудное имя? Если это класс-контейнер, то как из него что-либо извлечь? И какой смысл применять функцию внутри контейнера (а именно это делает метод >>=, называемый также операцией связывания), если мы не можем вытащить результат из этого контейнера?

Отвечу вначале на последний вопрос. Зачем нужно связывание (>>=)? Монады являются и одновременно не являются контейнерами. Они — обёртки, упаковки для вычислений, а не для значений (return). Однако они обёртывают вычисления не для того, чтобы их было удобнее хранить в монадных коробочках, а чтобы их можно было удобнее соединять друг с другом. Вместо «коробочек» представьте обыкновенные кирпичи, которые ровно кладутся друг к другу. Это, кстати, похоже на шаблон Adapter в ОО-проектировании. Каждая монада определяет какой-то способ передавать результат от одного вычисления к другому и реализует стандартный интерфейс, чтобы этот способ использовать (>>=). И что бы ни случилось, результат всегда останется в той же монаде (даже, если произойдёт сбой, fail).

Самая простая программистская аналогия монадам, которую я придумал, это конвееры (pipes) в командной оболочке Unix. Монады обеспечивают однонаправленный конвеер для вычислений. То же самое делают и конвееры в Unix. Например:
$ seq 1 5 | awk '{print $1 " " $1*$1*$1 ;}'
1 12 83 274 645 125
seq создаёт список целых чисел. awk вычислят куб каждого из них. Что здесь замечательного? У нас есть две слабо связанные друг с другом программы, которым мы можем легко указать работать вместе. Поток текста создаваемый программой слева попадает по конвееру в программу справа, которая может читать этот поток, что-то с ним делать и создавать уже новый текстовый поток. Текстовый поток — общий формат для результата вычислений, | — операция, связывающая их воедино.

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

Как вы уже, наверное, знаете, списки и тип Maybe в Хаскеле — монады. Например, пусть у нас есть простое вычисление, которое возвращает пару из числа и его куба обратно в монаду (return):
\x -> return (x, x^3)
тогда мы можем взять список и направить его «по конвееру» в это вычисление:
ghci> [1,2,3,4,5] >>= \x -> return (x,x^3)
[(1,1),(2,8),(3,27),(4,64),(5,125)]
Заметьте, что мы получили список пар. Это та же самая исходная монада (то есть список). Однако если мы возмьём значение Maybe и направим его в то же вычисление, на выходе у нас будет та же сама монада Maybe:
ghci> Just 5 >>= \x -> return (x,x^3)
Just (5,125)
Таким образом, мы можем создать конвеер из двух вычислений, и поведение этого конвеера зависит от контекста (т.е. от того, какая монада используется), а не от самих вычислений. В отличии от юниксовых конвееров, монады строго типизованы, и сама система типов заботится о том, чтобы выход одной монады был совместим с входом другой. И в отличии от юниксовых конвееров, мы можем задавать наши собственные правила связывания (>>=). Например, такие: «не делать более 42 вычислений подряд» или «посмотреть на входное значение, сделать то или это». Классы монад содержат в себе подобные правила, как соединять вычисления.
Дополнение: в комментариях подсказывают, что гораздо более подробно и более строго аналогия между юниксовым конвеером и монадами разобрана в статье Monadic i/o and UNIX shell programming.
Теперь, я надеюсь, вы понимаете монады не хуже меня (не обязательно полностью). Хочу обсудить несколько мнемонических правил. Почему return называется return?

В большинстве языков return возвращает результат вычисления из функции. В Хаскеле же он конструктор для монад. Это очень странно. Однако посмотрим как работает >>=: эта операция извлекает значение из монады слева, а затем связывает его с аргументом функции справа (отсюда, кстати, и другое название метода — bind). А функция справа должна вернуть значение обратно в монаду, чтобы можно было передать эстафетную палочку дальше следующей операции >>=. Это первое мнемоническое правило: return — возвращает вычисленное значения обратно в монаду.

Вторая мнемоника. Функция верхнего уровня любой программы на Хаскеле выполняется в монаде IO (тип функции mainIO ()). Эта монада позволяет выполнять ввод-вывод и вообще любые последовательные действия. Таким образом, монадный код выполняется на самом верхнем уровне программы, и именно он вызывает любой «чистый» код по мере необходимости, а не наоборот. Таким образом, любое «чистое» значение, если не отбрасывается, то рано или поздно возвращается в монаду её вызвавшую.

Надеюсь, что после этих объяснений имя return для монадного конструктора больше не кажется таким уж странным. Я, однако, не утверждаю, что мои объяснения 100% технически верны.

Следующий вопрос бывшего ОО-программиста, как вытащить значение вычисления из монады?. Начнём с того, что монады преднамеренно спроектированы именно так, что это не всегда возможно. Например, нельзя извлечь чистое значение из монады IO. Если дана такая «односторонняя» монада, то всё, что можно с ней делать — передавать внутреннее значение по монадному конвееру дальше. В Хаскеле разработан специальный синтаксис с ключевым словом do, которые делает такую многократную передачу монады по конвееру очень похожей на последовательную императивную программу. Следующие две программы делают одно и то же. Первая записана с do-нотацией:
main :: IO ()
main = do
name <- getLine
putStrLn ("Hi, " ++ name)
а вторая явно использует >>=:
main :: IO ()
main = getLine >>= \name -> putStrLn ("Hi, " ++ name)
Эквивалентная программа на Питоне:
from sys import stdin, stdout

if __name__ == "__main__":
name = stdin.readline()
stdout.write("Hi, " + name)
Однако иногда вытащить чистое значение из монадного вычисления можно. Это не предусмотрено общим монадным интерфейсом, поэтому разработчик монады должен специально предусмотреть возможность извлекать значения наружу. Например, можно извлекать значения из монады Maybe, используя функцию fromMaybe:
ghci> fromMaybe 0 $ Just 3
3
ghci> fromMaybe 0 $ Nothing
0


Заключение по монадам

Итак, связывание (>>=) позволяет объединять различные монадные вычисления вместе. Почти везде, где есть цепь вычислений, монады очень подходят. Конкретные реализации монад могут содержать разные правила комбинирования вычислений. Имя метода return сбивает с толку начинающих, это метод возвращает результа вычисления обратно в монаду, а не из монады. В общем, когда я понял эти простые идеи, это сильно помогло.

5. Страшные слова


Я знаю только то, что ничего не знаю.


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

Надо признать, Хаскель остаётся испытательной площадкой для исследователей. И это одновременно и хорошо, и плохо. Это хорошо, потому что даёт чувство, что передний край науки и технологии очень близок, и можно при желании пользоваться преимуществами новых подходов. При желании. И одновременно это плохо, потому что иногда, когда хочется использовать новую изящную библиотеку, оказывается, что она активно использует незнакомые и не совсем понятные идеи, и нужно быть готовым такие идеи осваивать.

Например, есть современная XML-библиотека HXT. Она очень много использует стрелки. Стрелки — более универсальные комбинаторы вычислений, чем монады, но мне потребовалось гораздо больше, чем один день, чтобы их более-менее понять. Строго говоря, стрелки не являются частью языка, но они — понятие, которое применяют пользователи этого языка. И таких примеров немало. Хотя тем, кому стрелки осваивать не хочется, можно пользоваться более традиционной и активно поддерживаемой XML-библиотекой HaXml.

Я думаю, важно не бояться «страшных слов». К счастью, основополагающие идеи хорошо описаны. Как правило, есть статьи их очень детально объясняющие. Я сам решил осваивать такие идеи по мере необходимости. Это обещает быть и увлекательным, и одновременно посильным.

Заключение



Я перечислил пять простых идей, освоив которые, мне стало легче привыкнуть к Хаскелю. Лямбды — это просто способ записи функций, и функции нескольких аргументов можно всегда записать как функцию одного, возвращающую другую функцию. Типы классов очень похожи на абстрактные полиморфные интерфейсы в объектно-ориентированном подходе. Монады — стандартизованный способ соединять вычисления вместе. А страшные слова — просто страшные слова. Без них можно жить, но скучно.

Надеюсь, мои заметки будут полезны и ещё кому-нибудь.

Эта статья есть также по-английски. This post is also available in English.