Реализация экземпляра Applicative для словарей (карта, связанные массивы)

Как отмечалось в комментариях, вы не можете реализовать действительный экземпляр Applicative для Map, потому что вы не можете реализовать pure законопослушным способом. Из-за закона тождества pure id <*> v = v реализация pure должна поддерживать все ключи при пересечении карт с приложением функции. Вы не можете сделать это для частичных карт, потому что из-за параметризации у вас может не быть ключа в одной или другой карте, из которого можно вызвать функцию a -> b или аргумент a, необходимые для создания b в результирующей карте. pure x должен работать так же, как и для ZipList (который использует repeat), создавая карту, которая сопоставляет каждый ключ с одним и тем же значением x, но это невозможно с Map, потому что оно конечно. Однако это возможна с альтернативными представлениями, допускающими бесконечные карты, такими как карта, основанная на функциях и Eq.

-- Represent a map by its lookup function.
newtype EqMap k v = EM (k -> Maybe v)

-- Empty: map every key to ‘Nothing’.
emEmpty :: EqMap k v
emEmpty = EM (const Nothing)

-- Singleton: map the given key to ‘Just’ the given value,
-- and all other keys to ‘Nothing’.
emSingleton :: (Eq k) => k -> v -> EqMap k v
emSingleton k v = EM (\ k' -> if k == k' then Just v else Nothing)

-- Insertion: add an entry that overrides any earlier entry
-- for the same key to return ‘Just’ a new value.
emInsert :: (Eq k) => k -> v -> EqMap k v -> EqMap k v
emInsert k v (EM e) = EM (\ k' -> if k == k' then Just v else e k')

-- Deletion: add an entry that overrides any earlier entry
-- for the same key to return ‘Nothing’.
emDelete :: (Eq k) => k -> EqMap k v -> EqMap k v
emDelete k (EM e) = EM (\ k' -> if k == k' then Nothing else e k')

emLookup :: EqMap k v -> k -> Maybe v
emLookup (EM e) = e

instance Functor (EqMap k) where

  -- Map over the return value of the lookup function.
  fmap :: (a -> b) -> EqMap k a -> EqMap k v
  fmap f (EM e) = EM (fmap (fmap f) e)

instance Applicative (EqMap k) where

  -- Map all keys to a constant value.
  pure :: a -> EqMap k a
  pure x = EM (const (Just x))

  -- Intersect two maps with application.
  (<*>) :: EqMap k (a -> b) -> EqMap k a -> EqMap k b
  fs <*> xs = EM (\ k -> emLookup k fs <*> emLookup k xs)

К сожалению, это бесконечно не только семантически: когда вы добавляете или удаляете пары ключ-значение, оно также бесконечно растет в памяти! Это связано с тем, что записи представляют собой связанный список замыканий, а не материализованную структуру данных: вы можете удалить значения с карты только путем добавления записи, указывающей на их удаление, как реверсия в системе контроля версий. . Это также очень неэффективно для поиска, который является линейным по количеству ключей, а не логарифмическим для Map. В лучшем случае это нормальное академическое упражнение для начинающего функционального программиста среднего уровня, просто чтобы понять, как представлять вещи с помощью функций.

Простая альтернатива здесь — «карта по умолчанию», которая сопоставляет несуществующие ключи с постоянным значением.

data DefaultMap k v = DM v (Map k v)

dmLookup :: (Ord k) => k -> DefaultMap k v -> v
dmLookup k (DM d m) = fromMaybe d (Map.lookup k m)

-- …

Тогда реализация Applicative проста: пересечение существующих ключей плюс несуществующие ключи применяются со значением по умолчанию.

instance Functor (DefaultMap k) where

  -- Map over the return value of the lookup function.
  fmap :: (a -> b) -> DefaultMap k a -> DefaultMap k b
  fmap f (DM d m) = DM (f d) (fmap f m)

instance Applicative (DefaultMap k) where

  -- Map all keys to a constant value.
  pure x = DM x mempty

  -- Intersect two maps with application, accounting for defaults.
  DM df fs <*> DM dx xs = DM (df dx) $ Map.unions
    [ Map.intersectionWith ($) fs xs
    , fmap ($ dx) fs
    , fmap (df $) xs
    ]

DefaultMap несколько необычен тем, что вы можете удалять пары "ключ-значение", но только путем эффективного "сброса" их до значений по умолчанию, в том смысле, что поиск данного ключа всегда будет успешным, даже после удаления тот самый ключ. Хотя вы, конечно, можете восстановить что-то, напоминающее частичное поведение Map, используя DefaultMap k (Maybe v) со значением по умолчанию Nothing и инвариантом постоянного сопоставления определенных ключей с Just.

Я думаю, что существует также instance Monad (DefaultMap k), благодаря изоморфизму с instance Monad ((->) k) или instance Monad (Stream k), поскольку, как и Stream, DefaultMap всегда бесконечно, тогда как возможно конечное ZipList не может иметь Monad случае, потому что он неизбежно нарушает закон ассоциативности a >=> (b >=> c) = (a >=> b) >=> c.