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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

ghci> words "всё это слова в этом предложении"

["всё","это","слова","в","этом","предложении"]

ghci> words "всё        это слова в      этом      предложении"

["всё","это","слова","в","этом","предложении"]

Затем воспользуемся функцией group, которая тоже «живёт» в Data.List, чтобы сгруппировать одинаковые слова. Эта функция принимает список и собирает одинаковые подряд идущие элементы в подсписки:

ghci> group [1,1,1,1,2,2,2,2,3,3,2,2,2,5,6,7]

[[1,1,1,1],[2,2,2,2],[3,3],[2,2,2],[5],[6],[7]]

Но что если одинаковые элементы идут в списке не подряд?

ghci> group ["бум","бип","бип","бум","бум"]

[["бум"],["бип","бип"],["бум","бум"]]

Получаем два списка, содержащих "бум", тогда как нам бы хотелось, чтобы все вхождения одного и того же слова попали в один список. Что делать? Мы можем предварительно отсортировать список! Для этого применим функцию sort из Data.List. Она принимает список элементов, которые могут быть упорядочены, и возвращает новый список, содержащий те же элементы, но упорядоченные от наименьшего к наибольшему:

ghci> sort [5,4,3,7,2,1]

[1,2,3,4,5,7]

ghci> sort ["бум","бип","бип","бум","бум"]

["бип","бип","бум","бум","бум"]

Заметим, что строки упорядочены по алфавиту.

Теперь всё необходимое у нас есть, осталось только записать решение. Берём строку, разбиваем её на список слов, сортируем слова и группируем одинаковые. Затем применяем map и получаем список вроде ("boom", 3); это означает, что слово "boom" встретилось в исходной строке трижды.

import Data.List

wordNums :: String -> [(String, Int)]

wordNums = map (\ws -> (head ws, length ws)) . group . sort . words

Для написания этой функции мы применили композицию функций. Предположим, что мы вызвали функцию wordNums для строки "уа уа уи уа". К этой строке применяется функция words, результатом которой будет список ["уа","уа","уи","уа"]. После его сортировки функцией sort получим новый список ["уа","уа","уа","уи"]. Группировка одинаковых подряд идущих слов функцией group даст нам список [["уа","уа","уа"],["уи"]]. Затем с помощью функции map к каждому элементу такого списка (то есть к подсписку) будет применена анонимная функция, которая превращает список в пару – «голова» списка, длина списка. В конечном счёте получаем [("уа",3),("уи",1)].

Вот как можно написать ту же функцию, не пользуясь операцией композиции:

wordNums xs = map (\ws -> (head ws, length ws)) (group (sort (words xs)))

Кажется, здесь избыток скобок! Думаю, нетрудно заметить, насколько более читаемой делает функцию операция композиции.

Иголка в стоге сена

Следующая наша миссия – написание функции, которая принимает на вход два списка и сообщает, содержится ли первый список целиком где-нибудь внутри второго. Например, список [3,4] содержится внутри [1,2,3,4,5], а вот [2,5] – уже нет. Список, в котором мы ищем, назовём стогом, а список, который хотим обнаружить, – иголкой.

Чтобы выбраться из этой передряги, воспользуемся функцией tails из того же модуля Data.List. Она принимает список и последовательно применяет к нему функцию tail. Вот пример:

ghci> tails "победа"

["победа","обеда","беда","еда","да","а",""]

ghci> tails [1,2,3]

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

Возможно, пока неясно, зачем она нам вообще понадобилась. Сейчас увидим.

Предположим, мы хотим найти строку "обед" внутри строки "победа". Для начала вызовем tails и получим все «хвосты» списка. Затем присмотримся к каждому «хвосту», и если хоть какой-нибудь из них начинается со строки "обед", значит, иголка найдена! Вот если бы мы искали "фуу" внутри "победа" – тогда да, ни один из «хвостов» с "фуу" не начинается.

Чтобы узнать, не начинается ли одна строка с другой, мы применим функцию isPrefixOf, снова из модуля Data.List. Ей на вход подаются два списка, а она отвечает, начинается второй список с первого или нет.

ghci> "гавайи" `isPrefixOf` "гавайи джо"

True

ghci> "ха-ха" `isPrefixOf` "ха"

False

ghci> "ха" `isPrefixOf` "ха"

True

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

List. Она принимает предикат и список и сообщает, удовлетворяет ли этому предикату хотя бы один элемент списка. Внимание:

