Миран Липовача - Изучай Haskell во имя добра!

• Название: Изучай Haskell во имя добра!
• Автор: Миран Липовача
• Жанр: Программирование
• Год: 2012
• ISBN: 978-5-94074-749-9

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

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

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

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

Эта книга поможет многим читателям найти свой путь к Haskell.

Отображения, монады, моноиды и другое!

Всё сказано в названии: «Изучай Хаскель во имя добра!» – весёлый иллюстрированный самоучитель по этому сложному функциональному языку.

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

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

Продираясь сквозь образные (и порой безумные) примеры автора, вы научитесь:

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

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

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

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

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

Миран Липовача (Miran Lipovača) изучает информатику в Любляне (Словения). Помимо его любви к Хаскелю, ему нравится заниматься боксом, играть на бас-гитаре и, конечно же, рисовать. У него есть увлечение танцующими скелетами и числом 71, а когда он проходит через автоматические двери, он притворяется, что на самом деле открывает их силой своей мысли.

---

addThree :: Int -> Int -> Int -> Int

addThree x y z = x + y + z

addThree' :: Int -> Int -> Int -> Int

addThree' = \x -> \y -> \z -> x + y + z

Если мы объявим функцию подобным образом, то станет понятно, почему декларация типа функции представлена именно в таком виде. И в декларации типа, и в теле функции имеются три символа –>. Конечно же, первый способ объявления функций значительно легче читается; второй – это всего лишь очередная возможность продемонстрировать каррирование.

ПРИМЕЧАНИЕ. Обратите внимание на то, что во втором примере анонимные функции не заключены в скобки. Когда вы пишете анонимную функцию без скобок, предполагается, что вся часть после символов –> относится к этой функции. Так что пропуск скобок экономит на записи. Конечно, ничто не мешает использовать скобки, если это вам больше нравится.

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

flip' :: (a –> b –> c) –> b –> a –> c

flip' f = \x y –> f y x

Несмотря на то что эта запись равнозначна flip' f x y = f y x, мы даём понять, что данная функция чаще всего используется для создания новых функций. Самый распространённый сценарий использования flip – вызов её с некоторой функцией и передача результирующей функции в map или zipWith:

ghci> zipWith (flip (++)) ["люблю тебя", "любишь меня"] ["я ", "ты "]

["я люблю тебя","ты любишь меня"]

ghci> map (flip subtract 20) [1,2,3,4]

[19,18,17,16]

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

Я вас сверну!

Когда мы разбирались с рекурсией, то во всех функциях для работы со списками наблюдали одну и ту же картину. Базовым случаем, как правило, был пустой список. Мы пользовались образцом (x:xs) и затем делали что-либо с «головой» и «хвостом» списка. Как выясняется, это очень распространённый шаблон. Были придуманы несколько полезных функций для его инкапсуляции. Такие функции называются свёртками (folds). Свёртки позволяют свести структуру данных (например, список) к одному значению.

Функция свёртки принимает бинарную функцию, начальное значение (мне нравится называть его «аккумулятором») и список. Бинарная функция принимает два параметра. Она вызывается с аккумулятором и первым (или последним) элементом из списка и вычисляет новое значение аккумулятора. Затем функция вызывается снова, с новым значением аккумулятора и следующим элементом из списка, и т. д. То, что остаётся в качестве значения аккумулятора после прохода по всему списку, и есть результат свёртки.

Левая свёртка foldl

Для начала рассмотрим функцию foldl – свёртка слева. Она сворачивает список, начиная с левой стороны. Бинарная функция применяется для начального значения и первого элемента списка, затем для вновь вычисленного аккумулятора и второго элемента списка и т. д.

Снова реализуем функцию sum, но на этот раз будем пользоваться свёрткой вместо явной рекурсии.

sum' :: (Num a) => [a] –> a

sum' xs = foldl (\acc x –> acc + x) 0 xs

Проверка – раз, два, три!

ghci> sum' [3,5,2,1]

11

Давайте посмотрим более внимательно, как работает функция foldl. Бинарная функция – это лямбда-выражение (\acc x –> acc + x), нуль – стартовое значение, и xs – список. В самом начале нуль используется как значение аккумулятора, а 3 – как значение образца x (текущий элемент). Выражение (0+3) в результате даёт 3; это становится новым значением аккумулятора. Далее, 3 используется как значение аккумулятора и 5 – как текущий элемент; новым значением аккумулятора становится 8. На следующем шаге 8 – значение аккумулятора, 2 – текущий элемент, новое значение аккумулятора становится равным 10. На последнем шаге 10 из аккумулятора и 1 как текущий элемент дают 11. Поздравляю – вы только что выполнили свёртку списка!

