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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

findKey :: (Eq k) => k –> [(k,v)] –> Maybe v

findKey key [] = Nothing

findKey key ((k,v):xs)

  | key == k = Just v

  | otherwise = findKey key xs

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

Это классическая рекурсивная функция, обрабатывающая список. Базовый случай, разбиение списка на «голову» и «хвост», рекурсивный вызов – всё на месте. Также это классический шаблон для применения свёртки. Посмотрим, как то же самое можно реализовать с помощью свёртки.

findKey :: (Eq k) => k –> [(k,v)] –> Maybe v

findKey key = foldr (\(k,v) acc –> if key == k then Just v else acc) Nothing

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

ghci> findKey "юля" phoneBook

Just "853–24-92"

ghci> findKey "оля" phoneBook

Just "555–29-38"

ghci> findKey "аня" phoneBook

Nothing

Отлично, работает! Если у нас есть телефонный номер девушки, мы просто (Just) получим номер; в противном случае не получим ничего (Nothing).

Модуль Data.Map

Мы только что реализовали функцию lookup из модуля Data.List. Если нам нужно значение, соответствующее ключу, понадобится обойти все элементы списка, пока мы его не найдём.

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

Так как модуль Data.Map экспортирует функции, конфликтующие с модулями Prelude и Data.List, мы будем импортировать их с помощью квалифицированного импорта.

import qualified Data.Map as Map

Поместите этот оператор в исходный код и загрузите его в GHCi. Мы будем преобразовывать ассоциативный список в отображение с помощью функции fromList из модуля Data.Map. Функция fromList принимает ассоциативный список (в форме списка) и возвращает отображение с теми же ассоциациями. Немного поиграем:

ghci> Map.fromList [(3, "туфли"),(4,"деревья"),(9,"пчёлы")]

fromList [(3, "туфли"),(4,"деревья"),(9,"пчёлы")]

ghci> Map.fromList [("эрик","форман"),("роберт","чейз"),("крис", "тауб")]

fromList [("крис","тауб"),("роберт","чейз"),("эрик","форман")]

Когда отображение из модуля Data.Map показывается в консоли, сначала выводится fromList, а затем ассоциативный список, представляющий отображение.

Если в исходном списке есть дубликаты ключей, они отбрасываются:

ghci> Map.fromList [("MS",1),("MS",2),("MS",3)]

fromList [("MS",3)]

Вот сигнатура функции fromList:

Map.fromList :: (Ord k) => [(k, v)] –> Map.Map k v

Она говорит, что функция принимает список пар со значениями типа k и v и возвращает отображение, которое отображает ключи типа k в значения типа v. Обратите внимание, что если мы реализуем ассоциативный список с помощью обычного списка, то значения ключей должны лишь уметь сравниваться (иметь экземпляр класса типов Eq); теперь же должна быть возможность их упорядочить (класс типов Ord). Это существенное ограничение модуля Data.Map. Упорядочиваемые ключи нужны ему для того, чтобы размещать данные более эффективно.

Теперь мы можем преобразовать наш исходный ассоциативный список phoneBook в отображение. Заодно добавим сигнатуру:

import qualified Data.Map as Map

phoneBook :: Map.Map String String

phoneBook = Map.fromList $

  [("оля","555–29-38")

  ,("женя","452–29-28")

  ,("катя","493–29-28")

  ,("маша","205–29-28")

  ,("надя","939–82-82")

  ,("юля","853–24-92")

  ]

Отлично. Загрузим этот сценарий в GHCi и немного поиграем с телефонной книжкой. Во-первых, воспользуемся функцией lookup и поищем какие-нибудь номера. Функция lookup принимает ключ и отображение и пытается найти соответствующее ключу значение. Если всё прошло удачно, возвращается обёрнутое в Just значение; в противном случае – Nothing:

ghci> :t Map.lookup

Map.lookup :: (Ord k) => k -> Map.Map k a -> Maybe a

ghci> Map.lookup "оля" phoneBook

Just "555-29-38"

ghci> Map.lookup "надя" phoneBook

Just "939-82-82"

ghci> Map.lookup "таня" phoneBook

Nothing

