# Fixpoints of functions in Python and C++

**27 Sep 2017, 10:07 • c++, python**

*The fixpoint operator (\(\mu\)) on functions provides a way of converting nonrecursive functions into recursive ones.
Let's learn how to implement it in Python and C++.*

A fixpoint of a mapping \(\phi\) is an \(x\) such that \(\phi(x)=x\). Consider the following function:

\[ f(g,x) = \begin{cases} 1 & \text{for } x \leqslant 1 \\ x \cdot g(x-1) & \text{for } x>1 \end{cases} \]If we restrict ourselves to \(\mathbb{N}\), \(f\) is of type \((\mathbb{N} \rightarrow \mathbb{N}) \times \mathbb{N} \rightarrow \mathbb{N} \), which can be also thought of as \((\mathbb{N} \rightarrow \mathbb{N}) \rightarrow (\mathbb{N} \rightarrow \mathbb{N})\):

\[ f(g) = \begin{cases} 1 & \text{for } x \leqslant 1 \\ \lambda x . x \cdot g(x-1) & \text{for } x>1 \end{cases}\]Viewed thus, \(f\) is an endofunction, so we can try to get its (least) fixpoint, \(\mu f\) (hence \(\mu f=f(\mu f)\)). Note that what we get is the factorial:

\[ \mu f(x)=x! \]It's very easy to implement \(\mu\) in Python:

def fact_(x, f): if x <= 1: return 1 else: return x * f(x-1) def fix(f): return lambda x: f(x, fix(f)) fact = fix(fact_) print(fact(5))

Since Python is dynamically typed, there are no type declarations in the code. We simply return a \(\lambda\)-function which applies \(f\) to \(x\) and itself.

However, in C++ we'd run into difficulties because the definition of `fix`

is self-referencing (Python is dynamic so it doesn't matter there).
What we need to do is define a callable class. The `()`

operator can then refer to the fixpoint itself as follows:

template<typename T> class Fix { std::function<T(const T&, const std::function<T(T)>&)> f; public: Fix(const std::function<T(const T&, const std::function<T(T)>&)>& _f) : f(_f) {} T operator()(T x) const { return f(x, *this); } }; int fact_(int x, const std::function<int(int)>& f) { return x <=1 ? 1 : x * f(x - 1); } const auto& fact = Fix<int>(factF); std::cout << fact(5) << std::endl;

Note that since `Fix`

is a class, we can use `f(x, *this)`

.