在Racket中求函数的反函数

Question

我正在尝试编写一个高阶Racket函数，它接受一个一元的一阶函数并返回其反函数。我知道它必须像这样开始：

``` (let [(inverse (lambda (f) (lambda (y) ...)))]) ```

我之所以这么想是因为`inverse`必须使用返回一个函数的函数，并且该函数接受一个y并返回x，使得`(= (f x) y)`。换句话说，反函数的约定大致如下：

; inverse : (number? -> number?) -> (number? -> number?)

我正在努力破解省略号应该填什么的问题？

编辑： 回应有人说这是不可能的，我愿意接受一个反函数，当给定 y 时返回可能的 x。针对有关该函数没有反函数的评论，请注意我对 f 的契约。它是一个 (number? -> number?) 映射，因此具有反函数。

- Daniel

---

@RoddyoftheFrozenPeas：抱歉，我已经编辑了问题以使其更清晰。 - Daniel

丹尼尔，我想我们都会对你在这里尝试实现什么感到好奇？这只是探索函数式编程，还是你有一些真正的任务用例？因为截至目前为止的两个答案都表明，按照所呈现的方式，在数学上是不可能的。 - Ben

Answer 1

对于一般情况来说，假设有一个任意函数 f，你无法确定它的反函数是什么。更糟糕的是，某些函数可能根本没有反函数——比如：输入函数可以执行MD5哈希，而哈希函数没有反函数。很抱歉，你的问题没有答案。

- Óscar López

---

是的，你说得对。我想错了。请看我提供的答案。 - Daniel

在Racket中仍然可以找到双射函数的反函数。这是许多计算机代数系统的常见功能。 - Anderson Green

但是如果我们假设f函数是双射的呢？ - ladytoky0

Answer 2

考虑函数f(x)=x^2。这是一个没有反函数的非常简单的函数。(因为f(1)=f(-1)，所以y=1没有唯一的反函数)。

由于一个非常简单的函数可能没有反函数，你不能期望一个通用的Scheme函数有反函数。

- soegaard

---

假设函数输出其中一种可能性是可以的。 - Daniel

这个怎么样(define (f x) (let loop () (loop) 42))？有反函数吗？ - soegaard

那并不是一个真正的函数。它不是从X映射到Y的映射。 - Daniel

不是数学意义上的，但它是一个很好的Scheme函数。 - soegaard

Answer 3

我记得以前见过这个，但我想不起来它是如何运作的。现在我记起来了，但我意识到我的问题有误导性，因为我之前看到的版本假定我们已经有了一个名为 "root" 的函数，该函数将返回所提供函数的一个零点。如果有这个函数，那就相当容易：

(define (inverse f)
  (lambda (y)
    (root (lambda (x) (- (f x) y)))))

很容易看出这个函数的工作原理。函数的反函数就是使 f(x) = y 成立的 x。显然，函数 f(x) - y = 0 的根就是该 x。

我错在这里，因为对于 root 函数，我们最好能用牛顿迭代法或其他某种近似方法。

- Daniel