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