Take inverse of a function in Racket

3
votes

I am trying to write a higher-order Racket function that takes a first-order function of one variable and returns its inverse. I know that it has to start off something like this:

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

I figured this because inverse must take a function which returns a function which takes a y and returns x such that (= (f x) y). In other words, the contract for inverse is something like:

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

I'm just stumped trying to figure out what goes where the elipses are?

EDIT: In response to people saying this is impossible, I am willing to accept an inverse function that when given y returns a possible x. In response to comments about the function not having an inverse, please note the contract that I have for f. It is a (number? -> number?) mapping, and therefore has an inverse.

3
lambdafunctional-programmingschemeracket
@RoddyoftheFrozenPeas: Sorry, I've edited the question to make it clearer. – Daniel
Daniel, I think we'd all be curious about what you're trying to achieve here? Is this simply an exploration of functional programming, or to you have some real use-case for a task? Because as both the answers so far indicate, this is mathematically impossible as presented. – Ben

3 Answers

6
votes

For the general case, given an arbitrary function f you can't tell what's its inverse function. Even worse, a given function might not have an inverse at all - for example: the input function could perform an MD5 hash, which has no inverse. Sorry, your question has no answer.

3
votes

Consider f(x)=x^2. This is a very simple function without an inverse. (because f(1)=f(-1) there are no unique inverse to y=1).

Since a very simple function might have no inverse, you cant't expect a general Scheme function to have an inverse.

2
votes

I knew that I had seen this before, but I couldn't remember how it worked. Now I remember, but I realized that I had been misleading in my question because the version I had seen assumed that we already had a function called root which would return one of the zeros of a provided function. Given that function, it is pretty easy:

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

It's pretty easy to see how this works. The inverse of a function is the x such that f(x) = y. Obviously, the root of the function f(x) - y = 0 is that x.

The place where I had gone wrong is that the best we can do for root is Newton's method or some other approximation.