`(a -> b) -> (c -> d)` in Haskell?

Question

这是又一个通过范畴论来解释 Haskell 的问题。

让我们以一些简单而广为人知的东西为例。fmap？所以，省略了 f 实际上是一个 Functor 这个事实，有 fmap :: (a -> b) -> f a -> f b。据我所知，(a -> b) -> f a -> f b 只不过是 (a -> b) -> (f a -> f b) 的语法糖；因此得出结论：

(1) fmap 是一个生成函数的函数。

现在，Hask 也包含函数，所以 (a -> b)，特别是 (f a -> f b)，是 Hask 的一个对象（因为 Hask 的对象是明确定义的 Haskell 类型 - 即数学集合 - 并且确实存在类型为 (a -> b) 的集合，对于每个可能的 a，对吧？）。所以，再次强调：

(2) (a -> b) 是 Hask 的一个对象。

现在奇怪的事情发生了：显然，fmap 是 Hask 的一个态射，因此它是一个函数，它接受另一个函数并将其转换为另一个函数；最终的函数尚未应用。

因此，需要另一个 Hask 的态射才能从 (f a -> f b) 得到 f b。对于类型为 a 的每个项目 i，存在一个定义为 \f -> f (lift i) 的态射 apply_i :: (f a -> f b) -> f b，其中 lift i 是一种构建具有特定 i 的 f a 的方法。

另一种看待它的方式是 GHC 风格：(a -> b) -> f a -> f b。与我上面写的相反，(a -> b) -> f a 将映射到 Hask 的常规对象。但这种观点违背了 Haskell 的基本公理 - 没有多元函数，只有应用（柯里化）的替代方案。

我想在这一点上问一下： (a -> b) -> f a -> f b 应该是一个 (a -> b) -> (f a -> f b) -> f b，为了简单起见而使用的语法糖，还是我漏掉了非常、非常重要的东西？

- Zazaeil

---

评论不适合进行长时间的讨论；此对话已被移至聊天室。 - Samuel Liew

Answer 1

“（a -> b）-> f a -> f b”并不是简化的“（a -> b）->（f a -> f b）-> f b”，我认为你所缺少的，这并不是你的错，是因为只有在特定情况下，“（a -> b）->（f a -> f b）”中的中间箭头才能像外部的“(a -> b) -> (f a -> f b)”一样被称为同态。Functor类的一般情况将是（伪语法）

class (Category (──>), Category (~>)) => Functor f (──>) (~>) where
  fmap :: (a ──> b) -> f a ~> f b

因此，它将类别中箭头表示为──>的态射映射到类别~>中的态射，但是这个态射映射本身只是一个普通的函数。你是对的，在Hask中，函数箭头和态射箭头是相同类型的箭头，但从数学上讲，这是一个相当退化的情况。

- leftaroundabout

---

是的，同意，你的例子非常明确，但对于编程语言来说有些冗余。但为什么不默认更加明确，并强制 GHC 引用 (a -> b) -> (f a -> f b) 呢？(a -> b) -> f a -> f b 是一种非常不寻常的符号滥用！ - Zazaeil

这并不是滥用符号，只是在直觉上没有其他常见的右结合、非交换操作符可用。(a -> b) -> f a -> f b 的意思是非常明确的，不存在任何歧义。因为它是右结合的，所以唯一可能的解析是（转换为前缀表示法）(->) (a -> b) ((->) (f a) (f b))。 - chepner

@SerejaBogolubov，你是否也认为 3 * 4 * 5 是符号滥用，我们应该被迫写成 (3 * 4) * 5 或者 3 * (4 * 5)？那 1 - 2 - 3 或者 f $ g $ x 呢？如果你认为默认情况下运算符结合方式在计算级别是可以理解的，那么在类型级别为什么不呢？ - Daniel Wagner

@DanielWagner，请查看另一个答案下的评论。这解决了所有问题。 - Zazaeil

