如何实现 f(g) == g(f)，涉及 IT 技术。

Question

我昨天回答了一个问题，这让我开始思考一个有趣的（对我来说）难题。

在仅使用lambda、数字和+的限制下（没有if、?:或其他语言功能），目标是实现一些f和一些g，使得

// contract
f(x) => f'
g(y) => g'
f'(g') == g'(f')

// or more simply:
m(n) == n(m)

这是我迄今为止想到的 - 这段代码是用JavaScript编写的，目的是为了能够在浏览器中演示代码，但任何功能语言的答案都可以接受（racket、clojure、ocaml、lambda calc等）。

// f
const f = x => k =>
  k(y => y + x)

// g
const g = y => k =>
  k(x => x + y)
  
// make instance of each
const a = f(1)
const b = g(2)

console.log(a(b))
// x => x + y1
// should be 3

console.log(b(a))
// y => y + x2
// should be 3

我已经修复了关系的一半，但是由于f和g现在不对称，另一半仍然无法正常运作。

// f
const f = x => k =>
  k(y => y(x))

// g
const g = y => k =>
  k(x => x + y)
  
// make instance of each
const a = f(1)
const b = g(2)

console.log(a(b))
// 3
// should be 3 (OK)

console.log(b(a))
// y => y + x2
// should be 3

我知道为什么它不起作用，但是我尝试修复它时遇到了麻烦。最重要的是，如果无法修复，我想了解原因。

如果您有违规解决方案，我仍然很感兴趣 ^_^

- Mulan

---

你可以通过创建类似于“mayBe monad”的东西来解决它。你可以使用类似于http://mathworld.wolfram.com/BooleanFunction.html的矩阵。 - user4074041

如果您认为默认参数是 lambda 的一部分，而不是 "其他语言特性", 您可以这样做: const f = x => (fn = () => 0) => x + fn(); ;) - user3297291

Answer 1

这篇答案假设使用强类型系统（例如 Haskell），但我会尽量使用类似 JavaScript 的语法。

如果我们保持在参数化的范畴内，就不需要（甚至不能）使用数字或条件。常数函数不改变任何东西，所以我将它们排除在外，直接处理 f 和 g。

首先，请注意以下等式：

f(g) == g(f)

这段文字涉及到IT技术相关内容。其中，“implies that both f and g have function types”表示f和g都是函数类型；假设它们具有不同的输入，我们可以得出f: A -> X 和g: B -> X == (A -> X) -> X == ((B -> X) -> X) -> X == ...，即可得到一个无限制类型。我记得曾经读过一篇论文，介绍了这个确切的构造方法（可以将其表示为一对类型，并且我认为它形成了一个类别），但很遗憾我忘记了它的名字，或许还有更多可以说的。

另外一个更简单的解决方法是要求A == B。然后，由于对称方程式，X == A，因此可以得出f, g: A -> A -- 对于任意的A。其中一个满足该条件的可能性是恒等函数：

id(id) == id(id)

当我们将A特化为A->A时，就会出现其他解决方案；然后我们搜索类型为(A->A)->(A->A)的函数。其中一个是（已经找到的）特化的恒等函数，还有所有形如h=>h o ... o h的函数--将一个函数复合多次得到的函数（(o)=h=>x=>h(h(x))）。这些函数在应用时会“添加它们的重复”，例如：

(h => h o h)(h => h o h) == (h => h o h) o (h => h o h)
                         == h => h o h o h o h.

从这个例子中，我们可以看到我们可以进行选择。

f == g == h => h,
f == g == h => h o h,
f == g == h => h o h o h,
f == g == ...

我认为，以下所有函数都属于类型 forall A. (A -> A) -> (A -> A)（不包括无限循环）。

似乎还存在这种构造的极限与上述无限情况（现在在实际的 Haskell 中）的关系：

Prelude> let g = \h -> h . g

<interactive>:11:19:
    Occurs check: cannot construct the infinite type: b ~ (b -> c) -> c

- phipsgabler

---

非常好的解释关于无限类型 - 这让很多意义。 - Mulan

Answer 2

这是我能够接近的最近的一次，但它确实使用了三元 (?:) 表达式

const f = x => g =>
  g === undefined ? x : g() + x
  
const g = y => f =>
  f === undefined ? y : f() + y

const a = f(1)
const b = g(2)

console.log(a(b)) // 3
console.log(b(a)) // 3

这里的f与g完全等价，我们可以轻松地只使用其中一个。

const f = x => g =>
  g === undefined ? x : g() + x

const a = f(1)
const b = f(2)

console.log(a(b)) // 3
console.log(b(a)) // 3

- Mulan

Answer 3

要实现这个，显然f和g都必须接受一个函数作为参数并返回相同类型的值。但是经过一段时间的摆弄后，很快就让我意识到我正在处理无限类型。

除非你的函数像Haskell的id或JS的x => x那样简单。因此在Haskell中，我会这样做;

f :: a -> a
g :: a -> a

f = id
g = id

*Main> f(g)(+3) 2
5
*Main> g(f)(+3) 2
5

同样可以在JS中简单实现。

- Redu