In this article I want to share with you few tricks that I learned in go that would allow you to write reusable code. I will start with code that is written for only one use case and refactor it to be reusable.

You can see all code from this blogpost in github repo.

How to reuse code in Go?

If you want something similar that you already have, what should you do? How do people avoid duplication without inheritance and generics?

TL;DR - Using golang interfaces and composition.

Instead of inheritance, you should use composition and accept interfaces instead of concrete types. Instead of generics, use narrow interfaces describing exactly what you need or if there is no other way and you want to be very generic - use empty interfaces interface{} with unboxing.

If you feel little uneasy about golang interfaces, I recommend you to read some tutorials first:

Algorithmic example

I was recently reading section about backtracking in The Algorithm Design Manual by Skiena. Backtracking is a very useful algorithm that can be used to solve puzzles, generate all possible permutations of given set or all it subsets.

Sudoku puzzle being solved by backtracking

In the book author describes there universal backtracking algorithm. Examples in the book are written in C and I decided that I would rewrite them to Go.

Core of alorithm is a Backtrack function, it uses problem specific functions:

IsSolution(a []elements, k int, n int)
ConstructCandidates(a []elements, k int, n int) []elements
ProcessSolution(a []elements, k int, n int)

To solve your problem, you just need to substitute those functions.

I succeeded in translating the algorithm to Go for the subset generation problem, you can see the code below.

package main

import (
    "fmt"
)

var total int

func Backtrack(a []bool, k int, input int) {
    if IsSolution(a, k, input) {
        ProcessSolution(a, k, input)
        return
    }
    k++

    candidates := ConstructCandidates(a, k, input)
    for _, c := range candidates {
        a[k-1] = c
        Backtrack(a, k, input)
    }
}

func IsSolution(a []bool, k int, n int) bool {
    return k == n
}

func ConstructCandidates(a []bool, k int, n int) []bool {
    return []bool{true, false}
}

func ProcessSolution(a []bool, k int, n int) {
    fmt.Printf("{")
    for i, v := range a {
        if v {
            fmt.Printf("%d", i)
        }
    }
    fmt.Printf("}\n")
    total++
}

func main() {
    a := make([]bool, 10)
    Backtrack(a, 0, 10)
    fmt.Println("total", total)
}

If you run the script it will print all possible subsets of range from 0 to 9 inclusive.

$  go run simplebacktrack.go 

{0123456789}
{012345678}
{012345679}
...
{8}
{9}
{}
total 1024

Algorithm works, but clearly the implementation isn't reusable, because Backtrack algorithm uses hardcoded functions specific to the problem.

The simplest generalization that we can make is to make Backtrack function customizable - pass an interface that implements all specific methods to the Backtrack function!

Extracting required functionality to interface

Let's define our interface - it should have almost the same methods that has our concrete implementation:

type BacktrackerImpl interface {
    IsSolution(a []interface{}, k int, input interface{}) bool

    ConstructCandidates(a []interface{}, k int, n interface{}) []interface{}

    ProcessSolution(a []interface{}, k int, n interface{})
}

Notice that slice of bool []bool was replaced with slice of empty interfaces []interface{}.

Empty interface is a powerful tool - it describes a type that implements at least 0 methods, which means that every type satisfies empty interface. Thanks to this property we could use our Backtracker with bools, integers and even with Cats (defined as named structs).

Changing code to implement interface (close look at empty interfaces)

Now we have to modify our subset algorithm to implement this interface:

// SubsetImpl implements BacktrackerImpl interface.
type SubsetImpl struct {
    total    int
}

func (b *SubsetImpl) IsSolution(a []interface{}, k int, n interface{}) bool {
    return k == n
}

func (b *SubsetImpl) ConstructCandidates(a []interface{}, k int, n interface{}) []interface{} {
    // 1. We can't just return []bool{true, false} here.
    result := make([]interface{}, 2)
    result[0] = true
    result[1] = false
    return result
}

func (b *SubsetImpl) ProcessSolution(a []interface{}, k int, n interface{}) {
    fmt.Printf("{")
    for i, v := range a {
        if v.(bool) { // 2. We convert the type from interface{} to bool.
            fmt.Printf("%d", i)
        }
    }
    fmt.Printf("}\n")
    b.total++
}

First we create a struct with one field - total. total was previously a global variable, now it's stored inside the instance of the struct.

We then define methods required by the interface. They take as a receiver pointer to the instance of SubsetImpl type.

It shouldn't be a big problems, because we had those functions (ConstructCandidates, ProcessSolution, etc) defined in our first algorithm. The only difference is that those functions took slice of bools as a first argument and we have to change it to slice of empty interfaces.

To achieve this we only need to make two two small changes:

Instead of returning []bool{true, false} we need to allocate slice of empty interfaces and fill it with boolean values. Slice of empty interfaces isn't 'any slice'
We convert the type from interface{} to bool. If the value stored in empty interface was of some other type, program will panic. You can learn more about type conversions from type assertions and type switches article.

Changing original code to use new interface

Backtrack function already takes three parameters, so at this point it's better to make it a method of a type and store data in a struct, than add another parameters.

type Backtracker struct {
    impl BacktrackerImpl
}

// New creates new backtrackers, it takes implementation of backtracking
// problem as an argument.
func New(i BacktrackerImpl) *Backtracker {
    return &Backtracker{impl: i}
}

// Backtrack explores solutions of the problem. It's a little simplified
// version (working for all concrete examples in this blogpost).
func (b Backtracker) Backtrack(a []interface{}, k int, input interface{}) {
    if b.impl.IsSolution(a, k, input) {
        b.impl.ProcessSolution(a, k, input)
        return
    }
    k++

    candidates := b.impl.ConstructCandidates(a, k, input)
    for _, c := range candidates {
        a[k-1] = c
        b.Backtrack(a, k, input)
    }
}

Looks like we have all the pieces we need! Our new implementation can be used as follows:

func main() {
    a := make([]interface{}, 10)
    impl := &SubsetImpl{}
    b := backtrack.New(impl)
    b.Backtrack(a, 0, 10)
    fmt.Println("total", impl.total)
}

Using backtracking algorithm to solve another problem

Another implementation example in generator of permutations. It uses integers instead of bytes.

type PermutationImpl struct {
    total    int
}

func (b *PermutationImpl) IsSolution(a []interface{}, k int, n interface{}) bool {
    return k == n
}

func (b *PermutationImpl) ConstructCandidates(a []interface{}, k int, n interface{}) []interface{} {

    inPerm := make(map[int]bool)

    for i := 0; i < k-1; i++ {
        inPerm[a[i].(int)] = true
    }

    result := []interface{}{}

    for i := 1; i <= n.(int); i++ {
        if !inPerm[i] {
            result = append(result, i)
        }
    }

    return result
}

func (b *PermutationImpl) ProcessSolution(a []interface{}, k int, n interface{}) {
    fmt.Println(a)
    b.total++
}

Permutation implementation can be used in similar way to SubsetImpl:

impl := &PermutationImpl{}
b := backtrack.New(impl)

Thanks to empty interfaces everything just works!

Summary

I hope that you enjoyed this blogpost. Definitely reusing code in go can be challenging without inheritance and generics, but it's definitely possible.

This example doesn't exhaust all the possible ways to write reusable code in go. I would like to hear your battle stories from the work on go codebases, share your experience in the comment section or write me an email at justyna.ilczuk@gmail.com.

You can see all code from this blogpost in github repo.