A sorting example

Recall the Bubblesort exercise, where we sorted an array of integers:

  1. func bubblesort(n []int) {
  2.     for i := 0; i < len(n)-1; i++ {
  3.         for j := i + 1; j < len(n); j++ {
  4.             if n[j] < n[i] {
  5.                 n[i], n[j] = n[j], n[i]
  6.             }
  7.         }
  8.     }
  9. }

A version that sorts strings is identical except for the signature of thefunction: func bubblesortString(n []string) { / … / } . Using thisapproach would lead to two functions, one for each type. By using interfaces wecan make this more generic. Let’s create a new function that willsort both strings and integers, something along the lines of this non-workingexample:

  1. func sort(i []interface{}) {  1
  2.     switch i.(type) {         2
  3.     case string:              3
  4.         // ...
  5.     case int:
  6.         // ...
  7.     }
  8.     return /* ... */          4
  9. }

Our function will receive a slice of empty interfaces at 1. We then 2 use atype switch to find out what the actual type of the input is. And then 3then sort accordingly. And, when done, return 4 the sorted slice.

But when we call this function with sort([]int{1, 4, 5}), it fails with:“cannot use i (type []int) as type []interface { } in function argument”

This is because Go can not easily convert to a slice of interfaces.Just converting to an interface is easy, but to a slice is much more costly.The full mailing list discussion on this subject can be found at[go_nuts_interfaces]. To keep a long story short: Go does not (implicitly) convert slices for you.

So what is the Go way of creating such a “generic” function?Instead of doing the type inference ourselves with a type switch, we letGo do it implicitly:The following steps are required:

  • Define an interface type (called Sorter here) with a number of methodsneeded for sorting. We will at least need a function to get the length of theslice, a function to compare two values and a swap function.
  1. type Sorter interface {
  2.     Len() int           // len() as a method.
  3.     Less(i, j int) bool // p[j] < p[i] as a method.
  4.     Swap(i, j int)      // p[i], p[j] = p[j], p[i] as a method.
  5. }
  • Define new types for the slices we want to sort. Note that we declare slice types:
  1. type Xi []int
  2. type Xs []string
  • Implementation of the methods of the Sorter interface.For integers:
  1. func (p Xi) Len() int               {return len(p)}
  2. func (p Xi) Less(i int, j int) bool {return p[j] < p[i]}
  3. func (p Xi) Swap(i int, j int)      {p[i], p[j] = p[j], p[i]}

And for strings:

  1. func (p Xs) Len() int               {return len(p)}
  2. func (p Xs) Less(i int, j int) bool {return p[j] < p[i]}
  3. func (p Xs) Swap(i int, j int)      {p[i], p[j] = p[j], p[i]}
  • Write a generic Sort function that works on the Sorter interface.
  1. func Sort(x Sorter) { 1
  2.     for i := 0; i < x.Len() - 1; i++ { 2
  3.         for j := i + 1; j < x.Len(); j++ {
  4.             if x.Less(i, j) {
  5.                 x.Swap(i, j)
  6.             }
  7.         }
  8.     }
  9. }

At 1 x is now of the Sorter type and using the defined methods for this interface we implementBubblesort at 2.

Now we can use our generic Sort function as follows:

  1. ints := Xi{44, 67, 3, 17, 89, 10, 73, 9, 14, 8}
  2. strings := Xs{"nut", "ape", "elephant", "zoo", "go"}
  5. Sort(ints)
  6. fmt.Printf("%v\n", ints)
  7. Sort(strings)
  8. fmt.Printf("%v\n", strings)