在Go中的界面{}上搜索界面{}的函数

Question

I'm trying to implement a function that takes an element of any type and a slice of the same type and search the first inside the second, giving it's position as result or -1 otherwise.

I'm not a Go expert, so my first thought was to pass the element to search as interface{} and the slice as []interface{}, but it didn't really work.

Here's what I tried:

package main

import (
    "fmt"
)

func IsElementInListWithPos(element interface{}, list []interface{}) int {
    for i := range list {
        if list[i] == element {
            return i
        }
    }

    return -1
}

func main() {
    list1 := []int{1, 2, 3, 4, 5, 6}
    list2 := []string{"a", "b", "c", "d"}
    pos1 := IsElementInListWithPos(3, list1)
    pos2 := IsElementInListWithPos("a", list2)
    fmt.Println(pos1, pos2)
}

It gives me the following errors:

cannot use list (type []int) as type []interface {} in argument to IsElementInListWithPos
cannot use list2 (type []string) as type []interface {} in argument to IsElementInListWithPos

Any idea how I could solve this issue without actually using two different functions? Thanks in advance.

Answer 1

The sort package demonstrates how interfaces can be used to implement algorithms in a type-independent way.

Linear search requires two essential operations that depend on the haystack element type, Len and Equal. So we can write the following Haystack interface and a Search function that using it:

type Haystack interface {
    Len() int
    Equal(int, interface{}) bool
}

func Search(haystack Haystack, needle interface{}) int {
    for i := 0; i < haystack.Len(); i++ {
        if haystack.Equal(i, needle) {
            return i
        }
    }
    return -1
}

This makes writing implementations for Haystack simple, but not type-safe:

type Strings []string

func (s Strings) Len() int                        { return len(s) }
func (s Strings) Equal(i int, x interface{}) bool { return s[i] == x.(string) }

type Ints []int

func (s Ints) Len() int                        { return len(s) }
func (s Ints) Equal(i int, x interface{}) bool { return s[i] == x.(int) }

func main() {
    strings := []string{"b", "a", "c", "d"}
    fmt.Println(Search(Strings(strings), "c")) // 2
    fmt.Println(Search(Strings(strings), "e")) // -1

    ints := []int{2, 1, 3, 4}
    fmt.Println(Search(Ints(ints), 3)) // 2
    fmt.Println(Search(Ints(ints), 5)) // -1
}

Note the type assertions in the Equal methods. To make this type-safe we have to get rid of the interface{} argument to Equal:

type Haystack interface {
    Len() int
    Equal(int) bool
}

func Search(haystack Haystack) int {
    for i := 0; i < haystack.Len(); i++ {
        if haystack.Equal(i) {
            return i
        }
    }
    return -1
}

type Strings struct {
    hs     []string
    needle string
}

func (s Strings) Len() int         { return len(s.hs) }
func (s Strings) Equal(i int) bool { return s.hs[i] == s.needle }

type Ints struct {
    hs     []int
    needle int
}

func (s Ints) Len() int         { return len(s.hs) }
func (s Ints) Equal(i int) bool { return s.hs[i] == s.needle }

func main() {
    strings := []string{"b", "a", "c", "d"}
    fmt.Println(Search(Strings{strings, "c"})) // 2
    fmt.Println(Search(Strings{strings, "e"})) // -1

    ints := []int{2, 1, 3, 4}
    fmt.Println(Search(Ints{ints, 3})) // 2
    fmt.Println(Search(Ints{ints, 5})) // -1
}

This made both the interface implementations and using the Search function much more complicated.

The moral of the story is that using interfaces this way requires a sufficiently complicated algorithm to be worth the trouble. If writing the interface implementation for a particular type is more work than writing the concrete implementation for the algorithm, well, then just write the concrete functions you need:

func SearchStr(haystack []string, needle string) int {
    for i, x := range haystack {
        if x == needle {
            return i
        }
    }
    return -1
}

func SearchInt(haystack []int, needle int) int {
    for i, x := range haystack {
        if x == needle {
            return i
        }
    }
    return -1
}

func main() {
    strings := []string{"b", "a", "c", "d"}
    fmt.Println(SearchStr(strings, "c")) // 2
    fmt.Println(SearchStr(strings, "e")) // -1

    ints := []int{2, 1, 3, 4}
    fmt.Println(SearchInt(ints, 3)) // 2
    fmt.Println(SearchInt(ints, 5)) // -1
}