Functional inverse

Internals & Design
1

An idea: A function finv that returns the functional inverse of a function. For instance

finv(::typeof(cos)) = acos

I thought of this not for cos, but for a particular function whose inverse does not have a recognized name nor a conventional computer function name like arccosine → acos.

Two possible uses:

  1. discoverability in the case that myfunc is well known, but there is no standard name for the inverse. Instead of remembering myfunc_inv(x) or invmyfunc(x) or whatever, it is always `finv(myfunc)(x).
  2. To get the functional inverse of an unknown function. Maybe in a computation similar to automatic differentiation.

Possible complications are how to handle multiple branches and multiple arguments.

Are there outstanding cases where this would be useful, or is my use case more or less isolated ? A related question, is there already a convention used in some packages that I have not discovered?

4 Likes
2

Sure, this is definitely something you could implement for specific functions, although I would guess that the majority of functions used in practical code don’t have well-defined inverses. But I think your idea of implementing finv(::typeof(f)) for various functions f is sound.

On the other hand, the existence of a computation that could invert an arbitrary function efficiently would, at the very least, prove P = NP and probably render all of computer science obsolete. So that part’s probably not going to happen :wink:

7 Likes
3

To get the functional inverse of an unknown function. Maybe in a computation similar to automatic differentiation.

A package that implements the analysis-stack of inverse function theorem / implicit function theorem via AD + Newton + symbolic shortcuts when feasible would be really cool, but I know of no precedent of any library/language doing this well. Unfortunately this sounds like a really big project (if some terms in your function are themselves implicit functions, then you need to collapse the stack and use shortcuts).

4

While we are obviously not going to have an algorithm that does functional inverse of cryptographic hash functions, I agree that it would be useful to just have a function where the inverses are explicitly defined on everything you can write an inverse for. I even seem to remember having written an API for a package that required people to define inv(::typeof(f)) for functions they want to use.

By the way, you should be able to just use inv, I don’t see any reason why it would need a special name as it doesn’t have methods for specific functions like that.

2 Likes
5

Well my main motivation was discoverability and maybe reducing verb count, rather than dealing comprehensively with functional routines. For instance

finv(::typeof(lambertw))=  z -> z*exp(z)

And I have at least one other use case.

But, if you really think there are algorithms that would like to use routines that produce numerical functional inverses, you could do something like this.

function nofunc end
finv(f::Function) = nofunc

Then your algorithm that wants inverses could include a catchall method for nofunc, and optimized methods for those functions that have defined a method for finv.

1 Like
6

There’s also this cute trick:

julia> Base.literal_pow(::typeof(^), ::typeof(sin), ::Val{-1}) = asin # edited silly typo

julia> (sin^-1)(1)
1.5707963267948966
4 Likes
7

This is exactly what i guessed. It has been done before, and may as well be made general. But, inv is used for multiplicative inverse (and its generalization to matrices) which is a different concept. And inv is in base. In any case, the most important thing is to have a 500 post discussion about whether it belongs in base and which concept gets primacy for using inv :wink:

3 Likes
8

That is too temptingly cute. (but you meant asin)… Or on second thought, it is more obvious what (sin^-1)(x) means than what finv(sin)(x) means.

1 Like
9

I don’t think the literal_pow thing is such a good idea, because then it really does look like a multiplicative inverse. Same reason I use \arccos(x) instead of \cos^{-1}(x).

10

It may not be exactly what you are looking for, but I think the most general way to do this is with interval arithmetic, i.e. https://github.com/JuliaIntervals/IntervalContractors.jl Which is a combination of analytics and provable numerical methods on intervals.

Guess it depends on the application, though… But if you don’t know about JuliaIntervals, it is a fun read nevertheless!

2 Likes
11

I agree with you for written math. You’ve seen early 20th century papers with sin x, etc. And the same thought went through my head just now. But in the code you need parens, which disambiguate: (sin^-1)(x).

12

I still think it’s more common not to use parentheses for functions with \textrm text. I personally like them to have parentheses.

13

That looks cool. David’s interval project is great. But, I have to say, I don’t like cos!, because ! does not mean mutating function in this case. … we are drifting. That’s ok. Hendrix’s drifting was looping for an hour or so this morning.

14

You can define such a type of function with Reduce.jl symbolic package:

julia> using Reduce

julia> finv(f::Function) = collect(Algebra.solve(:($f(x) == y),:x))
finv (generic function with 1 method)

julia> finv(cos)
2-element Array{Expr,1}:
 :(x = acos(y) + 2 * arbint(5) * π)     
 :(x = -((acos(y) - 2 * arbint(5) * π)))

Also, to select the principal branch, set allbranch to off

julia> allbranch(false)
false

julia> finv(cos)
1-element Array{Expr,1}:
 :(x = acos(y))
5 Likes
15

Alternatively, if you want to also evaluate the function at x, you can do it like this

julia> using Reduce

julia> allbranch(false)
false

julia> @generated function finv(x,::Val{f}) where f
           out = Algebra.solve(:($f(y) == x),:y)
           :(@fastmath $(out[1].args[2]))
       end
finv (generic function with 1 method)

julia> finv(x,f::Function) = finv(x,Val(f))
finv (generic function with 2 methods)

julia> finv(1,sin)
1.5707963267948966

This allows you to evaluate the inverse at any x of any function f that is invertible.

4 Likes
16

Such inverses bound to function names have nice applications in pattern matching and destructuring assignmens,

@match Polar(r, phi) = z

Old issue:

https://github.com/kmsquire/Match.jl/issues/15

1 Like
17

Those are some interesting ideas. But, adding a dependency, especially a binary dependency, is not a good option for something so simple.

For the moment, I have decided on finv and pushed changes to github. For LambertW.jl, I have

finv(::typeof(lambertw)) = z -> z * exp(z)

For EmpiricalCDFs.jl, the empirical CDF is a callable object. I use essentially the following

function finv(cdf::EmpiricalCDF)
    function (c::Real)
        _inverse(cdf,c)
    end
end

These seem consistent and generalize well.

1 Like