进行通用算法

Question

I can't figure out a clean way to implement an algorithm that will work on any type.

The following code will produce errors trying to convert a string or a typed slice into interfaces, and you can't compare interface{} objects: invalid operation: result[0] > result[n - 1] (operator > not defined on interface)

func main() {
    c := Algo("abc")
    //...
    c := Algo([3]int{1,2,3})
    //...
}

func Algo(list []interface{}) chan []interface{} {
    n := len(list)
    out := make(chan []interface{})
    go func () {
        for i := 0; i < n; i++ {
            result := make([]interface{}, n)
            copy(result, list)
            // an actually useful algorithm goes here:
            if (result[0] > result[n-1]) {
                result[0], result[n-1] = result[n-1], result[0]
            }
            out <- result
        }
        close(out)
    }()
    return out
}

Although it's a pain (I think it should be automatic), I can manually box and unbox typed slices into interface{}s, the real problem above is the comparison. And it just keeps getting more and more kludgy.

a := [3]int{1,2,3}
b := make([]interface{}, len(a))
for i, _ := range a {
    b[i] = a[i]
}

I've even thought of using vector.Vector, but so many people say never to use them.

So should I just implement the same algorithm for int slices and strings? What about slices of myObject? I can make an interface with a custom comparison func, but then how do I make it work with standard types?

Answer 1

You can do this in Go using interfaces. A function that takes an interface type is generic in the sense that it doesn't care about the data representation of the underlying concrete type. It does everything through method calls.

To make a generic version of your algorithm then, you have to identify all of the capabilities that the algorithm requires of the data objects and you have to define methods that abstract these capabilities. The abstract method signatures become method sets of interfaces.

To make a type compatible with this kind of generic algorithm, you define methods on the type to satisfy the interface of the algorithm parameter.

I'll take your example code and show one way to do this. Most of the required capabilities happen to be covered by sort.Interface so I chose to embed it. Only one other capability is needed, one to make a copy of the data.

type algoContainer interface {
    sort.Interface
    Copy() algoContainer
}

Below is a complete working program made from your example code.

package main

import (
    "fmt"
    "sort"
)

func main() {
    s1 := sortableString("abc")
    c1 := Algo(s1)
    fmt.Println(s1, <-c1)

    s2 := sortable3Ints([3]int{1,2,3})
    c2 := Algo(&s2)
    fmt.Println(s2, <-c2)
}

type algoContainer interface {
    sort.Interface
    Copy() algoContainer
}

type sortableString []byte
func (s sortableString) Len() int { return len(s) }
func (s sortableString) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s sortableString) Less(i, j int) bool { return s[i] < s[j] }
func (s sortableString) Copy() algoContainer {
   return append(sortableString{}, s...)
}
func (s sortableString) String() string { return string(s) }

type sortable3Ints [3]int
func (sortable3Ints) Len() int { return 3 }
func (s *sortable3Ints) Swap(i, j int) {
   (*s)[i], (*s)[j] = (*s)[j], (*s)[i]
}
func (s sortable3Ints) Less(i, j int) bool { return s[i] < s[j] }
func (s sortable3Ints) Copy() algoContainer { c := s; return &c }

func Algo(list algoContainer) chan algoContainer {
    n := list.Len()
    out := make(chan algoContainer)
    go func () {
        for i := 0; i < n; i++ {
            result := list.Copy()
            // actually useful:
            if result.Less(n-1, 0) {
                result.Swap(n-1, 0)
            }
            out <- result
        }
        close(out)
    }()
    return out
}