@DanielWagner 3 * 4 * 5 不是一个好的比喻，因为即使没有运算符结合的概念，它也是无歧义的。(至少对于精确算术来说。) - leftaroundabout

Answer 2

fmap实际上是一组态射。在Hask中，一个态射总是从一个具体类型到另一个具体类型。如果一个函数有具体的参数类型和返回类型，你可以将该函数视为一个态射。类型为Int -> Int 的函数表示从Int到Int的态射（实际上是一个自同态）。然而，fmap的类型为Functor f => (a -> b) -> f a -> f b，没有具体的类型！我们只有类型变量和伪运算符=>。

考虑以下一组具体的函数类型。

Int -> Int
Char -> Int
Int -> Char
Char -> Char

此外，请考虑以下类型构造器

[]
Maybe

[] 应用于 Int 返回一个我们可以称之为 List-of-Ints 的类型，但我们通常只称之为 [Int]。（当我刚开始接触函子时最令人困惑的事情之一是，我们没有单独的名称来指代各种类型构造器产生的类型；输出只是由评估为其的表达式命名。）Maybe Int 返回我们只称之为 Maybe Int 的类型。

现在，我们可以定义一堆像下面这样的函数：

fmap_int_int_list :: (Int -> Int) -> [Int] -> [Int]
fmap_int_char_list :: (Int -> Char) -> [Int] -> [Char]
fmap_char_int_list :: (Char -> Int) -> [Char] -> [Int]
fmap_char_char_list :: (Char -> Char) -> [Char] -> [Char]
fmap_int_int_maybe :: (Int -> Int) -> Maybe Int -> Maybe Int
fmap_int_char_maybe :: (Int -> Char) -> Maybe Int -> Maybe Char
fmap_char_int_maybe:: (Char -> Int) -> Maybe Char -> Maybe Int
fmap_char_char_maybe :: (Char -> Char) -> Maybe Char -> Maybe Char

每个都是在Hask中的不同态射，但当我们用Haskell定义它们时，会有很多重复。

fmap_int_int_list f xs = map f xs
fmap_int_char_list f xs = map f xs
fmap_char_int_list f xs = map f xs
fmap_char_char_list f xs = map f xs
fmap_int_int_maybe f x = case x of Nothing -> Nothing; Just y -> Just (f y)
fmap_int_char_maybe f x = case x of Nothing -> Nothing; Just y -> Just (f y)
fmap_char_int_maybe f x = case x of Nothing -> Nothing; Just y -> Just (f y)
fmap_char_char_maybe f x = case x of Nothing -> Nothing; Just y -> Just (f y)

当f的类型不同时，定义不会有所不同，只有当x/xs的类型不同时才会有所不同。这意味着我们可以定义以下的多态函数

fmap_a_b_list f xs = map f xs
fmap_a_b_maybe f x = case x of Nothing -> Nothing; Just y -> Just (f y)

每个 Hask 中都代表着一组态射，fmap 本身是我们用来指代由所有多态函数引用的构造特定的态射的一个总称。

有了这个基础，我们可以更好地理解 fmap :: Functor f => (a -> b) -> f a -> f b。

给定 fmap f，我们首先关注 f 的类型。例如，我们可能会发现 f :: Int -> Int，这意味着 fmap f 必须返回 fmap_int_int_list 或者 fmap_int_int_maybe 中的一种，但我们还不确定是哪个。所以它返回一个受限的函数，类型为 Functor f => (Int -> Int) -> f Int -> f Int。一旦将该函数应用于类型为 [Int] 或 Maybe Int 的值，我们就会最终得到足够的信息来知道实际上使用了哪个态射。

- chepner

---

@SerejaBogolubov 这只是符号上的便利问题。暂时不考虑 fmap，写 (+) :: Num a => a -> a -> a 要比写 (+) :: Num a => a -> (a -> a) 更方便，写 foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b 要比写 foldr :: Foldable t => (a -> (b -> b)) -> (b -> (t a -> b)) 更方便。 - duplode

如果你故意忽略 -> 运算符的结合性，那么它只能被解释为那样。不要那样做！ 你会抱怨 1 + 2 * 3 可以被解释为 (1+2)*3 == 9 吗？不会，因为你不会忽略 * 的高优先级。 - chepner

涉及Haskell类型签名语法的问题并不纯粹涉及范畴论。 - duplode

但是，fmap 不是一个箭头，因此这个简单的替换方法并不适用。从范畴论的角度来看，有两个独立的附加函子，我们选择将它们“合并”为单个操作符 (->)。您可能希望阅读 https://bartoszmilewski.com/2015/03/13/function-types/，其中详细解释了函数类型实际上是什么，并提到了 curry 和 uncurry。(在Zmilewski的书中，还讨论了关于如何应用附加函子的问题，但我暂时忘记在哪里了。) - chepner

谢谢@chepner - 我错过了那一点，并且仍然不太确定，但我一定会阅读那篇看起来有趣的文章！ - Robin Zigmond

Answer 3

现在发生了奇怪的事情：显然，fmap是Hask的一个同态，因此它是一个函数，可以接受另一个函数并将其转换为另一个函数；最终函数尚未应用。因此，需要另一个Hask的同态才能从（f a->f b）到达f b。对于类型a的每个项i，都存在一个同态apply_i ::（f a->f b）-> f b，定义为\f-> f（lift i），其中lift i是一种构建具有特定i的f a的方法。

范畴论中的应用概念以CCC's - Cartesian Closed Categories的形式进行建模。如果您拥有自然双射（X×Y，Z）≅（X，Y⇒Z），则类别是CCC。

特别是这意味着存在一个自然变换（评估），其中[Y，Z]：（Y⇒Z）×Y→Z，使得对于每个g:X×Y→Z，都存在一个g:X→（Y⇒Z），使得g = g×id; [Y，Z]。因此，当你说，

因此，需要一个额外的Hask的态射才能从（f a -> f b）到达f b。

你从（fa ⇒ fb）到fb的方式是通过[f a，f b]：（f a ⇒ f b）× fa → fb。

另一个重要的要点是，在范畴论中，“元素”不是原始概念。相反，元素是形式为→X的箭头，其中是终端对象。如果您取X=，则有(Y，Z)≅(×Y，Z)≅(，Y⇒Z)。也就是说，映射g:Y→Z与元素g:→（Y⇒Z）一一对应。

在Haskell中，这意味着函数恰好是箭头类型的"元素"。因此，在Haskell中，应用程序h y将通过对y:→Y进行的h:→(Y⇒Z)的评估来建模。也就是说，(h)×y:→(Y⇒Z)×Y的评估，它由组合(h)×y;[Y,Z]:→Z给出。

- Jorge Adriano Branco Aires

Answer 4

为了完整起见，本答案重点关注了评论中提到但其他回答没有涉及的一个问题。

引用如下：

另一种看待它的方式是 GHC 风格：(a -> b) -> f a -> f b。与我上面写的相反，(a -> b) -> f a 映射到 Hask 的常规对象。

类型签名中的 -> 是右结合的。因此，(a -> b) -> f a -> f b 实际上与 (a -> b) -> (f a -> f b) 相同，将 (a -> b) -> f a 视为其中的一部分是一种语法混淆。这与...无异。

(++) :: [a] -> [a] -> [a]

并不意味着部分应用 (++) 会给我们一个 [a] 列表（相反，它会给我们一个在某些列表前面添加元素的函数）。

从这个角度来看，您提出的范畴论问题（例如，“需要一种更多的 Hask 的态射才能从 (f a -> f b) 到 f b”）是一个单独的问题，Jorge Adriano 在 他的回答 中很好地解决了。

- duplode