# Find the fixed point of a recursive functional?

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.

• There is no fixed point of $T$: the inputs and outputs have different types. – D.W. Mar 2 '20 at 17:00
• 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 – D. Ben Knoble Mar 2 '20 at 21:10
• 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. – Pseudonym Mar 2 '20 at 23:52