ghci> any (>4) [1,2,3]

False

ghci> any (=='Х') "Грегори Хаус"

True

ghci> any (\x -> x > 5 && x < 10) [1,4,11]

False

Соберём все эти функции вместе:

import Data.List

isIn :: (Eq a) => [a] -> [a] -> Bool

needle `isIn` haystack = any (needle `isPrefixOf`) (tails haystack)

Вот и всё! Функция tails создаёт список «хвостов» нашего стога, а затем мы смотрим, начинается ли что-нибудь из них с иголки. Проверим:

ghci> "обед" `isIn` "победа"

True

ghci> [1,2] `isIn` [1,3,5]

False

Ой, подождите-ка! Кажется, только что написанная функция уже есть в Data.List… Ба-а, и правда! Она называется isInfixOf и делает в точности то же, что наша isIn.

Салат из шифра Цезаря

Гай Юлий Цезарь возложил на нас ответственное поручение. Необходимо доставить совершенно секретное сообщение в Галлию Марку Антонию. На случай, если нас схватят, мы закодируем сообщение шифром Цезаря, воспользовавшись с этой целью некоторыми функциями из модуля Data.Char.

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

Для сдвига символов вперёд и назад по кодовой таблице будем применять функции ord и chr, находящиеся в модуле Data.Char. Эти функции преобразуют символы к соответствующим кодам и наоборот:

ghci> ord 'a'

97

ghci> chr 97

'a'

ghci> map ord "abcdefgh"

[97,98,99,100,101,102,103,104]

Функция ord 'a' возвращает 97, поскольку символ 'a' является девяносто седьмым символом в таблице символов Unicode.

Разность между значениями функции ord для двух символов равна расстоянию между ними в кодовой таблице.

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

import Data.Char

encode :: Int -> String -> String

encode offset msg = map (\c -> chr $ ord c + offset) msg

Кодирование строки тривиально настолько, насколько легко взять сообщение и пройтись по каждому его символу функцией, преобразующей его в соответствующий код, прибавляющей смещение и конвертирующей результат обратно в символ. Любитель композиции записал бы такую функцию как (chr . (+offset) . ord).

ghci> encode 3 "привет марк"

"тулеих#пгун"

ghci> encode 5 "прикажи своим людям"

"фхнпелн%цзунс%рйєс"

ghci> encode 1 "веселиться вволю"

"гжтжмйуэт!ггпмя"

И вправду закодировано!

Декодирование сообщения – это всего навсего сдвиг обратно на то же количество позиций, на которое ранее проводился сдвиг вперёд.

decode :: Int -> String -> String

decode shift msg = encode (negate shift) msg

Теперь проверим, декодируется ли сообщение Цезаря:

ghci> decode 3 "тулеих#пгун"

"привет марк"

ghci> decode 5 "фхнпелн%цзунс%рйєс"

"прикажи своим людям"

ghci> decode 1 "гжтжмйуэт!ггпмя"

"веселиться вволю"

О строгих левых свёртках

В предыдущей главе мы видели, как работает функция foldl и как с её помощью реализовывать всякие крутые функции. Правда, мы пока не исследовали одну связанную с foldl ловушку: её использование иногда может приводить к так называемым ошибкам переполнения стека, которые случаются, если программе требуется слишком много места в одном специальном разделе памяти (в сегменте стека). Проиллюстрируем проблему, воспользовавшись свёрткой с функцией + для суммирования списка из сотни единиц:

ghci> foldl (+) 0 (replicate 100 1)

100

Пока всё работает. Но что если сделать то же самое для списка, содержащего, спасибо доктору Зло, один миллион единиц?

ghci> foldl (+) 0 (replicate 1000000 1)

*** Exception: stack overflow

Ого, жестоко! Что же случилось? Haskell ленив, поэтому он откладывает реальные вычисления настолько, насколько возможно. Когда мы используем foldl, Haskell не вычисляет аккумулятор на каждом шаге. Вместо этого он откладывает вычисление. На каждом следующем шаге он снова ничего не считает, опять откладывая на потом. Ему, правда, приходится сохранять старое отложенное вычисление в памяти, потому что новому может потребоваться его результат. Таким образом, пока свёртка foldl радостно торопится по списку, в памяти образуется куча отложенных вычислений, каждое из которых занимает некоторый объём памяти. Рано или поздно это может привести к ошибке переполнения стека.