Learning Functional Programming in Go

Directories correspond to the book's units and chapters:

Let's run our first Go application as follows:

Each chapter is divided into sequentially numbered directories that are in the order of their appearance in the book.

First, let's make sure we have Go installed, our GOPATH is properly set, and that we can run a Go application.

Many people use a global GOPATH to store the source code for all their Go applications or, frequently, manually reset their GOPATH. I found this practice to be troublesome when working with multiple Go projects for multiple clients, each of which had differing Go versions and third-party dependencies.

The example Go applications that we'll use in this chapter do not have dependencies; that is, we don't have to import any third-party packages. So, all we have to do to run our first app--cars.go--is verify that Go is installed, set our GOPATH, and type go run cars.go:

Using a global GOPATH is easy for projects that are super simple, like the examples in this chapter.

In Chapter 2, Manipulating Collections, our Go applications will start getting more complex, and we'll get introduced to a simple, more consistent way to manage our Go development environments.

Let's utilize a memoization technique to speed up our Fibonacci calculation.

First, let's create a function type named Memoized() and define our Fibonacci variable to be of that type:

type Memoized func(int) int
var fibMem Memoized

Next, let's implement theMemoize()function. The key thing to realize here is that as soon as our application starts, even before ourmain()function is executed, ourfibMemvariable get wired up. If we were to step through our code we'd see that ourMemoizefunction is called. The cache variable is assigned and our anonymous function is returned and assigned to our fibMem function literal variable.

funcMemoize(mf Memoized) Memoized {
       cache := make(map[int]int)
return func(key int) int {
if val, found := cache[key]; found {
return val
              }
              temp := mf(key)
              cache[key] = temp
return temp
       }
}

Memoize takes a Memoized() function type as its input and returns a Memoized() function.

In the first line of Memoize, we create a variable of the type map to act as our cache in order to hold computed Fibonacci computations.

Next, we create a closure that is of the type Memoized(), which is returned by the Memoize() function. Note that a closure is an inner function that closes over or that has access to variables in its outer scope.

Inside the closure, if we find the computation for the passed integer, we return its value from the cache; else we call the recursive Fibonacci function(mf) with the integer parameter (key), whose return value will be stored incache[key]. Next time, when the same key is requested its value will be returned directly from the cache.

An anonymous function is a function defined with no name. When an anonymous function includes logic that can access variables defined in its scope, for example, cache, and if that anonymous function can be passed as an argument or returned as the value of function calls, which is true in this case, then we can refer to this anonymous function as a lambda expression.

We'll implement the logic of the Fibonacci Sequence in a function named fib:

func fib(x int) int {
if x == 0 {
return 0
} else if x <= 2 {
return 1
} else {
return fib(x-2) + fib(x-1)
   }
}

The last thing we do in our memoize.go file is to create the following function:

func FibMemoized(n int) int {
return fibMem(n)
}

Now, it's time to see if our wiring works properly. In our main() function when we execute our println statement, we get the correct output.

println(fibonacci.FibMemoized(5))

The following is the output:

5

We can verify that 5 is the correct answer by glancing back at our Fibonacci(5)calculation graph shown earlier in this chapter.

If we were to step through our code using a debugger, we'd see that fibonacci.FibMemoized(5) calls the following

func FibMemoized(n int) int {
return fibMem(n)
}

And the value of n variable is 5. Since fibMem is pre-wired, we start executing at the return statement (and we have access to the cache variable that has already been initialized) . So, we begin executing at the return statement shown in the following code (from the Memoize function):

return func(key int) int {
if val, found := cache[key]; found {
return val
   }
   temp := mf(key)
   cache[key] = temp
return temp
}

Since this is the first time through, there are no entries in the cache and we skip past the body of the if block and run temp := mf(key)

That calls the fib function:

func fib(x int) int {
if x == 0 {
return 0
} else if x <= 2 {
return 1
} else {
return fib(x-2) + fib(x-1)
   }
}

Run the fib function as follows:

Since x is greater than 2 we run the last else statement that recursively calls fib twice. Recursive calls to fib continues until the base conditions are reached and the final result is calculated and returned.

Given the expression result := function1() + function2(), parallelization means that we can run each function on a different CPU core and the total time will be approximately the time it takes for the most expensive function to return its result. Consider the following explanation for parallelization and concurrency:

Go enhances the concurrent execution of Goroutines with synchronization and messaging using channels and provides multiway concurrent control with the Select statement.

The following language constructs provide a model in Go for concurrent software construction that is easy to understand, use, and reason about:

In the following code, data is sent to channel in the first line. In the second line, data is assigned the value received from channel:

channel <- data
data := <-channel

Since Go channels behave as FIFO queues, where the first items in are the first items out, and since the calculation for the next number in a Fibonacci sequence is a small component, it seems that our Fibonacci sequence function calculation is a great candidate for a concurrency implementation.

Let's give it a go. First, let's define a Channel function that uses a channel to perform Fibonacci calculations:

func Channel(ch chan int, counter int) {
       n1, n2 := 0, 1
for i := 0; i < counter; i++ {
              ch <- n1
              n1, n2 = n2, n1 + n2
       }
       close(ch)
}

First, we declare the variables n1 and n2 to hold our initial sequence values of 0 and 1.

Then, we create a loop for the total number of times given. In each loop, we send the next sequential number to the channel and calculate the next number in the sequence, until we reach our counter value, which is the last sequential number in our sequence.

The following FibChanneled function creates a channel, namely ch, using the make() function and defines it as a channel that contains integers:

funcFibChanneled(n int) int {
       n += 2
ch := make(chan int)
go Channel(ch, n)
       i := 0; var result int
for num := range ch {
              result = num
              i++
       }
return result
}

We run our Channel (Fibonacci) function as a Goroutine and pass it the ch channel and the 8number, which tells Channel to produce the first eight numbers from the Fibonacci sequence.

Next, we range over the channel and print any values that the channel produces for as long as the channel has not been closed.

Now, let's take a breather and examine what we've accomplished with our Fibonacci sequence examples.

In the first example, I used the~/myprojects/learn-fp-gopath. The path that I actually used to create the code in this book is~/clients/packt/dev/learn-fp-go. So, please don't be confused by those paths. They are the same thing.

Also, later in the book, when we start using Dot Init, the screenshots may reference the~/devdirectory. That comes from the Init script, that is,MY_DEV_DIR=~/dev.

Here are a few links in that directory:

01_duck@ -> /Users/lex/clients/packt/dev/learn-fp-go/2-design-patterns/ch04-solid/01_duck
01_hof@ -> /Users/lex/clients/packt/dev/learn-fp-go/1-functional-fundamentals/ch03-hof/01_hof
04_onion@ -> /Users/lex/clients/packt/dev/learn-fp-go/2-design-patterns/ch07-onion-arch/04_onion

For more information about Dot Init, see the appendix.

In the first benchmark test, we examine the performance of computing the eighth number in the Fibonacci sequence. Note that we pass the -bench=.argument, which means run all benchmark tests. The ./... argument means to run all the tests in this directory and all the child directories as well:

When we request the eighth number in the sequence, the simple recursive implementation runs faster than the memoized and channeled (optimized) versions, 213 ns/op compared to 1302 ns/op and 2224 ns/op, respectively.

In fact, when the simple version is executed once, it only takes 3.94 ns/op.

One very cool feature of Go's benchmark testing facility is that it is smart enough to figure out how many times to execute the function under test. The value of b.N will increase each time until the benchmark runner is satisfied with the stability of the benchmark. The faster the function runs under a test, the more times the benchmark facility will run it. The more times the benchmark facility runs a function, the more accurate the performance metric, for example, 3.94 ns/op.

Take the FibSimple test for example. When it is passed with 1, it means it only needs to execute once. Since it only takes 3.94 ns/op, we see it is executed 10,000,000 times. However, when FibSimple is passed with 40, we see that it takes 2,509,110,502 ns to complete one operation, and the benchmark facility is smart enough to only run it once. That way, we can be assured that running benchmark tests is as accurate as possible and they run within a reasonable time. How nice is that?

Since the FibSimple implementation is recursive and has not been optimized, we can test our assumption that the time it takes to calculate each successive number in the sequence will increase exponentially. We can do this using a common testing technique by calling the private function benchmarkFibSimple, which avoids directly invoking the test driver:

func benchmarkFibSimple(i int, b *testing.B) {
     for n := 0; n < b.N; n++ {
            FibSimple(i)
     }
}

func BenchmarkFibSimple1(b *testing.B)  { benchmarkFibSimple(1, b) }
func BenchmarkFibSimple2(b *testing.B)  { benchmarkFibSimple(2, b) }
func BenchmarkFibSimple3(b *testing.B)  { benchmarkFibSimple(3, b) }
func BenchmarkFibSimple10(b *testing.B) { benchmarkFibSimple(4, b) }
func BenchmarkFibSimple20(b *testing.B) { benchmarkFibSimple(20, b) }
func BenchmarkFibSimple40(b *testing.B) { benchmarkFibSimple(42, b) }

We test the first four numbers in the sequence, 20 and then 42. Since it takes about 3 seconds for my computer to calculate the 42nd number in the sequence, I decided not to go any higher. No need to wait longer than that when we can easily see the exponential growth pattern, without having to wait for more than a minute to get our results.

Our benchmark testing has proven that our simple, recursive implementation of the Fibonacci sequence behaves as expected. This behavior equates to poor performance.

Let's look at a few ways to increase performance.

We have observed that our FibSimple implementation always returns the same result, given the same input(s), and that there are no side effects in the environment in which it runs. For example, if we pass FibSimple an 8 value, we know that every time the result will be 13. We used this fact to leverage a caching technique called memoization to create the FibMemoized function.

Now, let's write some tests to see how effective MemoizeFcn is.

Since our fibTests structure has been defined in another test in our package, in chapter1/_01_fib/ex1_test.go, we don't need to define it again. This way, we only define the test table once, and we're able to reuse it in subsequent Fibonacci function implementations to get a reasonable apples-to-apples comparison of each solution.

Here's the basic unit test for the FibMemoized function:

func TestMemoized(t *testing.T) {
   for _, ft := range fibTests {
      if v := FibMemoized(ft.a); v != ft.expected {
         t.Errorf("FibMemoized(%d) returned %d, expected %d", ft.a, v, ft.expected)
      }
   }
}

It won't return an error unless there is a bug in our code.

That's one of the great things about running unit tests. You don't hear about them unless something breaks.

Here are the benchmark tests:

func BenchmarkFibMemoized(b *testing.B) {
     fn := FibMemoized
     for i := 0; i < b.N; i++ {
            _ = fn(8)
     }
}

As before, in the FibSimple example, we examine the performance of computing the eighth number in the Fibonacci sequence:

func BenchmarkFibMemoized(b *testing.B) {
     fn := FibMemoized
     for i := 0; i < b.N; i++ {
            _ = fn(8)
     }
}

func benchmarkFibMemoized(i int, b *testing.B) {
     for n := 0; n < b.N; n++ {
            FibMemoized(i)
     }
}

func BenchmarkFibMemoized1(b *testing.B)  { 
    benchmarkFibMemoized(1, b) }
func BenchmarkFibMemoized2(b *testing.B)  { 
    benchmarkFibMemoized(2, b) }
func BenchmarkFibMemoized3(b *testing.B)  { 
    benchmarkFibMemoized(3, b) }
func BenchmarkFibMemoized10(b *testing.B) { 
    benchmarkFibMemoized(4, b) }
func BenchmarkFibMemoized20(b *testing.B) { 
    benchmarkFibMemoized(20, b) }
func BenchmarkFibMemoized40(b *testing.B) { 
    benchmarkFibMemoized(42, b) }

As before, we carry out a test calling FibMemoized, using 1, 2, 3, 4, 20, and 42 as input.

Here's the complete listing for the FibChanelled function:

package fib

import "testing"

func TestChanneled(t *testing.T) {
     for _, ft := range fibTests {
            if v := FibChanneled(ft.a); v != ft.expected {
                   t.Errorf("FibChanneled(%d) returned %d, expected %d", ft.a, v, ft.expected)
            }
     }
}

func BenchmarkFibChanneled(b *testing.B) {
     fn := FibChanneled
     for i := 0; i < b.N; i++ {
            _ = fn(8)
     }
}

func benchmarkFibChanneled(i int, b *testing.B) {
     for n := 0; n < b.N; n++ {
            FibChanneled(i)
     }
}

func BenchmarkFibChanneled1(b *testing.B)  { 
    benchmarkFibChanneled(1, b) }
func BenchmarkFibChanneled2(b *testing.B)  { 
    benchmarkFibChanneled(2, b) }
func BenchmarkFibChanneled3(b *testing.B)  { 
    benchmarkFibChanneled(3, b) }
func BenchmarkFibChanneled10(b *testing.B) { 
    benchmarkFibChanneled(4, b) }
func BenchmarkFibChanneled20(b *testing.B) { 
    benchmarkFibChanneled(20, b) }
func BenchmarkFibChanneled40(b *testing.B) { 
    benchmarkFibChanneled(42, b) }

We performed twooptimizations on our original Fibonacci sequence logic using a caching technique and Go's concurrency features. We wrote both the optimization implementations. More optimizations are possible. In some cases, optimization techniques can be combined to produce even faster code.

What if all we had to do was write a simple recursive version and then when we compiled our Go code, the Go compiler would automatically generate object code with performance optimizations?

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.

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.

package main

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

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

3