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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

Свёртки могут быть использованы для реализации любой функции, где вы вычисляете что-либо за один обход списка[8]. Если вам нужно обойти список для того, чтобы что-либо вычислить, скорее всего, вам нужна свёртка. Вот почему свёртки, наряду с функциями map и filter, – одни из наиболее часто используемых функций в функциональном программировании.

Функции foldl1 и foldr1

Функции foldl1 и foldr1 работают примерно так же, как и функции foldl и foldr, только нет необходимости явно задавать стартовое значение. Они предполагают, что первый (или последний) элемент списка является стартовым элементом, и затем начинают свёртку со следующим элементом. Принимая это во внимание, функцию maximum можно реализовать следующим образом:

maximum' :: (Ord a) => [a] -> a

maximum' = foldl1 max

Мы реализовали функцию maximum, используя foldl1. Вместо использования начального значения функция foldl1 предполагает, что таковым является первый элемент списка, после чего перемещается к следующему. Поэтому всё, что ей необходимо, – это бинарная функция и сворачиваемый лист! Мы начинаем с «головы» списка и сравниваем каждый элемент с аккумулятором. Если элемент больше аккумулятора, мы сохраняем его в качестве нового значения аккумулятора; в противном случае сохраняем старое. Мы передаём функцию max в качестве параметра foldl1, поскольку она ровно это и делает: берёт два значения и возвращает большее. К моменту завершения свёртки останется самый большой элемент.

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

С другой стороны, функции foldl и foldr хорошо работают с пустыми списками. Подумайте, имеет ли смысл свёртка для пустых списков в вашем контексте. Если функция не имеет смысла для пустого списка, то, возможно, вы захотите использовать функции foldl1 или foldr1 для её реализации.

Примеры свёрток

Для того чтобы показать, насколько мощны свёртки, мы собираемся реализовать с их помощью несколько стандартных библиотечных функций. Во-первых, реализуем свою версию функции reverse:

reverse' :: [a] -> [a]

reverse' = foldl (\acc x -> x : acc) []

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

Функция \acc x -> x : acc – почти то же, что и операция :, за исключением порядка следования параметров. Поэтому функцию reverse' можно переписать и так:

reverse' :: [a] -> [a]

reverse' = foldl (flip (:)) []

Теперь реализуем функцию product:

product' :: (Num a) => [a] -> a

product' = foldl (*) 1

Чтобы вычислить произведение всех элементов списка, следует начать с аккумулятора равного 1. Затем мы выполняем свёртку функцией (*), которая перемножает каждый элемент списка на аккумулятор.

Вот реализация функции filter:

filter' :: (a -> Bool) -> [a] -> [a]

filter' p = foldr (\x acc -> if p x then x : acc else acc) []

Здесь начальное значение аккумулятора является пустым списком. Мы сворачиваем список справа налево и проверяем каждый элемент, пользуясь предикатом p. Если p x возвращает истину, элемент x помещается в начало аккумулятора. В противном случае аккумулятор остаётся без изменения.

Напоследок реализуем функцию last:

last' :: [a] -> a

last' = foldl1 (\ x -> x)

Для получения последнего элемента списка мы применяем foldr1. Начинаем с «головы» списка, а затем применяем бинарную функцию, которая игнорирует аккумулятор и устанавливает текущий элемент списка как новое значение аккумулятора. Как только мы достигаем конца списка, аккумулятор — то есть последний элемент – возвращается в качестве результата свёртки.

Иной взгляд на свёртки

Есть ещё один способ представить работу правой и левой свёртки. Скажем, мы выполняем правую свёртку с бинарной функцией f и стартовым значением z. Если мы применяем правую свёртку к списку [3,4,5,6], то на самом деле вычисляем вот что:

f 3 (f 4 (f 5 (f 6 z)))

Функция f вызывается с последним элементом в списке и аккумулятором; получившееся значение передаётся в качестве аккумулятора при вызове функции с предыдущим значением, и т. д. Если мы примем функцию f за операцию сложения и начальное значение за нуль, наш пример преобразуется так:

