如何实现 f(g) == g(f)

Question

我 answered a question yesterday 这让我想到了一个（对我来说）有趣的谜题

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

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

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

Here's what I came up with so far - this code is in JavaScript for the purpose of being able to demonstrate the code in the browser but answers in any functional language are acceptable (racket, clojure, ocaml, lambda calc, etc)

// 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 现在不对称[=22=，另一方仍然破裂]

// 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

我知道为什么它不起作用，但我无法修复它。最重要的是，如果不可能，我很想知道为什么。

如果你想出突破限制的方案，我还是有兴趣看看的^_^

Answer 1

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

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

Answer 2

这个答案假设一个强大的非单位类型系统（例如。Haskell，但我在这里尝试坚持类似 JS 的语法）。

如果我们停留在参数化领域，我们就不需要（甚至不能使用）数字或条件。常量函数不会改变任何东西，所以我将它们省略并直接处理 f 和 g。

首先，观察等式

f(g) == g(f)

意味着 f 和 g 都有函数类型。假设两者都有不同的输入，我们得到 f: A -> X 和 g: B -> X == (A -> X) -> X == ((B -> X) -> X) -> X == ...，即，你得到一个无限类型。我记得读过一篇关于这个确切构造的论文（可以将其表示为一对类型，我认为它构成了一个类别），但不幸的是忘记了它的名字——也许这里还有更多要说的。

一个更简单的解决方案是要求 A == B。然后 f, g: A -> X，但是由于 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)))。这些 "add their repetitions" 应用程序，例如

(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

Answer 3

显然，f 和 g 都必须接受一个函数作为参数，并且 return 必须接受相同类型的值。然而，在修补了一段时间之后，我很快发现我正在处理无限类型。

嗯，除非你的函数是 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实现。

如何实现 f(g) == g(f)

How to implement f(g) == g(f)

javascript

language-agnostic

functional-programming

lambda-calculus