类型实例的功能 [英] Typeclass instances for functions

问题描述

我通常会这样做，当我看到一些类型实例时，我不知道得到，是写一些良好类型的表达式，看看它返回什么：

有人可以解释这些实例吗？你通常会听到关于List和Maybe的实例，这些实例现在对我来说很自然，但我不明白函数如何成为Functor甚至是Monad。

编辑：
好​​的，这是一个不能编译的有效良好类型表达式：

  fmap（+ ）（+）1（+1）1 
  

解决方案

，我同意你的看法：函数不是很直观的函数，事实上我有时希望这些实例不在那里。这并不是说他们有时候并没有用处，但是他们经常以不必要和混乱的方式使用它们。这些方法总是可以替换为更具体的组合器（特别是 Control.Arrow ），或者用等价的但更方便描述的 reader monad 。

这就是说...要理解functor的函数，我建议你先考虑 Map 。在某种意义上， Map Int 与数组非常相似：它包含一些可以转换的元素（即<$​​ c $ c> fmap 以上），并且可以通过用整数索引它们来访问各个元素。 Map 只允许数组存在空位，并且从整数索引到任何可以排序的索引。

在另一个视图中， Map 仅仅是一个函数的具体实现：它将参数（键）与结果（值）。这应该很清楚函数functor 的工作原理：它覆盖函数的所有可能结果。

不幸的是，这个解释并没有太多解释 Monad 实例，因为 Map 实际上并没有monad （甚至不是 Applicative ）实例。直接调整列表/数组的实现实际上是不可能的...回顾：在列表中，我们有

 纯x ≡[x] 
（，）< $> [a，b] * （a，x），（a，y），（a，z），（b，x），（b，y），（b，z）] 
  

所以在合并之后，指数都是不同的。对于我们想要支持通用键的 Map 来说，这是行不通的。

然而，还有一个替代monad实例对于列表， zip列表：

 纯x≡重复x 
（，） < $> [a，b] * [x，y，z]≡[（a，x），（b，y）] 
  

注意元素的索引被保留。

现在这个实例实际上可以适用于 Map ，if只有 repeat :: a - >映射k a 生成器。这是不存在的，因为一般情况下有无数个密钥，我们不能枚举它们，也不能平衡这样一个 Map 需要的无限树。但是，如果我们仅限于只有很多可能值的关键类型（例如 Bool ），那么我们很好：

 实例Applicative（Map Bool）其中
 pure x = Map.fromList [（False，x），（True，x）] 
 <* > = Map.intersectWith（$）
  

现在，monad函数就是如此， code> Map 如果无限多个不同的参数都是可能的，那么这是没有问题的，因为您从来没有试图用关联的值存储它们。而是你总是只能当场计算出价值。

---

^† _{如果它没有被懒惰地完成 - 在Haskell中几乎不成问题，事实上，如果你通过 Map 的fmap，它也会发生懒惰。对于函数functor， fmap 实际上不是懒惰，但结果也会立即被遗忘，需要重新计算。}

I've just realized, that Functions have instances for Monad, Functor and Applicative.

What I usually do, when I see some typeclass instance I don't get, is write some well-typed expression and see what it returns:

Can somebody explain these instances? You usually hear about the instances for List and Maybe, which by now are natural to me, but I don't understand how Functions can be a Functor or even a Monad.

EDIT: Okay, this is a valid well-typed expression that doesn't compile:

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

解决方案

First, I agree with you: functions are not very intuitive as functors, and indeed I sometimes wish these instances weren't there. It's not that they aren't useful sometimes, but quite as often they're used in a needless and confusing manner. These methods can always be replaced with either more specific combinators (in particular from Control.Arrow), or with the equivalent but somehow much more descriptive reader monad.

That said... to understand the function functor, I suggest you first consider Map. In a way, Map Int is a lot like an array: it contains some elements that you can transform (i.e. fmap over), and you can access individual elements by indexing them with integers. Map just allows the "array" to have gaps in it, and generalises from integer-indices to any sort of index that can be ordered.

On another view though, Map is just a specific implementation of a function: it associates arguments (keys) to results (values). And that should make it quite clear how the function functor works: it fmaps over all possible results^† of the function.

This explanation unfortunately doesn't much explain the Monad instance, because Map doesn't actually have a monad (nor even Applicative) instance. A direct adaption of the list/array implementation would indeed not be possible... recap: on lists, we have

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

so after combining, the indices are all different. That can't work for Map where we want to support generic keys.

However, there's an alternative monad instance for list, the zip list:

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

Notice that the indices of the elements are preserved.

Now this instance could in fact be adapted for Map, if only there was a repeat :: a -> Map k a generator. This doesn't exist because in general there are infinitely many keys and we can't enumerate them all nor balance the infinite tree that such a Map would entail. But if we restrict ourselves to key types with only finitely many possible values (such as Bool), then we're good:

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

Now, that's exactly how the function monad works, just unlike with Map there's no problem if infinitely many different arguments are possible, because you never attempt to store all of them with associated values; rather you always only compute the values on the spot.

---

^†_{That would be infeasible if it weren't done lazily – which in Haskell is hardly a problem, in fact if you fmap over a Map it also happens lazily. For the function functor, fmap is actually not just lazy but the result is also immediately forgotten and needs to be recalculated.}

这篇关于类型实例的功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！