Почти хорошо: ассоциативные списки

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

 

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

 

Модуль 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

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"]

Превосходно!

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

ghci> Map.fromListWith max [(2,3),(2,100),(3,29),(3,11),(4,22),(4,15)] fromList [(2,100),(3,29),(4,22)]

Или хотим, чтобы значения с повторяющимися ключами скла- дывались:

ghci> Map.fromListWith (+) [(2,3),(2,100),(3,29),(3,11),(4,22),(4,15)] fromList [(2,103),(3,40),(4,37)]

Ну что ж, модуль Data.Map, да и другие модули из стандартной библиотеки языка Haskell довольно неплохи. Далее посмотрим, как написать свой собственный модуль.