混淆理解 Substitution / `ap` 类型签名和不同的实现（函数式编程）

Question

我是函数式编程的学生，如果我的问题听起来很奇怪，我深表歉意——我正在努力思考函数的给定类型签名及其实现方式。

正在查看 ap（替换）

的签名

https://gist.github.com/Avaq/1f0636ec5c8d6aed2e45

(a → b → c) → (a → b) → a → c

此处给出为

const S = f => g => x => f(x)(g(x));

我想我明白了。 f 是一个带有两个参数的函数，a 和 b 以及 returns c。 g 是一个接受 a 和 returns b 的函数。所以 g(a) returns b 因此 f(a)(b) 可以写成 f(a)(g(a))，即 returns c。

g(a) 是 b 的替代品吗？

好的，现在我正在寻找一个仍然有意义的不同实现：

https://github.com/sanctuary-js/sanctuary-type-classes/tree/v7.1.1#ap--applyf--fa-bfa---fb

ap(Identity(Math.sqrt), Identity(64))

类型签名

(f (a -> b), f a) -> f b

看起来类似于

(a → b → c) → (a → b) → a → c

使用 a = f、b = a 和 c = b 重写第二个我得到

(f -> a -> b) -> (f -> a) -> f -> b

假设 ap 有两个参数，其中第一个 f 可能是一些包含函数 a -> b 的仿函数，第二个 f 是一些包含函数 a -> b 的仿函数包含 a 返回一个函子，该函子将第一个函子的函数替换为给定的终点 b 然后函子包含 a.

好吧，退一步说，这两件事看起来截然不同，我无法理解他们怎么说的是同一件事。

const S = f => g => x => f(x)(g(x))
ap(Identity(Math.sqrt), Identity(64))

根据我的理解，ap(F(g),F(a)) 可以表示为 F(a).map(g)，同样，我仍然很难等同于 const S = f => g => x => f(x)(g(x))。也许我误解了什么。

...也许我的误解与 ap 的表达方式有关，以及它与 f => g => x => f(x)(g(x)) 的关系，因为我可以看到它们如何表达相同的签名，但我没有看到他们是一样的。

谁能在这里提供一些认知帮助，我将不胜感激

Answer 1

ap 是一种转换的名称，它在大量称为 Applicative Functors 的容器类型上表现相同。一种这样的容器类型是函数：它可以被视为其return值的容器。

您在我的要点中找到的 S 组合子来自无类型的 Lambda 微积分，是函数的转换 具体来说 。它恰好也是 Applicative Functor for Function 的有效实现，它恰好是 Ramda 和 Sanctuary 的首选实现。这就是为什么您可以将 ap 用作 S.

要了解 ap 是如何 S，让我们看一下 ap 的签名：

Apply f => (f (a -> b), f a) -> f b

让我们通过柯里化函数来去掉逗号。这应该会让接下来的步骤更容易理解：

Apply f => f (a -> b) -> f a -> f b

Apply f 部分表明，在我们看到 f a 的地方，我们可以使用包含 a 的 Applicative Functor 容器。让我们通过将 f 替换为 (Function x) 来将此签名专门用于 Function 容器。 x 是函数的输入，接下来是输出 .

(Function x) (a -> b) -> (Function x) a -> (Function x) b

这读作：给定一个从 x 到 a 到 b 的函数，以及一个从 x 到 a, returns 一个从 x 到 b.

的函数

我们可以删除 Function x 周围的括号，因为构造函数关联性的工作方式：

Function x (a -> b) -> Function x a -> Function x b

另一种写 Function a b 的方法是使用箭头符号：(a -> b)，所以在下一步中我们这样做：

(x -> (a -> b)) -> (x -> a) -> (x -> b)

最后我们可以再次去掉额外的括号，发现它就是我们的 S 组合子：

(x -> a -> b) -> (x -> a) -> x -> b
(a -> b -> c) -> (a -> b) -> a -> c

Answer 2

首先，我认为没有简单的解释为什么在无类型 lambda 演算中函数类型的应用函子被称为替换。 AFAIK，Schönfinkel 最初将此组合器称为融合或合并函数。

为了特化一般的应用函子类型(f (a -> b), f a) -> f b（非柯里化形式），我们需要知道参数化类型变量f在函数类型的上下文中究竟代表什么。

因为每个仿函数应用仿函数都在单一类型上进行参数化。然而，函数类型构造函数需要两种类型——一种用于参数，另一种用于 return 值。对于要成为（应用）函子实例的函数，我们必须因此忽略 return 值的类型。因此，f 表示 (a -> )，即。函数类型本身及其参数的类型。部分应用的函数类型构造函数的正确表示法实际上是前缀(->) a，所以让我们坚持这个。

接下来，我将重写柯里化形式的通用应用程序类型，并将 f 替换为 (->) r。我用另一个字母将应用程序的类型参数与其他类型变量分隔开来：

(f (a -> b), f a) -> f b
f (a -> b) -> f a -> f b // curried form

// substitution
(->) r (a -> b) -> (->) r a -> (->) r b // prefix notation
(r -> a -> b) -> (r -> a) -> (r -> b) // infix notation

// omit unnecessary parenthesis
(r -> a -> b) -> (r -> a) -> r -> b

这正是 S 组合子的类型。

混淆理解 Substitution / `ap` 类型签名和不同的实现（函数式编程）

Confusion in understanding Substitution / `ap` type signature and different implementations (functional programming)

functional-programming

category-theory

ramda.js

fantasyland

sanctuary