正如人们在评论中指出的那样，您无法实现有效的Applicative实例为Map因为你无法实施pure以守法的方式。由于同一律，pure id <*> v = v, the pure实现需要维护所有键，同时将映射与函数应用程序相交。您不能对部分映射执行此操作，因为根据参数化，您可能在一个映射或另一个映射中没有用于构造函数的键a -> b或论证a你需要制作一个b在生成的地图中。pure x需要像那个一样工作ZipList（它使用repeat），生成映射的地图every相同值的键x，但这不可能Map因为它是有限的。然而，它is可以使用允许无限映射的替代表示，例如基于函数和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)
不幸的是，这不仅仅是语义上无限的：正如你添加的或删除键值对，它也grows无限在记忆中！这是因为条目是闭包的链接列表，而不是具体化为数据结构：您只能通过以下方式从映射中删除值adding指示它们被删除的条目，就像版本控制系统中的恢复一样。查找的效率也非常低，查找的效率与键的数量成线性关系，而不是对数关系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有点不寻常的是你can删除键值对，但只能通过有效地将它们“重置”为其默认值，因为即使删除同一键后，对给定键的查找也始终会成功。虽然你当然可以恢复类似于部分行为的东西Map using DefaultMap k (Maybe v)默认为Nothing以及始终将定义的键映射到的不变量Just.
I think还有一个instance Monad (DefaultMap k)，通过同构instance Monad ((->) k) or instance Monad (Stream k)，因为喜欢Stream, a DefaultMap is always无限——而可能有限ZipList不能有Monad实例，因为它必然违反结合律a >=> (b >=> c) = (a >=> b) >=> c.
