Go Functional

Go Functional provides Functional Programming capabilities to Go. It wraps basic data-types, giving them methods that enable a style of programming that is powerful and expressive. This article will go through the basics of Functional Programming, and show you how Go Functional enables this pattern. We’ll see lots of example code, and get a feel for how Go Functional can solve (some rather contrived) problems in a delightfully readable and composable way. I focus on Go Functional’s sub-package Fslice, which operates exclusively on slices.

What’s Functional Programming

Popularized long ago by LISP and Haskell, and now by Erlang and Clojure among others, Functional Programming is a style of programming characterized by operating iteratively on lists. It shuns side-effects, prefering a deterministic environment wherein all logic resides in functions. Functions are passed to other functions. The output of one being sent to another, until finally the desired result is arrived at. Generally speaking the pattern requires:

First-class functions. Functions can be passed as parameters to other functions. The return value of a function can be a function.
No side-effects. A function cannot operate on any variable not passed into it as a parameter. A function cannot mutate any variable whatsoever. It can only return new data.
Composability. The output of one function can be used as input to another.

Go Functional does not enforce rule #2. You could break it if you wanted by referencing variables defined outside of scope. But if you do follow the rules of Functional Programming, you will be rewarded.

What does Go Functional look like?

We’re going to look at the sub-package Fslice, whose definition and method-set look like this:

type Fslice[T comparable] []T

type MethodSet[T comparable] interface {
	Map(MapFunction[T]) Fslice[T]
	Filter(FilterFunction[T]) Fslice[T]
	Some(SomeFunction[T]) bool
	Every(EveryFunction[T]) bool
	Includes(T) bool
	Reduce(ReduceFunction[T], T) T
	Sort(SortFunction[T]) Fslice[T]
	ToSlice() []T
}

Have you ever wondered which of the first 25 Fibonacci numbers are not prime? Me neither! Let’s find out.

fib25 := generateFibonacci(25)
fibNonPrimes := fslice.From(fib25).Filter(func(n int, _ int, _ []int) bool {
	r := false
	if n > 1 {
		r = !primes.IsPrime(n)
	}
	return r
})

fmt.Println(fibNonPrimes)

// Output:
// [8 21 34 55 144 377 610 987 2584 4181 6765 10946 17711 46368]

Here we filter out all non-primes, saving the result to an Fslice, which behaves just like a slice, when you want to use it that way. Since fibNonPrimes is an Fslice, it has full access to all the methods. Let’s say we need to find which of those numbers are co-primes with all other numbers in the set, because… reasons.

coPrimes := fibNonPrimes.Filter(func(n int, i int, nonPrimes []int) bool {

	return fslice.From(nonPrimes).Every(func(m int, j int, _ []int) bool {
		return (i == j) || primes.Coprime(n, m)
	})

})

Do you see what we did there? We are calling an Fslice method within an Fslice method. And why not? That’s composability, baby. What makes Functional Programming so elegant is that it can be done without transient or temporary variables. You could have them, but you don’t need them. Your logic is clean and nicely encapsulated.

The above code should be read as:

Filter coPrimes down to only those numbers for which my FilterFunction returns true
My filter function returns true if the Fslice.Every() method returns true
Fslice.Every() returns true if the EveryFunction I passed in returns true for every iteration

Go Functional uses methods and user-defined functions together. Here is the signature of a FilterFunction, along with the definition and implementation of the corresponding method.

//  FilterFunction is a user-defined function, passed into Fslice.Filter()
type FilterFunction[T any] func(v T, i int, arr []T) bool

// Fslice.Filter() interface
type MethodSet[T comparable] interface {
	...
	Filter(FilterFunction[T]) Fslice[T]
	...
}

// Fslice.Filter() implementation
func (fs Fslice[T]) Filter(fn FilterFunction[T]) Fslice[T] {
	r := make([]T, 0, len(fs))
	for i, v := range fs {
		if fn(v, i, fs) {
			r = append(r, v)
		}
	}
	return Fslice[T](r)
}

In the implementation of Fslice.Filter() we see that we are iterating over our input slice, returning only those elements for which the FilterFunction we passed in returns true.

That’s the essential magic. Every method takes a function. That function operates on every element of the slice (or every element it needs to, to produce a correct result).

There are in general two flavours of user-defined functions, in terms of their parametric signatures. I call them Mappers and Folders. Mappers take three parameters. Folders take two. Here are a few definitions of a couple user-defined functions. SortFunction and ReduceFunction are folders, while MapFunction, FilterFunction, SomeFunction, and EveryFunction are mappers. The others are oddballs. The docs of course provide fuller and more authoritative definitions.

//  MapFunction is a mapper. It has three params:
// v: the value being iterated over
// i: it's position
// arr: the full slice (non-mutable)
type MapFunction[T comparable] func(v T, i int, arr []T) T

//  ReduceFunction is a folder. It has two params: a and b.
//  They both represent values in the slice.
type ReduceFunction[T comparable] func(a T, b T) T

Go Functional is generic, capable of handling any comparable value. So floats, ints, or strings are just fine.

input := []string{"all", "your", "base", "are", "belong", "to", "us"}

longestWord := fslice.From(input).Reduce(func(a, b string) string {
    if utf8.RuneCountInString(a) > utf8.RuneCountInString(b) {
        return a
    }
    return b
})

fmt.Println(longestWord)
// Output: "belong"

Sounds like all that and bag of chips. What’s the catch?

Functional Programming offers many advantages of over a procedural or OOP style, but has some disadvantages too. What you gain in expressiveness can be lost in performance. In practice, I have not found this to matter 95% of the time. In most cases, readability and maintainability are more important than shaving off a few cycles. Go Functional includes a full-suite of benchmarks that go through common cases. They should give you an idea of the performance characteristics.

Put more succinctly, in the vast majority of cases, Go Functional is effectively a near-zero-cost abstraction, but it is not essentially so. There are cases that will result in unacceptable performance. Use the right tool for the job.

In terms of readability, my personal opinion is that functional is superior to all other styles. But you may not find so at first. It takes some getting used to.

What’s Next?

I would like to include a sub-package for maps (Fmap)
Maybe one for structs as well (Fstruct)
I’d like to introduce the concept of the Functor to enable greater polymorphism
I’d like to generate graphs from the benchmarks for visual grokking of performance characteristics
I’d like to cover especially expensive edge-cases in the benchmarks, and develop an understanding of how, when, and if cyclomatic complexity increases as functions are added to the chain.

Cloud Whisperer

[ Musings on Software Engineering ]