A functional is a function which takes another function as a parameter.

The fixed point of a function is an input such that

F(x) = x

Given an example functional,

T(F,x,y) = if x = 0 return 0
           else return y + F(x - 1,y)

what is the fixed point of the functional?

The functional looks similar to a recursive implementation of x * y given the if x = 0 return 0 and function call with x - 1, but I don't see where to go with this. To find a fixed point in a normal mathematical equation you'd just set T(f,x,y) = f(x,y) and solve, but given the format that doesn't really work. I can't see how the RHS can be simplified to allow that.

  • 1
    $\begingroup$ There is no fixed point of $T$: the inputs and outputs have different types. $\endgroup$ – D.W. Mar 2 '20 at 17:00
  • 1
    $\begingroup$ What DW says is correct, but higher-order functions (functionals) can have fixed-points—they are themselves functions! See the y-combinator and others for examples. It’s also possible to use a (tail-recursive) functional to compute the fix-point of any function that has one, given an appropriate starting value and step function. Ex Scala and Clojure $\endgroup$ – D. Ben Knoble Mar 2 '20 at 21:10
  • 2
    $\begingroup$ Also worth pointing out that most functionals do not have a single fixed point, so it's not correct to talk about "the" fixed point. The two most interesting fixed points of a functional, because they always exist and are unique, are the least fixed point, and the "optimal" fixed point. A given functional may not have a single "maximal" fixed point, and so the optimal fixed point is the greatest lower bound of all of the maximal fixed points. $\endgroup$ – Pseudonym Mar 2 '20 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.