Functional programming in Go

From Know Go: Generics

Now that generics have come to Go, what real-world code can we actually write using type parameters? Are they of any practical use in programs? Are there some things that we couldn’t easily write in Go before generics?

Finding elements in slices

While we could usually write the specific code we needed for a particular program, before generics it wasn’t easy to write functions on arbitrary container types, such as slices.

For example, we couldn’t write a function that takes a slice of arbitrary type and determines whether the slice contains a given element. Instead, we had to write a function that takes some specific type, such as []int, or []string.

But this is dull, because the logic is exactly the same, whatever the type of the slice element. And now we can write that function just once, for all types. Let’s try.

func Contains[E comparable](s []E, v E) bool {
    for _, vs := range s {
        if v == vs {
            return true
        }
    }
    return false
}

For any comparable type E, we’re saying, Contains[E] takes a slice of some type E and an element value of the same type, and returns a bool result, which is true if the element is in the slice.

The type parameter E is constrained, meaning that we can’t take literally any type, because we need to compare elements. If we can’t determine whether v == vs, we can’t tell if the two elements match.

And not every data type in Go is comparable in this way, meaning that it can be used with the == operator. For example, slices and maps are not comparable, and structs are not comparable if they contain slice or map fields.

So Go provides a predefined type constraint named comparable, which restricts the allowable types that Contains can take to only those that work with the == operator.

A generic function that needs to compare values of the type parameter must be constrained by at least comparable, as in this example.

Reversing slices

It’s perfectly possible to write generic functions that operate on slices of literally any type, in which case the type constraint would simply be any. If we don’t need to compare elements, for example, then we’re not limited to only comparable types.

For example, we might want to reverse a slice; that is, take a slice of some element type E, and produce a slice containing the same elements in the opposite order.

Let’s call this function Reverse:

func Reverse[E any](s []E) []E {
    result := make([]E, 0, len(s))
    for i := len(s) - 1; i >= 0; i-- {
        result = append(result, s[i])
    }
    return result
}

This time, we don’t need comparable, because we won’t be making any comparisons. All we need to do is loop over the input slice backwards, appending each element to the result slice.

The specific implementation doesn’t matter, and this one may not be the most efficient or even the easiest to understand. The point is that this is something we simply couldn’t have written at all without generics, without repeating the whole function for every specific element type.

Sorting slices

Sorting a slice is another example of something which can be a bit laborious without generics.

The standard library’s sort.Slice API requires users to pass in their own function to determine which of two elements is the lesser:

sort.Slice(s, func(i, j int) bool {
    return s[i] < s[j]
})

But it seems silly to have to pass in such a function when we’re sorting a slice of something perfectly straightforward like int, and that’s usually the case.

Go knows perfectly well how to compare two integers with <, so why should we have to write a function to do that? Well, you know why, but that doesn’t make it any less annoying.

Now we can write a generic Sort function which doesn’t have such an awkward API:

func Sort[E constraints.Ordered](s []E) []E {
    result := make([]E, len(s))
    copy(result, s)
    sort.Slice(result, func(i, j int) bool {
        return result[i] < result[j]
    })
    return result
}

Just as with the earlier Contains example, we need a type constraint here. Not every Go type works with the < operator: for example, structs don’t. Data types whose values can be unambiguously sorted into order, though, are referred to as ordered types. So we use constraints.Ordered, from the standard library, to express this limitation.

Again, this certainly isn’t a model implementation—it uses sort.Slice under the hood, which is slow because it uses reflection. That’s not necessary with generics, and we could implement some efficient sort algorithm such as Quicksort directly.

The important thing about this Sort function is not whether the code is any good—it isn’t—but that we can write it straightforwardly for any ordered type. So that unordered types needn’t feel left out, we could always provide a version where the user can pass in their own Less function, as before.

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.

However, before generics, first-class functions in Go were rather limited by the need to always specify the type of their parameters and results. That meant that it was difficult or impossible to use some of the most desirable features of first-class functions available in other languages.

An example of this kind of feature is mapping some function over a collection of elements. That is, applying the function to each element, with the final result being the transformed collection.

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.

This is nothing to do with Go’s map type, but it conveys the same idea of mapping one set of values to another; in this case, by applying some arbitrary function to each value.

Mapping a function over a slice

A Map function was difficult to write in Go without generics, because the signature of that arbitrary function is a problem. What type of parameter should it declare? We’d have to write a new version of the mapped function for each element type we needed.

Worse, we’d have to write a separate version of the Map function as well, because it has to declare the arbitrary function as a parameter. If the mapped function’s signature changes, so must the mapping function’s. How tiresome!

This is all much easier now. Let’s first of all work out what the type of the arbitrary function needs to be. Its job is to transform a value of some type E to another value of the same type, so it makes sense that its signature should be func(E) E. Here’s what a type definition for values of a function like that would look like:

