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

Существует много способов построить отображение «ключ–значение». Один из них – ассоциативные списки. Ассоциативные списки (также называемые словарями или отображениями ) – это списки, которые хранят неупорядоченные пары «ключ–значение». Например, мы можем применять ассоциативные списки для хранения телефонных номеров, используя телефонный номер как значение и имя человека как ключ. Нам неважно, в каком порядке они сохранены: всё, что нам требуется, – получить телефонный номер по имени. Наиболее простой способ представить ассоциативный список в языке 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принимает ассоциативный список (в форме списка) и возвращает отображение с теми же ассоциациями. Немного поиграем: