函数组合 VS 函数应用

Question

1. 谁能给出函数组合的例子吗？

2. 这是函数复合运算符的定义？

   (.) :: (b -> c) -> (a→b)→一个-> c
   f. g = \x ->; f(gx)
   

这表明它需要两个函数并返回一个函数，但我记得有人用英语表达了逻辑，就像

男孩是人类 ->阿里是男孩-> ali 是人类

1. 这个逻辑与函数组合有什么关系？
2. 函数应用和组合的强绑定是什么意思？哪个比另一个强绑定？

请帮忙。

谢谢。

Answer 1

（编辑1：我第一次错过了你问题的几个组成部分；请参阅我答案的底部。）

思考此类陈述的方法是查看类型。你所拥有的论证形式称为三段论。但是，我认为你记错了一些事情。三段论有很多种，据我所知，你的三段论并不对应于函数组合。让我们考虑一种三段论：

1. 如果外面阳光明媚，我就会变热。
2. 如果我热了，我就去游泳。
3. 因此，如果天气晴朗，我就会去游泳。

这称为假设三段论。用逻辑术语来说，我们可以这样写：让S代表命题“天气晴朗”，让H代表命题“我会变热” ，并让 W 代表命题“我会去游泳”。写α→β表示“α意味着β”，写∴表示“因此”，我们可以翻译以上为：

1. S → H
2. H → W
3. ∴ S → W

当然，如果我们将 S、H 和 W 替换为任意 α，则此方法有效em>、β 和 γ。现在，这看起来应该很熟悉。如果我们将蕴含箭头 → 更改为函数箭头 ->，则变为

1. a -> b
2. b -> c
3. ∴ a -> 你瞧

，我们有了复合运算符类型的三个组成部分！要将其视为逻辑三段论，您可以考虑以下内容：

1. 如果我有一个 a 类型的值，我可以生成一个 b 类型的值。
2. 如果我有一个 b 类型的值，我可以生成一个 c 类型的值。
3. 因此，如果我有一个 a 类型的值，我可以生成一个 c 类型的值。

这应该是有意义的：在 f 中。 g，存在一个函数g::a -> b 告诉您前提 1 为真，并且 f :: b -> c 告诉您前提 2 为真。因此，您可以得出最终语句，其中函数 f 。 g::a-> c 是一个见证人。

我不完全确定你的三段论意味着什么。它几乎是 modus ponens 的一个实例，但不完全是。后件论证采用以下形式：

1. 如果下雨，那么我就会被淋湿。
2. 正在下雨。
3. 因此，我会被淋湿。

写R表示“正在下雨”，写W表示“我会被淋湿”，这给了我们逻辑形式

1. R→ >W
2. R
3. ∴ W

将蕴含箭头替换为函数箭头，得到以下结果：

1. a -> b
2. a
3. ∴ b

这就是简单的函数应用，从 ($) :: (a ->; b)->一个-> b.。如果您想将其视为逻辑参数，它可能采用以下形式：

1. 如果我有一个 a 类型的值，我可以生成一个 b 类型的值。
2. 我有一个 a 类型的值。
3. 因此，我可以生成 b 类型的值。

这里，考虑表达式f x。函数f :: a -> b 是命题 1 真实性的见证人；值x :: a是命题2真实性的见证；因此结果可以是b类型，证明了结论。这正是我们从证明中发现的。

现在，您最初的三段论采用以下形式：

1. 所有男孩都是人类。
2. 阿里是个男孩。
3. 因此，阿里是人。

让我们把它翻译成符号。 Bx 表示x 是一个男孩； Hx 表示 x 是人类； a 表示 Ali；和 ∀x。 φ 表示 φ 对于 x 的所有值都成立。那么我们就有

1. ∀x。 Bx → Hx
2. Ba
3. ∴ Ha

这几乎是肯定的做法，但它需要实例化 forall。虽然逻辑上有效，但我不确定如何在类型系统级别解释它；如果有人想帮忙，我洗耳恭听。一种猜测是像 (forall x.B x -> H x) -> H 这样的 2 级类型。 Ba-> H a，但我几乎可以肯定这是错误的。另一种猜测是更简单的类型，例如 (B x -> H x) -> B 内部 -> H Int，其中 Int 代表 Ali，但我几乎可以肯定这是错误的。再次强调：如果你知道，也请告诉我！

最后一点。以这种方式看待事物——遵循证明和程序之间的联系——最终会导致 的深层魔力库里-霍华德同构，但这是一个更高级的主题。 （不过，这真的很酷！）

---

编辑 1： 您还要求提供函数组合的示例。这是一个例子。假设我有一个人们的中间名列表。我需要构建所有中间名缩写的列表，但要做到这一点，我首先必须排除每个不存在的中间名。很容易排除所有中间名为空的人；我们只是用过滤器（\mn -> not $ null mn）middleNames包含所有中间名不 null 的人。同样，我们可以使用 head 轻松获取某人的中间名首字母，因此我们只需要 map headfilteredMiddleNames 即可获取列表。换句话说，我们有以下代码：

allMiddleInitials :: [Char]
allMiddleInitials = map head $ filter (\mn -> not $ null mn) middleNames

但这是令人恼火的具体；我们确实想要一个中间名首字母生成函数。因此，让我们将其更改为：

getMiddleInitials :: [String] -> [Char]
getMiddleInitials middleNames = map head $ filter (\mn -> not $ null mn) middleNames

现在，让我们看一些有趣的事情。函数 map 的类型为 (a -> b) -> [一]-> [b]，并且由于 head 的类型为 [a] -> a，map head 的类型为 [[a]] -> [a]。类似地，filter 的类型为 (a -> Bool) -> [一]-> [a]，因此 filter (\mn -> not $ null mn) 的类型为 [a] -> [a]。因此，我们可以去掉这个参数，而是写成

-- The type is also more general
getFirstElements :: [[a]] -> [a]
getFirstElements = map head . filter (not . null)

你会看到我们有一个额外的组合实例： not has type Bool -> Bool，并且 null 的类型为 [a] -> Bool，所以不是。 null 的类型为 [a] -> Bool：它首先检查给定列表是否为空，然后返回是否不为空。顺便说一句，这个转换将函数更改为 point-free 风格；也就是说，结果函数没有显式变量。

您还询问了“强绑定”。我认为您指的是 . 和 $ 运算符（也可能是函数应用程序）的优先级。在 Haskell 中，就像在算术中一样，某些运算符比其他运算符具有更高的优先级，因此绑定得更紧密。例如，在表达式 1 + 2 * 3 中，它被解析为 1 + (2 * 3)。这是因为在 Haskell 中，以下声明有效：

infixl 6 +
infixl 7 *

数字越大（优先级），调用该运算符越早，因此该运算符绑定得越紧密。函数应用实际上具有无限优先级，因此它绑定最紧密：对于任何运算符 %，表达式 fx % g y 将解析为 (fx) % (gy)。 . （组合）和 $ （应用程序）运算符具有以下固定性声明：

infixr 9 .
infixr 0 $

优先级范围从 0 到 9，因此这表示 . 运算符的绑定比任何其他运算符（函数应用程序除外）更紧密，而 $ 的绑定不那么紧密。因此，表达式 f 。 g $ h 将解析为 (f . g) $ h;事实上，对于大多数运算符来说，f 。 g % h 将是 (f . g) % h 并且 f % g $ h 将是 f % (g $ h)代码>. （唯一的例外是极少数其他零或九个优先级运算符。）