Изучай Haskell во имя добра! (Липовача) - страница 74
Это классическая рекурсивная функция, обрабатывающая список. Базовый случай, разбиение списка на «голову» и «хвост», рекурсивный вызов – всё на месте. Также это классический шаблон для применения свёртки. Посмотрим, как то же самое можно реализовать с помощью свёртки.
>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, а затем ассоциативный список, представляющий отображение.
Если в исходном списке есть дубликаты ключей, они отбрасываются: