Code Along - Arrays and Slices in Go

Learning objectives

Now that we have seen that Euclid’s GCD algorithm offers an enormous improvement of efficiency over a trivial approach — even on a fast modern computer — we wonder whether the same will be true for the sieve of Eratosthenes.

Both the sieve of Eratosthenes and a simpler approach for prime finding generate an array of boolean variables to store whether a given integer is prime. Therefore, to prepare ourselves to implement these algorithms, we will need to learn how Go implements arrays.

Setup

Create a new folder called arrays in your go/src directory, and then create a new file within the go/src/arrays folder called main.go, which we will edit in this lesson.

In main.go, add the following starter code.

package main

import (
    "fmt"
)

func main() {
    fmt.Println("Arrays (and slices).")
}

Code along video

Beneath the video, we provide a detailed summary of the topics and code covered in the code along.

At the bottom of this page, you will have the opportunity to validate your work via auto-graded assessments that evaluate the functions covered in the code along.

Although we strongly suggest completing the code along on your own, you can find completed code from the code along in our course code repository.

Code along summary

Introduction to arrays

In Go, arrays have a fixed, constant size. This means that you cannot declare an array of length n, and once you declare an array, you are not allowed to change the length of the array. (Don’t worry, we will soon have a workaround for these quirks.)

We can declare arrays in the same way that we declare any other variable, using the var keyword, followed by the name of the array, followed by the type of the array. For example, to declare an array of integers called list of length 6, we can use the following notation:

var list [6]int

Let’s use this idea to declare an array of integers of length 6 and then print the array to the console.

func main() {
    fmt.Println("Arrays (and slices).")

    // arrays in Go have a fixed, constant size.
    var list [6]int // gives 6 default (zero) values
    fmt.Println(list)
}

STOP: Open a command line terminal and navigate into the folder containing your code by using the command cd go/src/arrays. Then, compile your code by executing the command go build. You can then run the code by executing the command arrays.exe on Windows or ./arrays on Mac.

As a result of running our code, we should see six zeroes printed to the console because when we declare an array of length n, each element of the array receives the default value for the type of the array, which we know in the case of an int type is zero. If we were to declare an array of strings, then each variable in the array would have value equal to the empty string ("").

Note: In Go, every variable in an array must have the same type.

In Go, the i-th value of the array list is denoted list[i]. Go is like many modern languages, and the pseudocode that we showed earlier, in that it uses 0-based indexing. That is, an array having n values has indices ranging between 0 and n – 1. Let’s use these ideas to set the first value of our array list equal to -8; to do so, we use the notation list[0] = -8 as if we were setting any other variable equal to a value.

func main() {
    fmt.Println("Arrays (and slices).")

    // arrays in Go have a fixed, constant size.
    var list [6]int // gives 6 default (zero) values
    list[0] = -8
    fmt.Println(list)
}

We can even set a value of the array where the index is given by some arithmetic expression, as shown below.

func main() {
    fmt.Println("Arrays (and slices).")

    // arrays in Go have a fixed, constant size.
    var list [6]int // gives 6 default (zero) values
    list[0] = -8
    i := 3
    list[2*i-4] = 17 // 2*i - 4 = 2
    fmt.Println(list)
}

We can determine the length of a given array by using the built-in function len(). This is helpful in setting the final value of an array list, since we know that the indices of list range between 0 and len(list) – 1. We use this idea below to set the final element of list equal to 43.

func main() {
    fmt.Println("Arrays (and slices).")

    // arrays in Go have a fixed, constant size.
    var list [6]int // gives 6 default (zero) values
    list[0] = -8
    i := 3
    list[2*i-4] = 17 // 2*i - 4 = 2
    list[len(list)-1] = 43
    fmt.Println(list)
}

STOP: Compile and run your code. We have set the elements of list at indices 0, 2, and 5, and you should see the output -8 0 17 0 0 43 printed to the console.

Setting an element of an array with index out of bounds

You might wonder what happens if we try to set the value of list for an index that is outside of the range from 0 to len(list) – 1. Whether the index is negative or larger than len(list) – 1, we will obtain a compiler error when attempting to set an element of an array with such an index because the index is out of bounds. The following two additional lines show examples of setting elements of an array that would lead to such a compiler error.

