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.