function - 函数的类型类实例

Question

我刚刚意识到，Functions 有 Monad、Functor 和 Applicative 的实例。

当我看到一些我没有得到的类型类实例时，我通常做的是编写一些类型良好的表达式并查看它返回的内容:

有人可以解释这些情况吗？您通常听说过 List 和 Maybe 的实例，这对我来说已经很自然了，但我不明白 Functions 如何成为 Functor 甚至 Monad。

编辑:好的，这是一个有效的类型良好的表达式，但无法编译:

fmap (+) (+) 1 (+1) 1

Answer 1

首先，我同意你的看法:函数不像仿函数那样直观，事实上我有时希望这些实例不存在。并不是说它们有时没有用，而是它们经常以不必要和令人困惑的方式使用。这些方法总是可以替换为更具体的组合器(特别是来自 Control.Arrow)，或者替换为等效的但不知何故更具描述性的 reader monad .

也就是说...要了解函数仿函数，我建议您首先考虑 Map .在某种程度上，Map Int 很像一个数组:它包含一些您可以转换的元素(即 fmap over)，您可以通过 用整数索引它们。 Map 只允许“数组”中有间隙，并将整数索引推广到任何可以排序的索引。

但从另一个角度来看，Map 只是函数 的特定实现:它将参数(键)与结果(值)相关联。这应该很清楚函数仿函数是如何工作的:它映射函数的所有可能结果^†。

不幸的是，这个解释并没有太多解释 Monad 实例，因为 Map 实际上没有 monad(甚至 Applicative)实例。列表/数组实现的直接改编确实是不可能的……回顾一下:在列表上，我们有

pure x ≡ [x]
(,) <$> [a,b] <*> [x,y,z] ≡ [(a,x),(a,y),(a,z),(b,x),(b,y),(b,z)]

所以合并后，索引都是不同的。这不适用于我们想要支持通用键的 Map。

但是，列表有一个替代的 monad 实例，zip 列表:

pure x ≡ repeat x
(,) <$> [a,b] <*> [x,y,z] ≡ [(a,x),(b,y)]

请注意，元素的索引已保留。

现在这个实例实际上可以适用于 Map，只要有一个 repeat::a -> Map k a 生成器就好了。这是不存在的，因为通常有无限多个键，我们无法枚举所有键，也无法平衡这样一个 Map 需要的无限树。但是，如果我们将自己限制在只有有限多个可能值的键类型(例如 Bool)，那么我们就很好:

instance Applicative (Map Bool) where
  pure x = Map.fromList [(False, x), (True, x)]
  <*> = Map.intersectWith ($)

现在，这正是函数 monad 的工作方式，与 Map 不同的是，如果可能有无限多不同的参数也没有问题，因为您永远不会尝试存储所有 具有关联值；相反，您总是只在现场计算值。

---

^†_{如果不是懒惰地完成那将是不可行的——这在 Haskell 中几乎不是问题，事实上如果你在 Map 上进行 fmap也懒惰地发生。对于function functor，fmap其实不只是偷懒，结果也马上被遗忘，需要重新计算。}