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

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