Exercises

Map function with interfaces

• Use the answer from the earlier map exercise but nowmake it generic using interfaces. Make it at least work forints and strings.

Answer

• package main
  

func main() { m := []e{1, 2, 3, 4} s := []e{"a", "b", "c", "d"} mf := Map(m, mult2) sf := Map(s, mult2) fmt.Printf("%v\n", mf) fmt.Printf("%v\n", sf)}

Pointers

• Suppose we have defined the following structure:

type Person struct {
    name string
    age     int
}

What is the difference between the following two lines?

var p1 Person
p2 := new(Person)

• What is the difference between the following two allocations?

func Set(t *T) {
    x = t
}

and

func Set(t T) {
    x= &t
}

Answer

• The expression, var p1 Person allocates a Person-value to p1. The type of p1 is Person.The second line: p2 := new(Person) allocates memory and assigns a pointer to p2. The type of p2 is*Person.

• In the first function, x points to the same thing that t does, which is the same thing that theactual argument points to. So in the second function, we have an “extra” variable containing a copy of theinteresting value. In the second function, x points to a new (heap-allocated) variable t which containsa copy of whatever the actual argument value is.

Linked List

• Make use of the package container/list to createa (doubly) linked list. Push the values 1, 2 and 4 to the list and thenprint it.

• Create your own linked list implementation. And perform the same actionsas above.

Answer

• The following is the implementation of a program using doublylinked lists from container/list.

package main
import (
    "container/list"
    "fmt"
)
func main() {
    l := list.New()
    l.PushBack(1)
    l.PushBack(2)
    l.PushBack(4)
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Printf("%v\n", e.Value)
    }
}

• The following is a program implementing a simple doublylinked list supporting int values.

package main
import (
    "errors" 1
    "fmt"
)
type Value int 2
type Node struct { 3
    Value
    prev, next *Node
}
type List struct {
    head, tail *Node
}
func (l *List) Front() *Node { 4
    return l.head
}
func (n *Node) Next() *Node {
    return n.next
}
func (l *List) Push(v Value) *List {
    n := &Node{Value: v} 5
    if l.head == nil { 6
        l.head = n
    } else {
        l.tail.next = n 7
        n.prev = l.tail 8
    }
    l.tail = n 9
    return l
}
var errEmpty = errors.New("List is empty")
func (l *List) Pop() (v Value, err error) {
    if l.tail == nil { 10
        err = errEmpty
    } else {
        v = l.tail.Value     11
        l.tail = l.tail.prev 12
        if l.tail == nil {
            l.head = nil 13
        }
    }
    return v, err
}
func main() {
    l := new(List)
    l.Push(1)
    l.Push(2)
    l.Push(4)
    for n := l.Front(); n != nil; n = n.Next() {
        fmt.Printf("%v\n", n.Value)
    }
    fmt.Println()
    for v, err := l.Pop(); err == nil; v, err = l.Pop() {
        fmt.Printf("%v\n", v)
    }
}

Import <1> the packages we will need. At <2> we declare a type for the value our list will contain,this is not strictly neccesary. And at <3> we declare a type for the each node in our list.At <4> we define the Front method for our list.When pushing, create a new Node <5> with the provided value. If the list is empty <6>,put the new node at the head. Otherwise <7> put it at the tail and make sure <8>the new node points back to the previously existing one. At <9> we re-adjust tailto the newly inserted node.

In the Pop 10 method, we return an error if the list is empty. If it is not empty 11we save the last value. And then 12 discard the last node from the list. Finally at 13we make sure the list is consistent if it becomes empty.

Cat

• Write a program which mimics the Unix program cat.

• Make it support the -n flag, where each line is numbered.

• The solution to the above question given in contains a bug. Can you spot and fix it?

Answer

• The following is implemention of cat which also supports a -n flag to number each line.