Диаграмма на предыдущей странице иллюстрирует работу свёртки шаг за шагом, день за днём. Цифры слева от знака + представляют собой значения аккумулятора. Как вы можете видеть, аккумулятор будто бы «поедает» список, начиная с левой стороны. Ням-ням-ням! Если мы примем во внимание, что функции каррированы, то можем записать определение функции ещё более лаконично:

sum' :: (Num a) => [a] –> a

sum' = foldl (+) 0

Анонимная функция (\acc x –> acc + x) – это то же самое, что и оператор (+). Мы можем пропустить xs в параметрах, потому что вызов foldl (+) 0 вернёт функцию, которая принимает список. В общем, если у вас есть функция вида foo a = bar b a, вы всегда можете переписать её как foo = bar b, так как происходит каррирование.

Ну что ж, давайте реализуем ещё одну функцию с левой свёрткой перед тем, как перейти к правой. Уверен, все вы знаете, что функция elem проверяет, является ли некоторое значение частью списка, так что я не буду этого повторять (тьфу ты – не хотел, а повторил!). Итак:

elem' :: (Eq a) => a –> [a] –> Bool

elem' y ys = foldl (\acc x –> if x == y then True else acc) False ys

Что мы имеем? Стартовое значение и аккумулятор – булевские значения. Тип аккумулятора и стартового значения в свёртках всегда совпадают. Запомните это правило: оно может подсказать вам, что следует использовать в качестве стартового значения, если вы затрудняетесь. В данном случае мы начинаем со значения False. В этом есть смысл: предполагается, что в списке нет искомого элемента. Если мы вызовем функцию свёртки с пустым списком, то результатом будет стартовое значение. Затем мы проверяем текущий элемент на равенство искомому. Если это он – устанавливаем в True. Если нет – не изменяем аккумулятор. Если он прежде был равен значению False, то остаётся равным False, так как текущий элемент – не искомый. Если же был равен True, мы опять-таки оставляем его неизменным.

Правая свёртка foldr

Правая свёртка, foldr, работает аналогично левой, только аккумулятор поглощает значения, начиная справа. Бинарная функция левой свёртки принимает аккумулятор как первый параметр, а текущее значение – как второй (\acc x –> …); бинарная функция правой свёртки принимает текущее значение как первый параметр и аккумулятор – как второй (\x acc –> …). То, что аккумулятор находится с правой стороны, в некотором смысле логично, поскольку он поглощает значения из списка справа.

Значение аккумулятора (и, следовательно, результат) функции foldr могут быть любого типа. Это может быть число, булевское значение или даже список. Мы реализуем функцию map с помощью правой свёртки. Аккумулятор будет списком; будем накапливать пересчитанные элементы один за другим. Очевидно, что начальным элементом является пустой список:

map' :: (a –> b) –> [a] –> [b]

map' f xs = foldr (\x acc –> f x : acc) [] xs

Если мы применяем функцию (+3) к списку [1,2,3], то обрабатываем список справа. Мы берём последний элемент, тройку, применяем к нему функцию, и результат оказывается равен 6. Затем добавляем это число к аккумулятору, который был равен []. 6:[] – то же, что и [6]; это новое значение аккумулятора. Мы применяем функцию (+3) к значению 2, получаем 5 и при помощи конструктора списка : добавляем его к аккумулятору, который становится равен [5,6]. Применяем функцию (+3) к значению 1, добавляем результат к аккумулятору и получаем финальное значение [4,5,6].

Конечно, можно было бы реализовать эту функцию и при помощи левой свёртки:

map' :: (a -> b) -> [a] -> [b]

map' f xs = foldl (\acc x –> acc ++ [f x]) [] xs

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

Если вы обратите список задом наперёд, то сможете выполнять правую свёртку с тем же результатом, что даёт левая свёртка, и наоборот. В некоторых случаях обращать список не требуется. Функцию sum можно реализовать как с помощью левой, так и с помощью правой свёртки. Единственное серьёзное отличие: правые свёртки работают на бесконечных списках, а левые – нет! Оно и понятно: если вы берёте бесконечный список в некоторой точке и затем сворачиваете его справа, рано или поздно вы достигаете начала списка. Если же вы берёте бесконечный список в некоторой точке и пытаетесь свернуть его слева, вы никогда не достигнете конца!