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:
:= []string{"a", "b", "c"}
s .Println(Map(s, strings.ToUpper))
fmt// 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:
:= []int{1, 2, 3, 4}
s .Println(Filter(s, IsEven[int]))
fmt// 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 {
:= make(S, len(s))
result for i := range s {
[i] = f(s[i])
result}
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:
:= []string{"a", "b", "c"}
s .Println(Map(s, strings.ToUpper))
fmt// 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 {
:= S{}
result for _, v := range s {
if f(v) {
= append(result, v)
result }
}
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
:
:= []int{1, 2, 3, 4}
s .Println(Filter(s, func(v int) bool {
fmtreturn 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:
.Println(Filter(s, IsEven[int]))
fmt// 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 {
:= init
cur for _, v := range s {
= f(cur, v)
cur }
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:
:= []int{1, 2, 3, 4}
s := Reduce(s, 0, func(cur, next int) int {
sum return cur + next
})
.Println(sum)
fmt// Output:
// 10
Other reduction operations
Let’s try another reduction operation. What about multiplication, for example?
:= []int{1, 2, 3, 4}
s := Reduce(s, 1, func(cur, next int) int {
p return cur * next
})
.Println(p)
fmt// Output:
// 24
We’re not restricted to just numerical operations, of course. Here’s a reduction involving strings, which just concatenates them all together:
:= []string{"a", "b", "c"}
s := Reduce(s, "", func(c, n string) string {
j return c + n
})
.Println(j)
fmt// Output:
// abc
If you think this is cool (I do!) then you might enjoy my book, Know Go. It’s a complete introduction to generics in Go and what new ways of programming it opens up, along with some other interesting new features of the language, such as iterators. Enjoy!