3 + (4 + (5 + (6 + 0)))

Или, если записать оператор + как префиксную функцию, получится:

(+) 3 ((+) 4 ((+) 5 ((+) 6 0)))

Аналогичным образом левая свёртка с бинарной функцией g и аккумулятором z является эквивалентом выражения

g (g (g (g z 3) 4) 5) 6

Если заменить бинарную функцию на flip (:) и использовать [] как аккумулятор (выполняем обращение списка), подобная запись эквивалентна следующей:

flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6

Если вычислить это выражение, мы получим [6,5,4,3].

Свёртка бесконечных списков

Взгляд на свёртки как на последовательное применение функции к элементам списка помогает понять, почему правая свёртка иногда отлично работает с бесконечными списками. Давайте реализуем функцию and с помощью foldr, а потом выпишем последовательность применений, как мы это делали в предыдущих примерах. Тогда мы увидим, как ленивость языка Haskell позволяет правой свёртке обрабатывать бесконечные списки.

Функция and принимает список значений типа Bool и возвращает False, если хотя бы один из элементов равен False; в противном случае она возвращает True. Мы будем обходить список справа, используя True как начальное значение. В качестве бинарной функции будем использовать операцию &&, потому что должны вернуть True только в том случае, когда все элементы списка истинны. Функция && возвращает False, если хотя бы один из параметров равен False, поэтому если мы встретим в списке False, то аккумулятор будет установлен в значение False и окончательный результат также будет False, даже если среди оставшихся элементов списка обнаружатся истинные значения.

and' :: [Bool] -> Bool

and' xs = foldr (&&) True xs

Зная, как работает foldr, мы видим, что выражение and' [True,False,True] будет вычисляться следующим образом:

True && (False && (True && True))

Последнее True здесь – это начальное значение аккумулятора, тогда как первые три логических значения взяты из списка [True,False,True]. Если мы попробуем вычислить результат этого выражения, получится False.

А что если попробовать то же самое с бесконечным списком, скажем, repeat False? Если мы выпишем соответствующие применения, то получится вот что:

False && (False && (False && (False …

Ленивость Haskell позволит вычислить только то, что действительно необходимо. Функция && устроена таким образом, что если её первый параметр False, то второй просто игнорируется, поскольку и так ясно, что результат должен быть False.

Функция foldr будет работать с бесконечными списками, если бинарная функция, которую мы ей передаём, не требует обязательного вычисления второго параметра, если значения первого ей достаточно для вычисления результата. Такова функция && – ей неважно, каков второй параметр, при условии, что первый — False.

Сканирование

Функции scanl и scanr похожи на foldl и foldr, только они сохраняют все промежуточные значения аккумулятора в список. Также существуют функции scanl1 и scanr1, которые являются аналогами foldl1 и foldr1.

ghci> scanl (+) 0 [3,5,2,1]

[0,3,8,10,11]

ghci> scanr (+) 0 [3,5,2,1]

[11,8,3,1,0]

ghci> scanl1 (\acc x –> if x > acc then x else acc) [3,4,5,3,7,9,2,1]

[3,4,5,5,7,9,9,9]

ghci> scanl (flip (:)) [] [3,2,1]

[[],[3],[2,3],[1,2,3]]

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

Функции сканирования используются для того, чтобы увидеть, как работают функции, которые можно реализовать как свёртки. Давайте ответим на вопрос: как много корней натуральных чисел нам потребуется, чтобы их сумма превысила 1000? Чтобы получить сумму квадратов натуральных чисел, воспользуемся map sqrt [1..]. Теперь, чтобы получить сумму, прибегнем к помощи свёртки, но поскольку нам интересно знать, как увеличивается сумма, будем вызывать функцию scanl1. После вызова scanl1 посмотрим, сколько элементов не превышают 1000. Первый элемент в результате работы функции scanl1 должен быть равен единице. Второй будет равен 1 плюс квадратный корень двух. Третий элемент – это корень трёх плюс второй элемент. Если у нас x сумм меньших 1000, то нам потребовалось (x+1) элементов, чтобы превзойти 1000.