SciTech.blog
SciTech.blog

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).

Comments

Name: