Explicit and structured computation progress

In imperative programming, we usually have code that looks the following way:

func addOneToSlice(xs []int) []int {
  rs := make([]int, len(xs))
  for i, value := range xs {
    rs[i] = value + 1
  }
  return rs
}

However, notice the following about the for loop:

• Each iteration has a specific purpose, which is to add one to the current element.

• However, each iteration has no constraint on which element it can operate.

• Operating with xs[i+2] and rs[i+3] wouldn't fundamentally alter the structure of the code we have, while making the end result incorrect.

Compare how the same task would be done in F#:

let rec addOneToList =
  function
  | [] -> []
  | x :: xs -> x + 1 :: addOneToList xs

Now consider the following:

• We have a list as a function argument.

• A list in functional languages is a linked list.

• The efficient and standard operations on linked lists are:

  • Separating the head x from its tail xs

  • Prepending a value x to a list xs

  • Comparing the list passed as a parameter with the empty list []

Given these restrictions, adding 1 to any element y not at the head of the list would significantly alter the structure of our function.

Now compare how the computation progresses in both styles:

• In the functional style, pattern matching and recursive definitions make the computation structure explicit. The result of operations like + does not interfere with the execution flow.

• In the imperative style, mutating values is used in operations with input data and for deciding which code blocks will be executed, which does not necessarily result in a structured execution flow.

As a consequence of having language features that make the computation progress explicit and structured, we avoid the need for mutation. Thus, immutability isn't an actual feature of a functional language, but a consequence of making the computation progress explicit and structured.