Exercises

Average

• Write a function that calculates the average of a float64 slice.

Answer

• The following function calculates the average:

package main
func average(xs []float64) (avg float64) { //<1>
    sum := 0.0
    switch len(xs) {
    case 0:                 //<2>
        avg = 0
    default:                //<3>
        for _, v := range xs {
            sum += v
        }
        avg = sum / float64(len(xs)) //<4>
    }
    return  //<5>
}

At 1 we use a named return parameter. If the length of xs is zero 2, we return 0. Otherwise 3, we calculate the average. At 4 we convert the value to a float64 to make the division work as len returns an int. Finally, at 5 we reutrn our avarage.

Bubble sort

• Write a function that performs a bubble sort on a slice of ints. From [bubblesort]:

It works by repeatedly stepping through the list to be sorted, comparing eachpair of adjacent items and swapping them if they are in the wrong order. Thepass through the list is repeated until no swaps are needed, which indicatesthat the list is sorted. The algorithm gets its name from the way smallerelements “bubble” to the top of the list.

It also gives an example in pseudo code:

procedure bubbleSort( A : list of sortable items )
  do
    swapped = false
    for each i in 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  while swapped
end procedure

Answer

• Bubble sort isn’t terribly efficient. For (n) elements it scales (O(n^2)).But bubble sort is easy to implement:

func main() {
    n := []int{5, -1, 0, 12, 3, 5}
    fmt.Printf("unsorted %v\n", n)
    bubblesort(n)
    fmt.Printf("sorted %v\n", n)
}
func bubblesort(n []int) {
    for i := 0; i < len(n)-1; i++ {
        for j := i + 1; j < len(n); j++ {
            if n[j] < n[i] {
                n[i], n[j] = n[j], n[i]
            }

Because a slice is a reference type, the bubblesort function works anddoes not need to return a sorted slice.

For-loop II

• Take what you did in exercise to write the for loop and extend it a bit.Put the body of the for loop - the fmt.Printf - in a separate function.

Answer

1. <{{src/for-func.go}}

Fibonacci

• The Fibonacci sequence starts as follows: (1, 1, 2, 3, 5, 8, 13, \ldots)Or in mathematical terms: (x1 = 1; x_2 = 1; x_n = x{n-1} + x_{n-2}\quad\forall n > 2).

Write a function that takes an int value and givesthat many terms of the Fibonacci sequence.

Answer

• The following program calculates Fibonacci numbers:

package main
import "fmt"
func fibonacci(value int) []int {
    x := make([]int, value) 1
    x[0], x[1] = 1, 1       2
    for n := 2; n < value; n++ {
        x[n] = x[n-1] + x[n-2] 3
    }
    return x 4
}
func main() {
    for _, term := range fibonacci(10) { 5
        fmt.Printf("%v ", term)
    }
}

At 1 we create an array to hold the integers up to the value given inthe function call. At 2 we start the Fibonacci calculation. Then 3:(xn = x{n-1} + x{n-2}). At 4 we return the _entire array.And at 5 we use the range keyword to “walk” the numbers returned by theFibonacci function. Here up to 10. Finally, we print the numbers.

Var args

• Write a function that takes a variable number of ints and print each integer on a separate line.

Answer

• For this we need the {…}-syntax to signal we define afunction that takes an arbitrary number of arguments.

package main
import "fmt"
func main() {
    printthem(1, 4, 5, 7, 4)
    printthem(1, 2, 4)
}
func printthem(numbers ...int) {
    for _, d := range numbers {
        fmt.Printf("%d\n", d)
    }
}

Functions that return functions

• Write a function that returns a function that performs a (+2) on integers. Name the function plusTwo.You should then be able do the following:

p := plusTwo()
fmt.Printf("%v\n", p(2))

Which should print 4. See .

• Generalize the function from above and create a plusX(x) which returns functions that add x to an integer.

Answer

• Define a new function that returns a function: return func(x int) int { return x + 2 }Function literals at work, we define the +2–function right there in the return statement.

func main() {
   p2 := plusTwo()
   fmt.Printf("%v\n",p2(2))
}
func plusTwo() func(int) int { 1
    return func(x int) int { return x + 2 } 2
}

• Here we use a closure:

func plusX(x int) func(int) int { 1
   return func(y int) int { return x + y } 2
}

Here 1, we again define a function that returns a function.We use the local variable x in the function literal at 2.

Maximum

• Write a function that finds themaximum value in an int slice ([]int).

Answer

• This function returns the largest int in the slice \var{l}:

func max(l []int) (max int) {   1
    max = l[0]
    for _, v := range l {   2
        if v > max {    3
            max = v
        }
    }
    return 4
}

At 1 we use a named return parameter.At 2 we loop over l. The index of the element is not important.At 3, if we find a new maximum, we remember it.And at 4 we have a “lone” return; the current value of max is now returned.

Map function

A map()-function is a function that takesa function and a list. The function is applied toeach member in the list and a new list containingthese calculated values is returned.Thus:

( \mathrm{map}(f(), (a1,a_2,\ldots,a{n-1},an)) = (f(a_1), f(a_2),\ldots,f(a{n-1}), f(a_n)) )

• Write a simplemap()-function in Go. It is sufficient for this function only to work for ints.

Answer

• A possible answer:

func Map(f func(int) int, l []int) []int {
    j := make([]int, len(l))
    for k, v := range l {
        j[k] = f(v)
    }
    return j
}
func main() {
    m := []int{1, 3, 4}
    f := func(i int) int {
        return i * i
    }
    fmt.Printf("%v", (Map(f, m)))
}

Stack

• Create a simple stack which can hold afixed number of ints. It does not have to grow beyond this limit.Define push – put something on the stack – and pop– retrieve something from the stack – functions. The stack should bea LIFO (last in, first out) stack.

A stack.

• Write a String method whichconverts the stack to a string representation.The stack in the figure could be represented as: [0:m] [1:l] [2:k] .

Answer

• First we define a new type that represents a stack; we need anarray (to hold the keys) and an index, which points to the last element.Our small stack can only hold 10 elements.

type stack struct {
    i    int
    data [10]int
}

Next we need the push and pop functions to actuallyuse the thing. First we show the wrong solution!

In Go, data passed to functions is passed-by-value meaning a copyis created and given to the function. The first stab for the functionpush could be:

func (s stack) push(k int) {
    if s.i+1 > 9 {
            return
    }
    s.data[s.i] = k
    s.i++
}

The function works on the s which is of the type stack. Touse this we just call s.push(50), to push the integer 50 onthe stack. But the push function gets a copy of s, so it isnot working on the real thing. Nothing gets pushed to ourstack. For example the following code:

var s stack
s.push(25)
fmt.Printf("stack %v\n", s);
s.push(14)
fmt.Printf("stack %v\n", s);

prints:

stack [0:0]
stack [0:0]

To solve this we need to give the function push a pointerto the stack. This means we need to change push from

func (s stack) push(k int)

to

func (s *stack) push(k int).

We should now use new() (see ).in to create a pointer to a newlyallocated stack, so line 1 from the example above needs to bes := new(stack) .

And our two functions become:

func (s *stack) push(k int) {
    s.data[s.i] = k
    s.i++
}
func (s *stack) pop() int {
    s.i--
    ret := s.data[s.i]
    s.data[s.i] = 0
    return ret
}

Which we then use as follows:

func main() {
    var s stack
    s.push(25)
    s.push(14)
    fmt.Printf("stack %v\n", s)
}

• fmt.Printf("%v") canprint any value (%v) that satisfies the Stringer interface(see ).For this to work we only need to define a String() function forour type:

func (s stack) String() string {
    var str string
    for i := 0; i <= s.i; i++ {
        str = str + "[" +
            strconv.Itoa(i) + ":" + strconv.Itoa(s.data[i]) + "]"
    }
    return str
}