为字典(映射、关联数组)实现 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
= 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
.
为关联数组实现仿函数实例(本质上是映射操作)似乎很简单(例如,参见 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
= 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
.