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:
funcSumLoop(nums []int) int { sum := 0 for _, num := range nums { sum += num } return sum }
The integer variablesum
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.
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:
funcSumRecursive(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.
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
.
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:
funcbenchmarkSumRecursive(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 took178 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:
funcSumTailCall(vs []int) int { if len(vs) == 0 { return 0 } return vs[0] + SumTailCall(vs[1:]) }
Results of the benchmark test: It took192 ns/op
.
Note
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 thework 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.
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.
Note
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.)
See that {ret = n + 2}
is our anonymous function/function literal/closure/lambda expression.
Our function literal:
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.