为字典（映射、关联数组）实现 Applicative 实例

Question

为关联数组实现仿函数实例（本质上是映射操作）似乎很简单（例如，参见 Functor 定义 [1]）。但是，Applicative 实例未定义。地图不是应用程序是否有充分的理论理由？它们需要哪些额外约束才能成为应用程序？

[1] https://hackage.haskell.org/package/containers-0.6.3.1/docs/Data-Map-Strict.html

Answer 1

正如人们在评论中指出的那样，您无法为 Map 实施有效的 Applicative 实例，因为您无法在 [=72= 中实施 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 的对数。对于 beginner-intermediate 函数式程序员来说，充其量只是一个不错的学术练习，只是为了了解如何用函数表示事物。

此处的一个简单替代方案是将不存在的键映射到常量值的“默认映射”。

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 有点不寻常，因为您可以删除键值对，但只能通过有效地将它们“重置”为默认值，因为查找对于给定的键，即使在删除相同的键后也总是会成功。尽管您当然可以使用 DefaultMap k (Maybe v) 恢复类似于 Map 的部分行为，默认值为 Nothing 并且始终将定义的键映射到 Just.

我认为还有一个instance Monad (DefaultMap k)，通过与instance Monad ((->) k)或instance Monad (Stream k)同构，因为像Stream，一个DefaultMap 总是无限——而 possibly-finite ZipList 不能有 Monad 实例，因为它必然违反结合律 a >=> (b >=> c) = (a >=> b) >=> c.

为字典（映射、关联数组）实现 Applicative 实例

Implementing Applicative instance for dictionaries (Map, associated arrays)

haskell

data-structures

functional-programming

separation-of-concerns