实现字典的适用实例(地图，关联数组) [英] Implementing Applicative instance for dictionaries (Map, associated arrays)

问题描述

为关联数组实现函子实例(本质上是映射操作)似乎很简单(例如，参见 Functor 定义[1]).但是，未定义 Applicative 实例.从理论上讲，地图不是适用语言，这有很好的理由吗?要成为应用程序，还需要哪些其他限制?

It seems straightforward to implement a functor instance (essentially a mapping operation) for associated arrays (e.g. see Functor definition [1]). However, Applicative instance is not defined. Is there a good theoretical reason that Maps are not Applicatives? What additional constrains are required for them to be Applicatives?

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

推荐答案

正如人们在评论中指出的那样，您不能为 Map Applicative 实例>，因为您不能以守法的方式实现 pure .由于身份法，纯ID< *>v = v ， pure 实现需要在将地图与函数应用程序相交的同时维护所有键.您无法对部分地图执行此操作，因为根据参数，您可能在一个地图或另一个地图中都没有按键来构造功能 a->.b 或参数 a ，您需要在结果映射中生成 b . pure x 将需要像 ZipList (使用 repeat )那样工作，从而生成一张可以映射每的地图>键为相同的值 x ，但是对于 Map 这是不可能的，因为它是有限的.但是， 可以使用允许无限映射的替代表示形式，例如基于函数和 Eq 的映射.

As folks have pointed out in the comments, you can’t implement a valid Applicative instance for Map because you can’t implement pure in a law-abiding way. Because of the identity law, pure id <*> v = v, the pure implementation needs to maintain all of the keys while intersecting the maps with function application. You can’t do that for partial maps because, by parametricity, you may not have a key in one map or the other from which to conjure the function a -> b or argument a that you need to produce a b in the resulting map. pure x would need to work like the one for ZipList (which uses repeat), producing a map that maps every key to the same value x, but this isn’t possible with Map because it’s finite. However, it is possible with alternative representations that allow infinite maps, such as a map based on functions and 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 的对数.充其量，对于初学者中级的函数式程序员来说，这是一个不错的学术练习，只是为了了解如何用函数表示事物.

Unfortunately, this isn’t just infinite semantically: as you add or remove key–value pairs, it also grows infinitely in memory! This is because the entries are a linked list of closures, not reified as a data structure: you can only remove values from the map by adding an entry indicating their removal, like a reversion in a version control system. It’s also very inefficient for lookups, which are linear in the number of keys, rather than logarithmic for Map. At best it’s an okay academic exercise for a beginner-intermediate functional programmer, just to get a feel for how to represent things with functions.

这里有一个简单的替代方法是默认映射"，它将不存在的键映射到一个恒定值.

A simple alternative here is a "default map" that maps nonexistent keys to a constant value.

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 的实现很简单:现有键的交集以及默认情况下应用的不存在的键.

Then the implementation of Applicative is straightforward: the intersection of the existing keys, plus the nonexistent keys applied with the default.

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(也许是v)恢复默认值 Nothing 且不变量为 Map 的部分行为.总是将定义的键映射到 Just .

DefaultMap is slightly unusual in that you can delete key–value pairs, but only by effectively "resetting" them to their default value, in that a lookup for a given key will always succeed even after a deletion of that same key. Although you can of course recover something resembling the partial behaviour of Map using DefaultMap k (Maybe v) with a default of Nothing and an invariant of always mapping defined keys to Just.

我认为还有一个 instance Monad(DefaultMap k)，通过与 instance Monad((->)k)同构 instance Monad(Stream k)，因为像 Stream 一样， DefaultMap 总是 无限，而可能是有限的 ZipList 不能具有 Monad 实例，因为它确实违反了关联性法则 a> =>(b> => c) = (a> => b)> =>c .

I think there’s also an instance Monad (DefaultMap k), by isomorphism with instance Monad ((->) k) or instance Monad (Stream k), since like Stream, a DefaultMap is always infinite—whereas the possibly-finite ZipList can’t have a Monad instance because it necessarily violates the associativity law a >=> (b >=> c) = (a >=> b) >=> c.

这篇关于实现字典的适用实例(地图，关联数组)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！