为字典(映射、关联数组)实现 Applicative 实例

Implementing Applicative instance for dictionaries (Map, associated arrays)

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

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

正如人们在评论中指出的那样,您无法为 Map 实施有效的 Applicative 实例,因为您无法在 [=72= 中实施 pure ] 方法。由于恒等律 pure id <*> v = vpure 实现需要在将映射与函数应用程序相交时维护所有键。您不能对部分映射执行此操作,因为根据参数化,您可能在一个映射或另一个映射中没有键来调用函数 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.