Связь между функцией карты в Data.Map и функцией fromList - PullRequest
Новая
       6

Связь между функцией карты в Data.Map и функцией fromList

0 голосов
/ 16 января 2019

Я не понимаю подпись Map.map (функция карты в Data.Map) и подпись Map.fromList. Сама функция есть в подписи. Я также не уверен, почему Map.fromList всегда вызывается, когда я хочу реализовать другие функции, такие как Map.member или Map.filter или Map.size. Например, почему я не могу просто применить функцию непосредственно к списку, но вместо этого должен косвенно применить ее через Map.fromList.

Не в последнюю очередь ... подпись fromList '. Я заметил, что вызываемая функция Map.Map имеет заглавную M вместо маленькой m, которая выключена (в отношении Map.map во второй строке). Почему это так?

Большое спасибо 

Map.fromList :: Ord k => [(k, a)] -> Map.Map k a
Map.map :: (a -> b) -> Map.Map k a -> Map.Map k b

fromList' :: (Ord a) => [(a,b)] -> Map.Map a b
fromList' = foldl (\acc (a,b) -> Map.insert a b acc) Map.empty

1 Ответ

0 голосов
/ 16 января 2019

Ух ты, похоже, ты в замешательстве. Это понятно, так как слово «карта» означает как минимум четыре разные вещи!

  1. Модуль Data.Map (вам, кажется, ясно об этом)
  2. Тип данных Map.Map k v (в модуле Data.Map), который является конечной картой, он же "словарь", он же "хэш-таблица" (но он не использует хеширование)
  3. Функция Map.map (в модуле Data.Map), которая применяет функцию к каждому значению в Map (словарь)
  4. Существует также стандартная функция map (в Prelude), которая работает со списками и не имеет ничего общего с Map s (словарями).

Уфф, что за глоток!

Вот несколько объяснений подписи: 

Map.fromList :: (Ord k) => [(k, a)] -> Map.Map k a

Map.Map k a - это параметризованный тип данных с двумя параметрами, k и a. Если вы знакомы с обобщениями в семействе C ++, это может быть написано Map<K, A>.

Функция fromList принимает список пар (ключ, значение), [(k, a)] и возвращает словарь. Ключи словаря имеют тип k, а значения имеют тип a. (Ord k) означает, что ключи должны быть упорядочены по отношению друг к другу, поскольку они хранят структуру данных в виде отсортированного сбалансированного дерева. 

-- A dictionary from people's names to their age
ages :: Map.Map String Int
ages = Map.fromList [("Bill", 32), ("Carol", 71), ("Diddy", 13)]

Map.map :: (a -> b) -> Map.Map k a -> Map.Map k b

Это принимает функцию от вещей типа a к вещам типа b в качестве первого параметра. В качестве второго параметра он берет словарь из любого типа ключа k для элементов типа a и применяет функцию к каждому значению в словаре, возвращая словарь из того же типа ключа для элементов типа b. 

-- A dictionary from people's names to whether they are allowed to drink alcohol
canDrink :: Map.Map String Bool
canDrink = Map.map (\age -> age >= 21) ages

fromList' - это просто пользовательская реализация fromList, реализованная путем многократной вставки. Неудивительно, что он имеет ту же сигнатуру, что и fromList (но переменные типа называются по-разному - это не имеет значения).

...