为什么 fmap 必须映射列表的每个元素？

Question

看完书Learn you a Haskell For Great Good, and the very helpful wiki book article Haskell Category Theory which helped me overcome the common category mistake ，我还有以下问题：

为什么必须 fmap 映射列表的每个元素？

我喜欢它，我只是想了解这在理论上如何合理。（或者也许使用 HoTT 更容易证明其合理性？）

在 Scala 表示法中，List 是一个函子，它接受任何类型并将其映射到所有列表类型集合中的一个类型，例如它将类型 Int 映射到类型 List[Int] 并将函数映射到 Int 例如

Int.successor: Int => Int 到 Functor[List].fmap(successor) : List[Int] => List[Int]
Int.toString: Int => String 到 Functor[List].fmap(toString): List[Int] => List[String]

现在 List[X] 的每个实例都是一个带有 empty function (mempty in Haskell) and combine function (mappend in Haskell). My guess is that one can use the fact that Lists are Monoids, to show that map has to map all elements of a list. My feeling here is that if one adds the pure function from Applicative 的幺半群，这给了我们一个列表，其中只有一个其他类型的元素。例如 Applicative[List[Int]].pure(1) == List(1)。由于这些元素上的 map(succ) 为我们提供了带有下一个元素的单例列表，因此这涵盖了所有这些子集。然后我假设所有这些单例上的 combine 函数为我们提供了列表的所有其他元素。我想这会以某种方式限制 map 的工作方式。

另一个暗示性的论点是 map 必须在列表之间映射函数。由于 List[Int] 中的每个元素都是 Int 类型，如果映射到 List[String] 则必须映射它的每个元素，否则类型不正确。

所以这两个论点似乎都指向了正确的方向。但我想知道完成剩下的路需要什么。

反例?

为什么这不是反例映射函数？

def map[X,Y](f: X=>Y)(l: List[X]): List[Y] = l match {
  case Nil => Nil
  case head::tail=> List(f(head))
}

好像很守规矩

val l1 = List(3,2,1)
val l2 = List(2,10,100)

val plus2 = (x: Int) => x+ 2
val plus5 = (x: Int) => x+5

map(plus2)(List()) == List()
map(plus2)(l1) == List(5)
map(plus5)(l1) == List(8)

map(plus2 compose plus5)(l1) == List(10)
(map(plus2)_ compose map(plus5)_)(l1) == List(10)

啊。但是不符合id法。

def id[X](x: X): X = x

map(id[Int] _)(l1) == List(3)
id(l1) == List(3,2,1)

Answer 1

这依赖于一个名为 "parametricity" 的理论结果，该结果首先由 Reynolds 定义，然后由 Wadler（以及其他人）开发。也许关于这个主题最著名的论文是 Wadler 的 "Theorems for free!"。

关键思想是，从函数的多态类型仅，我们可以得到一些关于函数语义的信息。例如：

foo :: a -> a

单从这个类型可以看出，如果foo终止，就是恒等函数。直觉上，foo 无法区分不同的 a，因为在 Haskell 中我们没有例如Java 的 instanceof 可以检查实际的运行时类型。同样，

bar :: a -> b -> a

必须 return 第一个参数。 baz :: a -> a -> a 必须 return 第一个或第二个。 quz :: a -> (a -> a) -> a 必须将函数应用于第一个参数的固定次数。你现在可能明白了。

一般的属性可以从一个类型推断出来是相当复杂的，但幸运的是可以计算mechanically. In category-theory, this is related to the notion of natural transformation.

对于map类型，我们得到以下可怕的属性：

forall t1,t2 in TYPES, f :: t1 -> t2.
 forall t3,t4 in TYPES, g :: t3 -> t4.
  forall p :: t1 -> t3.
   forall q :: t2 -> t4.
    (forall x :: t1. g (p x) = q (f x))
    ==> (forall y :: [t1].
          map_{t3}_{t4} g (map2_{t1}_{t3} p y) =
          map2_{t2}_{t4} q (map_{t1}_{t2} f y))

上面，map 是众所周知的 map 函数，而 map2 是类型为 (a -> b) -> [a] -> [b].

的任意函数

现在，进一步假设 map2 满足函子定律，特别是 map2 id = id。然后我们可以选择p = id和t3 = t1。我们得到

forall t1,t2 in TYPES, f :: t1 -> t2.
 forall t4 in TYPES, g :: t1 -> t4.
   forall q :: t2 -> t4.
    (forall x :: t1. g x = q (f x))
    ==> (forall y :: [t1].
          map_{t1}_{t4} g (map2_{t1}_{t1} id y) =
          map2_{t2}_{t4} q (map_{t1}_{t2} f y))

在 map2 上应用函子定律：

forall t1,t2 in TYPES, f :: t1 -> t2.
 forall t4 in TYPES, g :: t1 -> t4.
   forall q :: t2 -> t4.
    (forall x :: t1. g x = q (f x))
    ==> (forall y :: [t1].
          map_{t1}_{t4} g y =
          map2_{t2}_{t4} q (map_{t1}_{t2} f y))

现在，让我们选择 t2 = t1 和 f = id:

forall t1 in TYPES.
 forall t4 in TYPES, g :: t1 -> t4.
   forall q :: t1 -> t4.
    (forall x :: t1. g x = q x)
    ==> (forall y :: [t1].
          map_{t1}_{t4} g y =
          map2_{t1}_{t4} q (map_{t1}_{t1} id y))

根据map的函子定律：

forall t1, t4 in TYPES.
   forall g :: t1 -> t4, q :: t1 -> t4.
    g = q
    ==> (forall y :: [t1].
          map_{t1}_{t4} g y =
          map2_{t1}_{t4} q y)

这意味着

forall t1, t4 in TYPES.
 forall g :: t1 -> t4.
    (forall y :: [t1].
          map_{t1}_{t4} g y =
          map2_{t1}_{t4} g y)

这意味着

forall t1, t4 in TYPES.
          map_{t1}_{t4} = map2_{t1}_{t4}

总结：

如果map2是任何具有多态类型(a -> b) -> [a] -> [b]的函数，并且满足第一函子定律map2 id = id，则map2必须等价于标准map 函数。

又见一个related blog post by Edward Kmett.

请注意，在 Scala 中，仅当您不使用 x.isInstanceOf[] 和其他可能破坏参数化的反射工具时，以上内容才成立。

为什么 fmap 必须映射列表的每个元素？

Why must fmap map every element of a List?

haskell

functor

category-theory

scalaz

scala-cats