func main() {
    fmt.Println("Arrays (and slices).")

    // arrays in Go have a fixed, constant size.
    var list [6]int // gives 6 default (zero) values
    list[0] = -8
    i := 3
    list[2*i-4] = 17 // 2*i - 4 = 2
    list[len(list)-1] = 43
    list[len(list)] = 7 // compiler error!
    list[-4] = 2 // compiler error!
    fmt.Println(list)
}

Let’s make sure to comment out the two lines in func main() that result in a compiler error so that this error does not occur later on.

func main() {
    fmt.Println("Arrays (and slices).")

    // arrays in Go have a fixed, constant size.
    var list [6]int // gives 6 default (zero) values
    list[0] = -8
    i := 3
    list[2*i-4] = 17 // 2*i - 4 = 2
    list[len(list)-1] = 43
    //list[len(list)] = 7 // compiler error!
    //list[-4] = 2 // compiler error!
    fmt.Println(list)
}

When arrays fall short

Let us consider a function FactorialArray() that takes an integer n as input and returns an array fact of length n+1 such that fact[k] is equal to k!. Using what we have learned, we might write this function in the following way.

//FactorialArray takes as input an integer n.
//It returns the slice of length n+1 whose k-th element is k! 
func FactorialArray(n int) [n+1]int {
    if n < 0 {
        panic("Error: negative input given to FactorialArray().")
    }

    var fact [n+1]int

    fact[0] = 1

    for k := 1; k <= n; k++ {
        fact[k] = fact[k-1] * k
    }

    return fact
}

Unfortunately, when we compile and run main.go, we obtain a compiler error: non-constant array bound n+1. This error corresponds to the function signature, and is related to our us of [n+1]int as the return type of FactorialArray(). Go does not like this statement, or for that matter the declaration var fact [n+1]int, because of what we stated before: in Go, arrays must have fixed length equal to some constant integer value.

For now, place a multiline comment around FactorialArray() using /* and */. We will return to it after learning a bit more.

From arrays to slices

Fortunately, we will have an easy workaround when we want to declare an array whose length is equal to a variable (or an expression involving a variable). Our solution is to a data type called a slice.

Much like with declaring an array or any other variable, to declare a slice, we use the keyword var, followed by the name of the slice, followed by the type of the slice. But this time, we will not specify the length of the slice. For example, to declare a slice of integers called a, we can use var a []int. Let’s then print a to the console.

func main() {
    fmt.Println("Arrays (and slices).")

    //...

    var a []int
    fmt.Println(a)
}

When we compile and run this code, we see only [] printed to the console because a currently has no elements and has the special value nil. We need an initial length for our slice. Say that we would like for our slice to have length n, where n is an integer. To do so, we set a using a = make([]int, n).

func main() {
    fmt.Println("Arrays (and slices).")

    //...

    var a []int
    n := 4
    a = make([]int, n)
    fmt.Println(a)
}

Now when we compile and run this code, we see what we might expect printed to the console: 0 0 0 0, corresponding to four default integer values. Furthermore, we can set values of a using the same notation for setting values of an array.

func main() {
    fmt.Println("Arrays (and slices).")

    //...

    var a []int
    n := 4
    a = make([]int, n)
    a[0] = 42
    a[2] = -17
    fmt.Println(a)
}

Although we wanted to introduce arrays by showing their declaration, Go has a one-line declaration for slices that we will use most of the time. In particular, we can declare a slice b of length, say, n+2, with the single line b := make([]int, n+2).

func main() {
    fmt.Println("Arrays (and slices).")

    //...

    var a []int
    n := 4
    a = make([]int, n)
    a[0] = 42
    a[2] = -17
    fmt.Println(a)

    b := make([]int, n+2)
    fmt.Println(b)
}

A function for computing all factorials

We can now use what we have learned about slices to update our implementation of FactorialArray() as shown below. We still refer to this function as FactorialArray() even though it will technically return a slice.