type mapFunc[E any] func(E) E

For any type E, we’re saying—and it really is any type—a mapFunc[E] is a function that takes an E parameter and returns an E result.

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[E any](s []E, f mapFunc[E]) []E {
    result := make([]E, len(s))
    for i := range s {
        result[i] = f(s[i])
    }
    return result
}

For any type E, Map[E] takes a slice of E and a mapFunc[E], and returns a slice of E.

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, given a slice of string, we could map some function that takes a string and returns a string. Here’s one example using a familiar function of this kind from the standard library:

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

Filtering slice elements with a function

Let’s look at another popular functional pattern on slices. 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.

For example, suppose we have a slice of integers and we want to extract only the even values from it. We need some generic function Filter that takes an arbitrary slice, and an arbitrary function that decides which elements to keep and which to discard.

What can we deduce about the signature of this keep function, then? It must be:

type keepFunc[E any] func(E) bool

We’ll say that the semantics of a keepFunc are that it returns true if the element should be kept, or false if it should be dropped from the slice.

So now we can write Filter as a function that takes a slice and a keepFunc, and returns the filtered slice:

func Filter[E any](s []E, f keepFunc[E]) []E {
    result := []E{}
    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.

What kind of f would be useful? Suppose we want to filter a slice of integers to find only the even values.

We could write some function matching the keepFunc signature that returns true if its argument is even; that is, if dividing it by 2 gives a remainder of zero. Here it is:

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

Let’s try it out, by passing this function literal to Filter. The effect should be to produce a slice containing only even numbers:

s := []int{1, 2, 3, 4}
fmt.Println(Filter(s, func(v int) bool {
    return v%2 == 0
}))
// [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 very Go-like.

Passing a generic function to Filter

We’re not limited to passing only function literals to Filter. 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 write a generic keepFunc to pass to our generic Filter function? That is, a keepFunc function parameterized on some arbitrary type T? Generics within generics!

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

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

Stop, stop! We know this won’t work. Why? Because we can’t use the == operator with any. We can only use it 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
}

So far, so good, but can we use IsEven to filter some slice, by passing it to Filter? Let’s try:

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

Wonderful!

Reducing a slice to a single value

Map and Filter make perfect partners, but they’re even better when united with their best friend, Reduce. What does that do?

If Map uses a function to transform each element of a slice, and Filter uses a function to pick only the desired elements, then 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 reducing a sequence of values to a single value by some kind of computation.

For example, one simple way to reduce a slice of numbers would be to sum them all, producing the total as the result. If we had a Reduce function, we could do this by passing it a slice of numbers, along with some function that adds each element to the current running total.

In general, then, this arbitrary reduction function 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.

For a slice of element type E, then, the reduction function takes two parameters of type E and returns an E result. That sounds like func(E, E) E, so here’s a suitable type definition for a reduceFunc:

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

Now let’s try to write Reduce in terms of this definition:

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

For any type E, we’re saying, Reduce[E] takes a slice of E, a value of E, and a reduceFunc[E], and returns an E result.

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 in this case. 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)
// 10

Other reduction functions

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)
// 24

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

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

The effect of this reduceFunc is to join all the elements of s together into a single string.

Concurrent filtering

If we had large slices to deal with, and if the map, reduce, or filter operations on them were relatively expensive, it might be helpful to do these operations concurrently.

For example, suppose we had a slice of strings representing web URLs, and we wanted to filter them to extract only those URLs which respond with OK status.

We can imagine using our existing Filter implementation on this slice with some function that uses http.Get to call the URL and check the response status. But each request would take a fair amount of time (by computer standards): a few hundred milliseconds, perhaps.

Suppose each request takes about 250ms to complete, and there are 1,000 URLs to check. Filtering them sequentially would thus take more than two minutes.

Since we can make many HTTP requests at once, it seems silly not to start all these requests concurrently, and then wait for the responses to trickle in. The total filter time would then be a little more than the time of the slowest response, so of the order of 250ms.

That’s a pretty big speedup, and since all the tasks in this workload are independent of each other (making it what’s known as embarrassingly parallel), the speedup is linear with N. In other words, concurrent filtering of slice elements always takes about the same total time, no matter how large the slice.

Naturally, adding concurrency to something like Filter also adds a good deal of complication and extra code, but that’s okay: if it can be generic, then we only need to write it once! Indeed, some third-party libraries already provide a concurrent Filter and related functions.

Further reading

If you’ve already read my other blog posts introducing generics and type parameters, and you have an appetite for more, then you might enjoy my book Know Go: Generics. It explains Go’s support for generics in far more detail than there’s space to do here.

In chapter after sizzling chapter, we’ll learn all about type parameters and constraints, use generics to write fun and interesting constructs like concurrency-safe sets and caches, explore the new soon-to-be-standard slices and maps packages, and discuss when and how (and whether) you should introduce generics to your own projects.