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.
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
}
Currently, it is not possible to build a solution that respects all your criteria. It will be possible once generics are implemented. Or you could try building one using reflect, but that will yield a complex and potentially slow solution... so I generally advise against using reflect for something as simple as this (see second snippet below).
What you can do right now is to use something like:
func FindFirst(n int, f func(int) bool) int {
for i := 0; i < n; i++ {
if f(i) {
return i
}
}
return -1
}
// in your code (s is the slice, e the value you are searching for)
i := FindFirst(len(s), func(i int) bool {
return s[i] == e
})
if i != -1 {
// i is the index of the element with value e
}
This, as you can imagine, does not make much sense... as it's arguably simpler, faster, and more idiomatic to simply write out the loop explicitly:
// in your code (s is the slice, e the value you are searching for)
for i, v := range s {
if v == e {
_ = i // i is the index of the element with value e
break
}
}
Obviously, this whole approach (linear scan) is only reasonable if the number of elements in the slice is small. If your slice is big and changes rarely, it would arguably make more sense (from a time complexity perspective) to sort it (sort.Slice) first and then do binary searches (sort.Search) on the sorted slice. Or, alternatively, you could use a map instead: in which case (assuming keys are small) lookup would be O(1).