//FactorialArray takes as input an integer n.
//It returns the slice of length n+1 whose k-th element is k! 
func FactorialArray(n int) []int {
    if n < 0 {
        panic("Error: negative input given to FactorialArray().")
    }

    fact := make([]int, n+1)
    fact[0] = 1

    for k := 1; k <= n; k++ {
        fact[k] = fact[k-1] * k
    }

    return fact
}

Arrays are pass by value, and slices are pass by reference

You might be wondering what here is new. After all, once we declare a slice, we use it in the same way that we use an array.

When we introduced functions in a previous code along, we pointed out that Go uses “pass by value” for input parameters. This means that when we pass a variables such as an integer or string into a function, Go creates a copy of that variable and edits the copy, so that the original variable’s value is preserved.

This behavior is the same for arrays, but not for slices. Consider the following two functions, which change the first element of an input array or slice to 1.

func ChangeFirstElementArray(a [6]int) {
    a[0] = 1
}

func ChangeFirstElementSlice(a []int) {
    a[0] = 1
}

When we call these functions using the code below, we will see that although ChangeFirstArray() creates a copy of b, ChangeFirstSlice() edits c within the function. As a result, you might like to think about slices as pass by reference, since when we pass a slice into a function, we are able to change the underlying data.

func main() {
    fmt.Println("Arrays (and slices).")

    //...

    var c [5]int // is equal to [0, 0, 0, 0, 0]
    d := make([]int, 5) // also is equal to [0, 0, 0, 0, 0]

    ChangeFirstElementArray(c)
    ChangeFirstElementSlice(d)

    fmt.Println(c) // prints [0, 0, 0, 0, 0]
    fmt.Println(d) // prints [1, 0, 0, 0, 0]
}

Later in the course, we will discuss more about the distinction between arrays and slices and what is happening when a function takes a slice as a parameter. For now, in practice, we will use slices most of the time throughout this course, and in fact, we will typically use the term “array” to refer to a slice.

Finding the minimum value of a slice

In the main text, we introduced functions for finding the minimum of two integers and the minimum of three integers. Writing infinitely many functions, one for each possible number of input variables, is not a path we want to take. Instead, we would like to take an arbitrary number of inputs.

One way to take the minimum of an arbitrary number of variables is to assume that these variables are stored in a slice list. After ensuring that the list is not empty, we can declare a variable m to hold our minimum that is equal to the initial element of list and then range over the remaining elements of list, updating m every time that we encounter an element that is smaller than the current value of m.

//MinIntegerArray takes as input a slice of integers.
//It returns the minimum value in the array.
func MinIntegerArray(list []int) int {
	if len(list) == 0 {
		panic("Error: Empty list given as input().")
	}

	var m int // default value = 0

	// range over list, updating m if we find bigger value
	for i := 0; i < len(list); i++ { 
		if list[i] < m {
			m = list[i]
		}
	}

	return m
}

STOP: MinIntegerArray() looks correct, but it suffers from a bug. What is it?

Our current implementation of MinIntegerArray() will work for some arrays. However, let us consider what happens if every integers in list is positive, such as for the slice [3, 2, 1]. For this input slice, MinIntegerArray() will declare m, which has a default value of zero, and as the function ranges over list, it will never find an element list[i] that is smaller than m. As a result, m is never updated, and MinIntegerArray() will return 0.

One workaround for this bug is to declare m to be equal to list[0], as follows. Because we set m initially, we can start our ranging at index 1.

//MinIntegerArray takes as input a slice of integers.
//It returns the minimum value in the array.
func MinIntegerArray(list []int) int {
	if len(list) == 0 {
		panic("Error: Empty list given as input.")
	}

	m := list[0]

	// range over list, updating m if we find bigger value
	for i := 1; i < len(list); i++ { 
		if list[i] < m {
			m = list[i]
		}
	}

	return m
}

An alternative approach is to instead declare m to be equal to zero, but then in the for loop update m either if we are considering the first element or if the current element of list is smaller than m. We can then preserve our ranging over the entire slice, and we get to use the “or” keyword (||) that we learned about in the previous lesson.

//MinIntegerArray takes as input a slice of integers.
//It returns the minimum value in the array.
func MinIntegerArray(list []int) int {
	if len(list) == 0 {
		panic("Error: Empty list given as input.")
	}

	var m int // has default value of zero

	// range over list, updating m if we find bigger value
	for i := 0; i < len(list); i++ { 
		if i == 0 || list[i] < m {
			m = list[i]
		}
	}

	return m
}

Shorthand ranging tricks

Go offers two shorthand tricks for working with arrays that we will apply to the second correct implementation of MinIntegerArray() as an example.

The first trick addresses the commonness of ranging over all the indices of an array or slice. Rather than needing the lengthy statement for i := 0; i < len(list); i++, we can instead apply the shorthand for i := range list. We apply this change to MinIntegerArray() below.

//MinIntegerArray takes as input a slice of integers.
//It returns the minimum value in the array.
func MinIntegerArray(list []int) int {
	if len(list) == 0 {
		panic("Error: Empty list given as input.")
	}

	var m int // has default value of zero

	// range over list, updating m if we find bigger value
	for i := range list { // equivalent to for i:=0; i<len(list); i++
		if i == 0 || list[i] < m {
			m = list[i]
		}
	}

	return m
}

The second trick allows us to range over both the indices and the values of an array or slice. If we intend to use list[i], and especially if we plan to use it more than once, we can use the ranging shorthand for i, val := range list. Here, val is a variable (that we are able to name what we like) holding the current value of list[i].

//MinIntegerArray takes as input a slice of integers.
//It returns the minimum value in the array.
func MinIntegerArray(list []int) int {
	if len(list) == 0 {
		panic("Error: Empty list given as input.")
	}

	var m int // default value = 0

	// range over list, updating m if we find bigger value
	for i, val := range list {
		if i == 0 || val < m {
			m = val
		}
	}

	return m
}

We may also wish to range over only the values of an array, as exemplified by our first correct implementation of MinIntegerArray(). In this case, because i is not being used, we use an underscore (_) to indicate to Go that we do not intend to declare a variable equal to the current array index.

//MinIntegerArray takes as input a slice of integers.
//It returns the minimum value in the slice.
func MinIntegerArray(list []int) int {
	if len(list) == 0 {
		panic("Error: Empty list given as input.")
	}

	m := list[0]

	// range over list, updating m if we find bigger value
	for _, val := range list { 
		if val < m {
			m = val
		}
	}

	return m
}

STOP: This last implementation of MinIntegerArray() has a minor inefficiency. What is it?

Variadic functions

We may also want to find the minimum of an arbitrary collection of input integers without assuming that these integers are contained within an array. A variadic function is a function can take an arbitrary number of variables.

In Go, we use the notation vars ...type in a function’s parameters to indicate that we wish to take an arbitrary number of variables having type type. The variables vars will be stored in a slice of type []type, which we can then access as we like. The following MinIntegers() variadic function takes an arbitrary number of integers, which are stored in a slice numbers. We range over this slice in the same way that we ranged over list in MinIntegerArray().

//MinIntegers takes as input an arbitrary collection of integers.
//It returns the minimum value among the input integers.
func MinIntegers(numbers ...int) int {
	if len(numbers) == 0 {
		panic("Error: No integers given as input.")
	}

	var m int // default value = 0

	// range over numbers, updating m if we find bigger value
	for i, val := range numbers {
		if i == 0 || val < m {
			m = val
		}
	}

	return m
}

Note how similar MinIntegers() is to MinIntegerArray(); the only difference is the inputs that they take. In programming, any time that we see very similar code arising in our work, a red alert should go off in our brains telling us to use a subroutine. This way, we will only have to write (and debug) half as much code.

In this particular case, because we have already implemented MinIntegerArray(), we can use it as a subroutine in MinIntegers(). We will say much more about subroutines as this course progresses.

//MinIntegers takes as input an arbitrary collection of integers.
//It returns the minimum value among the input integers.
func MinIntegers(numbers ...int) int {
        if len(numbers) == 0 {
		panic("Error: No integers given as input.")
	}
	return MinIntegerArray(numbers)
}

We are now ready to return to apply what we have learned about arrays and slices to implement and compare the prime finding algorithms that we introduced in the main text. How fast could the sieve of Eratosthenes be? Join us to find out!