Fixed points and idempotency

Thinking about fixed points, I realised (even if it’s a trivial conclusion) that they can be elegantly used to define idempotency:

A function is idempotent if every member of its codomain is a fixed point.

Fixed point of some function f is any value a for which:

\[f(a) = a\]

(in functional programming, fixed points are super useful and lead to interesting things like recursion schemes and y-combinators)

Codomain of some function f is the set of values that the function maps the domain to. Given some function f, applying it to its domain element x produces the codomain element f(x).

When is that codomain element f(x) a fixed point? Let’s use the fixed point equation from earlier:

\[f(a) = a\] \[a = f(x)\] \[f(f(x)) = f(x)\]

We arrive at the exact condition for idempotency. A function is idempotent if repeated application results in the same value:

f(x) = f(f(x)) = f(f(f(x))) = ...

Here’s an example: Rounding function floor: Double => Int.

  • Every member of its codomain is a fixed point: for every integer n, floor(n) = n.
  • Therefore, function is idempotent.
  • Try it: floor(3.7) = floor(floor(3.7)) = 3.
Written on November 17, 2022