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, а затем ассоциативный список, представляющий отображение.
Если в исходном списке есть дубликаты ключей, они отбрасываются:
ghci> Map.fromList [("MS",1),("MS",2),("MS",3)]
fromList [("MS",3)]
Вот сигнатура функции fromList:
Map.fromList :: (Ord k) => [(k, v)] –> Map.Map k v