package main
import (
    "bufio"
    "flag"
    "fmt"
    "io" 1
    "os"
)
var numberFlag = flag.Bool("n", false, "number each line") // <<2>>
func cat(r *bufio.Reader) { 3
    i := 1
    for {
        buf, e := r.ReadBytes('\n') 4
        if e == io.EOF {            5
            break
        }
        if *numberFlag { 6
            fmt.Fprintf(os.Stdout, "%5d  %s", i, buf)
            i++
        } else { 7
            fmt.Fprintf(os.Stdout, "%s", buf)
        }
    }
    return
}
func main() {
    flag.Parse()
    if flag.NArg() == 0 {
        cat(bufio.NewReader(os.Stdin))
    }
    for i := 0; i < flag.NArg(); i++ {
        f, e := os.Open(flag.Arg(i))
        if e != nil {
            fmt.Fprintf(os.Stderr, "%s: error reading from %s: %s\n",
                os.Args[0], flag.Arg(i), e.Error())
            continue
        }
        cat(bufio.NewReader(f))
    }
}

At 1 we include all the packages we need. Here 2 we define a new flag “n”, which defaults to off. Note that we get the help (-h) for free. Start the function 3 that actually reads the file’s contents and displays it; Read one line at the time at 4. And stop 5 if we hit the end. If we should number each line, print the line number and then the line itself 6. Otherwise 7 we could just print the line.

• The bug show itself when the last line of the input does notcontain a newline. Or worse, when the input contains one line without aclosing newline nothing is shown at all. A better solution is the followingprogram.

package main
import (
    "bufio"
    "flag"
    "fmt"
    "io"
    "os"
)
var numberFlag = flag.Bool("n", false, "number each line")
func cat(r *bufio.Reader) {
    i := 1
    for {
        buf, e := r.ReadBytes('\n')
        if e == io.EOF && string(buf) == "" {
            break
        }
        if *numberFlag {
            fmt.Fprintf(os.Stdout, "%5d  %s", i, buf)
            i++
        } else {
            fmt.Fprintf(os.Stdout, "%s", buf)
        }
    }
    return
}
func main() {
    flag.Parse()
    if flag.NArg() == 0 {
        cat(bufio.NewReader(os.Stdin))
    }
    for i := 0; i < flag.NArg(); i++ {
        f, e := os.Open(flag.Arg(i))
        if e != nil {
            fmt.Fprintf(os.Stderr, "%s: error reading from %s: %s\n",
                os.Args[0], flag.Arg(i), e.Error())
            continue
        }
        cat(bufio.NewReader(f))
    }
}

Method calls

• Suppose we have the followingprogram. Note the package container/vector was once partof Go, but was removed when the append built-in was introduced.However, for this question this isn’t important. The package implementeda stack-like structure, with push and pop methods.

package main
import "container/vector"
func main() {
    k1 := vector.IntVector{}
    k2 := &vector.IntVector{}
    k3 := new(vector.IntVector)
    k1.Push(2)
    k2.Push(3)
    k3.Push(4)
}

What are the types of k1, k2 and k3?

• Now, this program compiles and runs OK. All the Pushoperations work even though the variables are of a different type. Thedocumentation for Push says:

func (p *IntVector) Push(x int)Push appends x to the end of the vector.

So the receiver has to be of type *IntVector, why does the codeabove (the Push statements) work correctly then?

Answer

• The type of k1 is vector.IntVector. Why? We usea composite literal (the {}), so we get a value of that typeback. The variable k2 is of vector.IntVector, because wetake the address (&) of the composite literal. And finallyk3 has also the type vector.IntVector, because newreturns a pointer to the type.

• The answer is given in [go_spec] in the section “Calls”,where among other things it says:

A method call x.m() is valid if the method set of (the type of)xcontains m and the argument list can be assigned to the parameter listof m. If x is addressable and &x’s method setcontains m, x.m() is shorthand for (&x).m().

In other words because k1 is addressable and*vector.IntVector does have the Push method, thecall k1.Push(2) is translated by Go into(&k1).Push(2) which makes the type system happy again (andyou too – now you know this).¹⁴