Functional programming in Go

From Know Go

Question: what the heck is functional programming, anyway? Don’t all programs use functions?

Yes, they do, but so-called “functional programming” takes this idea a step further. Instead of just using functions to organise chunks of imperative code, we can make function calls the main, or only, kind of control structure.

For example, rather than writing a loop to do something to each element of a slice, we could instead apply some function to each element. This is called mapping the function (nothing to do with Go maps; think of it in the mathematical sense of mapping one set of values to another).

Suppose we want to uppercase a bunch of strings, for instance. We could write a standard for ... range loop and call strings.ToUpper on each element in the loop body. Or, looplessly, we could write a single call to some imaginary function Map that will effectively do that for us:

s := []string{"a", "b", "c"}
fmt.Println(Map(s, strings.ToUpper))
// Output:
// [A B C]

The result of mapping a function onto a slice is another slice of the same length. But we could also filter a slice by some function that decides whether to keep or reject each element:

s := []int{1, 2, 3, 4}
fmt.Println(Filter(s, IsEven[int]))
// Output:
// [2 4]

Finally, we can reduce a slice to a single value by applying some function that combines elements (such as adding them up, for example). We can solve an awful lot of problems rather elegantly using just these three operations: map, filter, and reduce. This is what characterises the functional style of programming, and while it doesn’t necessarily suit every Go program, it’s a very useful idea to have in your mental toolbox.

In this post, I’ll show you how easy it is to write Map, Filter, and Reduce for yourself, and what you can do with them.

First-class functions

As you probably know, functions are values in Go. In other words, we can pass a function as an argument to another function, or return one as its result. Indeed, this is a common pattern, and one of the most powerful features of Go.

The technical term for this feature of a language is that its functions are first-class citizens: they’re on the same level as things like variables and literals, and can be used in the same way.

For example, if we wanted to double every integer in a slice, we could write some function double that doubles its input, and “map” that function over the slice. The result would be a slice where each element is twice the value of the corresponding element in the original slice.

Map

We’re saying that the Map function takes some arbitrary function as a parameter, along with a slice, let’s say, and applies the function to each element, returning the resulting slice. What does that look like? Let’s first of all work out what the type of the arbitrary function needs to be.

Well, because it transforms an element of type E to another element of type E, its signature would be func(E) E. Let’s give this type a name, then, to make it easier to think about:

type mapFunc[E any] func(E) E

Now we can write a generic function that takes a mapFunc[E] and applies it to every element of a slice of E:

func Map[S ~[]E, E any](s S, f mapFunc[E]) S {
    result := make(S, len(s))
    for i := range s {
        result[i] = f(s[i])
    }
    return result
}

As usual, the implementation is not the interesting part. What’s interesting is that now we can easily map any suitable function over a slice. For example, let’s map the standard library function strings.ToUpper over a slice of strings:

s := []string{"a", "b", "c"}
fmt.Println(Map(s, strings.ToUpper))
// Output:
// [A B C]

Pretty neat! It’s not like we couldn’t have written an explicit loop here, of course, but this is a more concise and elegant way of expressing the same idea.

Filter

Filter is the conventional name for a function that, like Map, takes an arbitrary function and applies it to each element of a slice. However, where Map uses the supplied function to transform each element, Filter uses it to decide which elements to keep and which to discard. The result of Filter is a slice containing only the elements that satisfied the keep function.

In other words, Filter takes an arbitrary slice, and also an arbitrary function that decides which elements of the slice to keep, and which to discard. Let’s see if we can figure out how to write both functions.

What can we deduce about the signature of this keep function, then? Its job is to take some slice element, of type E, and return true if the element should be included in the slice of results, or false if it should be discarded.

type keepFunc[E any] func(E) bool

Fine. So now we can write Filter in terms of this keepFunc type:

func Filter[S ~[]E, E any](s S, f keepFunc[E]) S {
    result := S{}
    for _, v := range s {
        if f(v) {
            result = append(result, v)
        }
    }
    return result
}

Again, there’s nothing very complicated about the implementation here. We range over the input slice checking whether f is true for each element. If so, we append it to the result slice. At the end, we have the slice containing only the elements of s for which f is true.

Filter functions

What kind of keepFunc could we use in real programs, then? Suppose we want to filter a slice of integers to find only the even values, for example.

In this case, our keepFunc would need to take an integer, and return true if it’s even. Well, that doesn’t sound too hard:

func(v int) bool {
    return v%2 == 0
}

Let’s try it out, then,by passing this function literal to Filter:

s := []int{1, 2, 3, 4}
fmt.Println(Filter(s, func(v int) bool {
    return v%2 == 0
}))
// Output:
// [2 4]

Reassuring! This looks more or less the same as when we used Map, except that instead of passing an existing function strings.ToUpper, we supplied an anonymous function literal instead, which is quite idiomatic in Go.

Generic filter functions

We’re not limited to passing only function literals to Filter, of course. We could certainly pass some existing named function, as we did with strings.ToUpper, too.

But there’s another interesting option. What if we wanted to pass a generic keepFunc? That is, a function parameterised on some type T?

Could we do that? We might start by trying something like this:

func IsEven[T any](v T) bool {
    return v%2 == 0
}

But, thinking about it, we already know this can’t work when T is constrained by any. Why not? Because we can only use the == operator with comparable types.

And Go’s % (remainder) operator only works with integers, which is an even smaller type set. So we’ll need to use constraints.Integer to ensure we only get values that support the % operator:

func IsEven[T constraints.Integer](v T) bool {
    return v%2 == 0
}

Let’s try it out:

fmt.Println(Filter(s, IsEven[int]))
// Output:
// [2 4]

Wonderful!

Map and Filter make perfect partners, but they’re even better when united with their best friend, Reduce. Where Map uses a function to transform each element of a slice, and Filter uses a function to pick only the desired elements, Reduce uses a function to combine the elements of a slice.

This operation is sometimes also called “fold”, “inject”, or a variety of other names depending on the programming language. Essentially, it’s about taking a sequence of values, doing some computation on them, and producing a single value as the result. For example, if we had a slice of numbers, we could add them up, producing a single result: the total.

In general, then, the function we pass to Reduce needs to take two things: a value representing the “current result” of the reduction (so far), and the next slice element to combine with it. It should return the updated current result, which in turn will be passed to the next invocation of the function, and so on, until we have the final result.

Let’s try to work out the signature of such a function first:

type reduceFunc[E any] func(cur, next E) E

In other words, a reduceFunc[E] takes two parameters of type E, and returns a single E result.

Implementing Reduce

This makes sense, so now let’s try to write Reduce:

func Reduce[E any](s []E, init E, f reduceFunc[E]) E {
    cur := init
    for _, v := range s {
        cur = f(cur, v)
    }
    return cur
}

The first parameter is the slice to operate on. The second is some starting value for the reduction (for example, zero). And the third is the reduceFunc to apply.

The implementation is pretty straightforward. We set cur equal to the initialising value init. Then, for each slice element, we call the reduceFunc with the current value of cur, and the element. The result of the reduceFunc becomes the next cur.

Let’s try summing a slice of integers, for example. Our reduceFunc is easy to write. It needs to take a cur and next value and return their sum:

func(cur, next int) int {
    return cur + next
}

So let’s pass this function literal to Reduce and see what it does:

s := []int{1, 2, 3, 4}
sum := Reduce(s, 0, func(cur, next int) int {
    return cur + next
})
fmt.Println(sum)
// Output:
// 10

Other reduction operations

Let’s try another reduction operation. What about multiplication, for example?

s := []int{1, 2, 3, 4}
p := Reduce(s, 1, func(cur, next int) int {
    return cur * next
})
fmt.Println(p)
// Output:
// 24

We’re not restricted to just numerical operations, of course. Here’s a reduction involving strings, which just concatenates them all together:

s := []string{"a", "b", "c"}
j := Reduce(s, "", func(c, n string) string {
    return c + n
})
fmt.Println(j)
// Output:
// abc