Fixed points

Let's take a look at a common implementation of a function for calculating Fibonacci numbers:

let fibonacci0 n =
  let mutable i, a, b = 0, 0, 1

  while n <> i do
    let next = a + b
    a <- b
    b <- next
    i <- i+1
    
  a

fibonacci0 10

55

Most people think since functional programing discourages mutation, that means tying their hands and being useless. However, there's a communication failure here. Functional programming is valuable, not because discourages mutation, but because it encourages structured programming and composability.

The above function contains one of those patterns that appear everywhere, and functional programming can help you to recognize and reuse it more than imperative programming. Let's take a look at the power function and how it allows to implement Fibonacci:

let rec power (f: 'a -> 'a) (initial: 'a, n: int) =
  if n = 0 then initial else power f (f initial, n - 1)

let fibonacci1 n = power (fun (a, b) -> (b, a + b)) ((0, 1), n) |> fst

Now you can see how fibonacci1 is verbose in those aspects essential to Fibonacci: the initial state and how it transitions to the next. The rest is left to the power function.

Another thing while loops help us to find are fixed points, i.e. for a function f a value c that holds f c = c. But this pattern can be disentangled from while loops as well:

let fixedPoint (f: 'a -> 'a) (initial: 'a) =
  let rec loop (prev: 'a) (current: 'a) =
    if prev = current then prev else loop current (f current)

  loop initial (f initial)

Euclid's Algorithm for calculating the Greatest Common Divisor between two positive integers relies on finding a fixed point:

let gcd0 (a:int, b:int) =
  let mutable x = a
  let mutable y = b
  while x <> y do
    if x > y then x <- x - y else y <- y - x
  
  x

gcd0 (12,8)

4

Now, relying on our fixedPoint function we get:

let step (x: int, y: int) =
  if x > y then x - y, y
  else if x < y then x, y - x
  else x, y

let gcd1 = fixedPoint step >> fst

gcd1 (12, 8)

4

This time we discover there's a fixed point when dividing successive elements of the Fibonacci sequence. That number is known as Golden Ratio.

let fibonacci = Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0, 1)

let fixedPointSeq (xs: 'a seq) = xs |> Seq.pairwise |> Seq.find (fun (a,b) -> a = b) |> fst

fibonacci |> Seq.pairwise |> Seq.map (fun (a,b) -> double b / double a ) |> fixedPointSeq

1.618033988749895

Functions power and fixedPoint are inspired by the power operator in APL (⍣)