Следующий трюк: создадим новое отображение, добавив в исходное новый номер. Функция insert принимает ключ, значение и отображение и возвращает новое отображение – почти такое же, что и исходное, но с добавленными ключом и значением:

ghci> :t Map.insert

Map.insert :: (Ord k) => k -> a -> Map.Map k a -> Map.Map k a

ghci> Map.lookup "таня" phoneBook

Nothing

ghci> let newBook = Map.insert "таня" "341-90-21" phoneBook

ghci> Map.lookup "таня" newBook

Just "341-90-21"

Давайте посчитаем, сколько у нас телефонных номеров. Для этого нам понадобится функция size из модуля Data.Map. Она принимает отображение и возвращает его размер. Тут всё ясно:

ghci> :t Map.size

Map.size :: Map.Map k a -> Int

ghci> Map.size phoneBook

6

ghci> Map.size newBook

7

Номера в нашей телефонной книжке представлены строками. Допустим, мы хотим вместо них использовать списки цифр: то есть вместо номера "939-82-82" – список [9,3,9,8,2,8,2]. Сначала напишем функцию, конвертирующую телефонный номер в строке в список целых. Можно попытаться применить функцию digitToInt из модуля Data.Char к каждому символу в строке, но она не знает, что делать с дефисом! Поэтому нужно избавиться от всех нецифр. Попросим помощи у функции isDigit из модуля Data.Char, которая принимает символ и сообщает нам, является ли он цифрой. Как только строка будет отфильтрована, пройдёмся по ней функцией digitToInt.

string2digits :: String -> [Int]

string2digits = map digitToInt . filter isDigit

Да, не забудьте импортировать модуль Data.Char. Пробуем:

ghci> string2digits "948-92-82"

[9,4,8,9,2,8,2]

Замечательно! Теперь применим функцию map из модуля Data. Map, чтобы пропустить функцию string2digits по элементам отображения phoneBook:

ghci> let intBook = Map.Map string2digits phoneBook

ghci> :t intBook

intBook :: Map.Map String [Int]

ghci> Map.lookup "оля" intBook

Just [5,5,5,2,9,3,8]

Функция map из модуля Data.Map принимает функцию и отображение и применяет эту функцию к каждому значению в отображении.

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

phoneBook =

  [("оля","555–29-38")

  ,("оля","342–24-92")

  ,("женя","452–29-28")

  ,("катя","493–29-28")

  ,("катя","943–29-29")

  ,("катя","827–91-62")

  ,("маша","205–29-28")

  ,("надя","939–82-82")

  ,("юля","853–24-92")

  ,("юля","555–21-11")

  ]

Если мы просто вызовем fromList, чтобы поместить всё это в отображение, то потеряем массу номеров! Вместо этого воспользуемся другой функцией из модуля Data.Map, а именно функцией fromListWith. Эта функция действует почти как fromList, но вместо отбрасывания повторяющихся ключей вызывает переданную ей функцию, которая и решает, что делать.

phoneBookToMap :: (Ord k) => [(k, String)] -> Map.Map k String

phoneBookToMap xs = Map.fromListWith add xs

  where add number1 number2 = number1 ++ ", " ++ number2

Если функция fromListWith обнаруживает, что ключ уже существует, она вызывает переданную ей функцию, которая соединяет оба значения в одно, а затем заменяет старое значение на новое, полученное от соединяющей функции:

ghci> Map.lookup "катя" $ phoneBookToMap phoneBook

"827–91-62, 943–29-29, 493–29-28"

ghci> Map.lookup "надя" $ phoneBookToMap phoneBook

"939-82-82"

ghci> Map.lookup "оля" $ phoneBookToMap phoneBook

"342-24-92, 555-29-38"

А ещё можно было бы сделать все значения в ассоциативном списке одноэлементными списками, а потом скомбинировать их операцией ++, например:

phoneBookToMap :: (Ord k) => [(k, a)] -> Map.Map k [a]

phoneBookToMap xs = Map.fromListWith (++) $ map (\(k,v) -> (k, [v])) xs

Проверим в GHCi:

ghci> Map.lookup "катя" $ phoneBookToMap phoneBook

["827–91-62","943–29-29","493–29-28"]