Exercise 8
Getting Started With Go
You're going to need to get Go code running. Download/install Go tools: a command-line compiler, or IDE, or whatever you like. Start by getting a “hello world” running. (There's one in the lecture slides.)
Download and extract the code skeleton for this exercise. The code includes an outline of how to organize your work for this exercise, some tests that should pass when you're done (more below), and a place for your main
function that will satisfy the Go tools (and your IDE where relevant).
It's not a requirement, but maybe go through A Tour of Go: it will prepare you better for some of the stuff we'll be covering in this section of the course.
Go Hailstone
The Hailstone sequence provided many useful examples in Haskell, so let's revisit it in Go. In hailstone.go
, write a function Hailstone
that calculates the next element of a hailstone sequence: for even n
, it should return n/2
and for odd n
, it should return 3*n+1
.
Hailstone(17) == 52
Hailstone(18) == 9
The function should take and return a uint
type:
func Hailstone(n uint) uint { … }
Hailstone Sequence
In this question, we will build the hailstone sequence in a Go array. Put code for this section in hailstone.go
.
Attempt 1: grow the slice
In this implementation, start with an empty []uint{}
slice. Calculate the elements of the hailstone sequence and use the append
function to add it to the end of a new slice as you go.
It is probably easiest to do this iteratively (not recursively). You should take a uint
argument and return a []uint
slice. In pseudocode (since ==
isn't defined on slices):
HailstoneSequenceAppend(5) == [5, 16, 8, 4, 2, 1]
Attempt 2: pre-allocate the array
Appending to an slice is expensive this way: we are constantly allocating and de-allocating arrays at they grow. Maybe we can do better? Write a function HailstoneSequenceAllocate
that generates the same result in a different way…
It is easy enough to figure out how big an array we need: we did it before. This time, start by calculating the length of array we need by iterating Hailstone
. (In the above example, you should realize you need an array of length 6.)
Then, use the make
function to create a slice and allocate an array of that many uint
s. Then fill it in and return it (no append
ing, just set array elements). Results should be the same as HailstoneSequenceAppend
in all cases.
Test and Benchmark
Go has built-in testing and benchmarking functionality. The exer8_test.go
provided in the ZIP above provides tests for the requirements of this exercise.
At this point, the test for hailstone functionality should pass. If you comment-out the Point
tests (or go finish that question below and come back here), you should pass the other tests:
go test exer8 -v
There are also some short benchmarks that we can use to see which of the hailstone sequence functions is actually faster:
go test exer8 -bench=.
Add a comment to your hailstone.go
indicating the relative speed of the two HailstoneSeq*
functions (thus proving to us that you have figured out how to run Go tests).
A Struct for Points
In points.go
, create a struct Point
for two-dimensional points: \((x,y)\) values. The struct should have two fields, x
and y
, both float64
.
Create a function NewPoint
that creates a Point
given x
and y
values: this would be a constructor in any other language, but in Go, it's just a function that returns a Point
.
[Note: we don't really need a constructor this simple and could use a Go struct literal instead, but we're creating the constructor anyway. There are, of course, cases where some work is required to construct a struct instance.]
String Representation
There is a perfectly reasonable default string representation for structs in Go (which is used if you fmt.Print
them), but we can make it nicer.
Create a String()
method on Point
using fmt.Sprintf
to output the usual parentheses-and-commas representation of a point:
pt := NewPoint(3, 4.5)
fmt.Println(pt) // should print (3, 4.5)
fmt.Println(pt.String() == "(3, 4.5)") // should print true
Hint: The %v
format seems nice.
Calculate Norm
One more method to add: the Euclidean norm of the point: add up the squares of the components and take the square root.
If everything is working, this should print true
.
pt := NewPoint(3, 4)
fmt.Println(pt.Norm() == 5.0)
Also, the provided tests should all pass.
Submitting
Submit your files through CourSys for Exercise 8.