A journey from imperative programming to pure FP and enlightenment

Let's take a journey from imperative to a pure functional way of programming a sum function. First, let's look at the imperative sum function:

func SumLoop(nums []int) int {
       sum := 0
       for _, num := range nums {
              sum += num
       }
       return sum
}

The integer variable sum changes or mutates over time; sum is not immutable. There are no for loops or mutating variables in pure FP.

So, how can we iterate through a series of elements using pure FP? We can do this using recursion.

Immutable variable: A variable whose value is assigned during runtime and cannot be modified.

Note that Go does have constants, but they differ from immutable variables in that values are assigned to constants at compile time, rather than at runtime:

func SumRecursive(nums []int) int {
       if len(nums) == 0 {
              return 0
       }
       return nums[0] + SumRecursive(nums[1:])
}

Notice that the last line of the preceding SumRecursive function calls itself: SumRecursive(nums[1:]) . That's recursion.

Benchmark test for the imperative SumLoop function

We have heard that recursion in Go can be slow. So, let's write some benchmark tests to check it out. First, let's test the performance of the basic imperative function SumLoop:

func benchmarkSumLoop(s []int, b *testing.B) {
       for n := 0; n < b.N; n++ {
              SumLoop(s)
       }
}

func BenchmarkSumLoop40(b *testing.B) { benchmarkSumLoop([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40}, b) }

Results: It took 46.1 ns/op.

Benchmark test for the SumRecursive function

Now that we know how long the imperative function SumLoop takes, let's write a benchmark test to see how long our recursive version, namely SumRecursive, would take:

func benchmarkSumRecursive(s []int, b *testing.B) {
       for n := 0; n < b.N; n++ {
              SumRecursive(s)
       }
}

func BenchmarkSumRecursive40(b *testing.B) { benchmarkSumRecursive([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40}, b) }

Results: It took 178 ns/op.

Tail call recursion is faster in languages such as Prolog, Scheme, Lua, and Elixir, and the ECMAScript 6.0-compliant JavaScript engines embrace the pure functional style of programming. So, let's give it a shot:

func SumTailCall(vs []int) int {
       if len(vs) == 0 {
              return 0
       }
       return vs[0] + SumTailCall(vs[1:])
}

Results of the benchmark test: It took 192 ns/op.

TCO: A tail call is where the last statement of a function is a function call. An optimized tail call has been effectively replaced with a GoTo statement, which eliminates the work required to set up the call stack before the function call and restore it afterward.

We could even use GoTo statements to further speed up the tail call recursion, but it would still be three times slower than the imperative version.

Why? This is because Go does not provide pure FP support. For example, Go does not perform TCOs, nor does it provide immutable variables.

A time of reckoning

Why would we want to use pure FP in Go? If writing expressive, easy-to-maintain, and insightful code is more important than performance, then perhaps.

What are our alternatives? Later, we'll look at some pure FP libraries that have done the heavy lifting for us and have made strides toward being more performant.

Is that all there is to functional programming in Go? No. Not by a long shot. What we can do with FP in Go is currently partially limited by the fact that the Go compiler currently does not support TCO; However, that may change soon. For details see the How to Propose Changes To Go section in the Appendix.

There is another aspect to functional programming that Go fully supports: function literals. And as it turns out, that is the single most important characteristic that a language must have to support FP.

Function literals: These are functions that are treated as first-class citizens of a language, for example, any variable type, such as int and string. In Go, functions can be declared as a type, assigned to variables and fields of a struct, passed as arguments to other functions, and returned as values from other functions. Function literals are closures, giving them access to the scope in which they are declared. When function literals are assigned to a variable at runtime, for example, val := func(x int) int { return x + 2}(5), we can call that anonymous function a function expression. Function literals are used in lambda expressions along with currying. (For details about lambda expressions, see Chapter 10, Functors, Monoids, and Generics.)

A quick example of a function literal

See that {ret = n + 2} is our anonymous function/function literal/closure/lambda expression.

Our function literal:

• Is written like a function declaration, but without a function name following the func keyword
• Is an expression
• Has access to all the variables available in its lexical scope (n in our case)

package main

func curryAddTwo(n int) (ret int) {
   defer func(){ret = n + 2}()
   return n
}

func main()  {
   println(curryAddTwo(1))
}

The output is as follows:

3

Note that we used the defer statement to delay the execution of our function literal until after its surrounding function (curryAddTwo) is returned. Since our anonymous function has access to all the variables in its scope (n), it can modify n. The modified value is what gets printed.