fix f is the least fixed point of the function
f, i.e. the least defined
x such that
f x =
x.
When
f is strict, this means that because, by the definition
of strictness,
f ⊥ = ⊥ and such the least defined fixed point
of any strict function is
⊥.
Examples
We can write the factorial function using direct recursion as
>>> let fac n = if n <= 1 then 1 else n * fac (n-1) in fac 5
120
This uses the fact that Haskell’s
let introduces recursive
bindings. We can rewrite this definition using
fix,
Instead of making a recursive call, we introduce a dummy parameter
rec; when used within
fix, this parameter then refers
to
fix’s argument, hence the recursion is reintroduced.
>>> fix (\rec n -> if n <= 1 then 1 else n * rec (n-1)) 5
120
Using
fix, we can implement versions of
repeat as
fix . (:) and
cycle as
fix . (++)
>>> take 10 $ fix (0:)
[0,0,0,0,0,0,0,0,0,0]
>>> map (fix (\rec n -> if n < 2 then n else rec (n - 1) + rec (n - 2))) [1..10]
[1,1,2,3,5,8,13,21,34,55]
Implementation Details
The current implementation of
fix uses structural sharing
fix f = let x = f x in x
A more straightforward but non-sharing version would look like
fix f = f (fix f)