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

ghci> Nothing

Nothing

ghci> Just "эй"

Just "эй"

ghci> Just 3

Just 3

ghci> :t Just "эй"

Just "эй" :: Maybe [Char]

ghci> :t Just True

Just True :: Maybe Bool

Видите, значение Just Trueимеет тип Maybe Bool. Похоже на то, что список, содержащий значения типа Bool, имеет тип [Bool].

Если функция findнаходит элемент, удовлетворяющий предикату, она возвращает этот элемент, обёрнутый в Just. Если не находит, возвращает Nothing:

ghci> find (>4) [3,4,5,6,7]

Just 5

ghci> find odd [2,4,6,8,9]

Just 9

ghci> find (=='x') "меч-кладенец"

Nothing

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

firstTo40 :: Maybe Int

firstTo40 = find (\x -> digitSum == 40) [1..]

Мы просто взяли бесконечный список [1..]и начали искать первое число, значение digitSumдля которого равно 40.

ghci> firstTo40

Just 49999

А вот и ответ! Можно сделать более общую функцию, которой нужно передавать искомую сумму в качестве параметра:

firstTo :: Int -> Maybe Int

firstTo n = find (\x -> digitSum x == n) [1..]

И небольшая проверка:

ghci> firstTo 27

Just 999

ghci> firstTo 1

Just 1

ghci> firstTo 13

Just 49

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

Существует много способов построить отображение «ключ–значение». Один из них – ассоциативные списки. Ассоциативные списки (также называемые словарями или отображениями ) – это списки, которые хранят неупорядоченные пары «ключ–значение». Например, мы можем применять ассоциативные списки для хранения телефонных номеров, используя телефонный номер как значение и имя человека как ключ. Нам неважно, в каком порядке они сохранены: всё, что нам требуется, – получить телефонный номер по имени. Наиболее простой способ представить ассоциативный список в языке Haskell – использовать список пар. Первый компонент пары будет ключом, второй – значением. Вот пример ассоциативного списка с номерами телефонов:

phoneBook =

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

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

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

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

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

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

]

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

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

findKey key xs = snd . head $ filter (\(k,v) –> key == k) xs

Всё довольно просто. Функция принимает ключ и список, фильтрует список так, что остаются только совпадающие ключи, получает первую пару «ключ–значение», возвращает значение. Но что произойдёт, если искомого ключа нет в списке? В этом случае мы будем пытаться получить «голову» пустого списка, что вызовет ошибку времени выполнения. Однако следует стремиться к тому, чтобы наши программы были более устойчивыми к «падениям», поэтому давайте используем тип Maybe. Если мы не найдём ключа, то вернём значение Nothing. Если найдём, будем возвращать Just < то, что нашли >.

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).

Мы только что реализовали функцию 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, а затем ассоциативный список, представляющий отображение.

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