How to use pointers to interface in go as internal data structure for collection-like types?

Question

TLDR; I need to use pointers to interface e.g. *Comparable as an internal Data's object in my Node as a part of Tree. Data should conform to pointer to Comparable interface that has only one method Less which compares two objects of Comparable interface type.

If I am using just Comparable as type for Data in Node, without pointer, everything works fine. However after I switch to *Comparable compiler gives strange errors and code won't compile

Code with Comparable:

package main

type Comparable interface {
    Less(than Comparable) bool
}

type Node struct {
    Data Comparable
}

func NewNode(data Comparable) *Node {
    return &Node{Data: data} }

type Tree struct {
    root *Node
}

func NewTree() *Tree {
    return &Tree{}
}

func (t *Tree) insert(data Comparable) {
    if t.root == nil || t.root.Data.Less(data) {
        t.root = NewNode(data)
    }
}

type Row struct {
    Row []string
}

func NewRow(row[] string) *Row {
    return &Row{Row: row}
}

func (r Row) Less(other Comparable) bool {
    return r.Row[0] < other.(Row).Row[0]
}

func main() {
    t := NewTree()
    t.insert(*NewRow([]string{"123"}))
    fmt.Printf("%v\n", t.root.Data.(Row).Row)
}

tests:

package main

import (
    "reflect"
    "testing"
)

func TestInsert(t *testing.T) {
    d := []string{"42"}
    tree := NewTree()
    tree.insert(*NewRow(d))
    if !reflect.DeepEqual(tree.root.Data.(Row).Row, d) {
        t.Error("returned elements are not matching")
    }
}

func TestInsert2x(t *testing.T) {
    d1 := []string{"42"}
    d2 := []string{"99"}
    tree := NewTree()
    tree.insert(*NewRow(d1))
    tree.insert(*NewRow(d2))
    if !reflect.DeepEqual(tree.root.Data.(Row).Row, d2) {
        t.Error("returned elements are not matching")
    }
}

However when I convert Comparable to *Comparable, everything breaks and the root cause is something like *Row is not equal to *Comparable compiler error:

for line return r.Row[0] < other.(*Row).Row[0]

Invalid type assertion: other.(*Row) (non-interface type *Comparable on left)

and for line if t.root == nil || t.root.Data.Less(data) {

Unresolved reference 'Less'

package main

type Comparable interface {
    Less(than *Comparable) bool
}

type Node struct {
    Data *Comparable
}

func NewNode(data *Comparable) *Node {
    return &Node{Data: data}
}

type Tree struct {
    root *Node
}

func NewTree() *Tree {
    return &Tree{}
}

func (t *Tree) insert(data *Comparable) {
    if t.root == nil || t.root.Data.Less(data) {
        t.root = NewNode(data)
    }
}

type Row struct {
    Row []string
}

func NewRow(row[] string) *Row {
    return &Row{Row: row}
}

func (r *Row) Less(other *Comparable) bool {
    return r.Row[0] < other.(*Row).Row[0]
}

func main() {
    t := NewTree()
    t.insert(NewRow([]string{"123"}))
    fmt.Printf("%v\n", t.root.Data.(*Row).Row)
}

tests:

package main

import (
    "reflect"
    "testing"
)

func TestInsert(t *testing.T) {
    d := []string{"42"}
    tree := NewTree()
    tree.insert(NewRow(d))
    if !reflect.DeepEqual(tree.root.Data.(*Row).Row, d) {
        t.Error("returned elements are not matching")
    }
}

func TestInsert2x(t *testing.T) {
    d1 := []string{"42"}
    d2 := []string{"99"}
    tree := NewTree()
    tree.insert(NewRow(d1))
    tree.insert(NewRow(d2))
    if !reflect.DeepEqual(tree.root.Data.(*Row).Row, d2) {
        t.Error("returned elements are not matching")
    }
}

The question is how to use *Comparable as type of Data in Node so that code above compiles. I tried a couple ugly options with interface{} type for Data and explicit casts everywhere. This approach I didn't like as it is very unsafe.

You can check all code parts in my github repo

Answer 1

Interfaces can accept both structs and pointers to structs.

You can pass in a pointer to Row (*Row) to Tree.insert(data Comparable), by combining your 1st Tree.insert(data Comparable) function definition with your 2nd main() function calls.

Here's a full running example, also on Go Playground: https://play.golang.org/p/Gh_RT3R-Fy0 .

package main

import (
    "fmt"
)

type Comparable interface {
    Less(than Comparable) bool
}

type Node struct {
    Data Comparable
}

func NewNode(data Comparable) *Node {
    return &Node{Data: data}
}

type Tree struct {
    root *Node
}

func NewTree() *Tree {
    return &Tree{}
}

func (t *Tree) insert(data Comparable) {
    if t.root == nil || t.root.Data.Less(data) {
        t.root = NewNode(data)
    }
}

type Row struct {
    Row []string
}

func NewRow(row []string) *Row {
    return &Row{Row: row}
}

func (r Row) Less(other Comparable) bool {
    return r.Row[0] < other.(*Row).Row[0]
}

func main() {
    t := NewTree()
    t.insert(NewRow([]string{"123"}))
    fmt.Printf("%v\n", t.root.Data.(*Row).Row)
}

That being said, this is brittle code since the Row.Less function accesses the underlying type of Comparable and assumes the array has at a 0 index value (length > 0).

func (r Row) Less(other Comparable) bool {
    return r.Row[0] < other.(*Row).Row[0]
}

It's much better to remove any dependency on the underlying type of Comparable when interface functions are called. You can do this augmenting the Comparable interface and Row.Less definition as follows. In this approach, there's no need to cast in the Row struct definition.

On Go Playground: https://play.golang.org/p/8-71-pEn-zK

type Comparable interface {
    Less(than Comparable) bool
    CompareValue() string
}

func (r Row) CompareValue() string {
    if len(r.Row) == 0 {
        return ""
    }
    return r.Row[0]
}

func (r Row) Less(other Comparable) bool {
    return r.CompareValue() < other.CompareValue()
}

For more information on pointer to interfaces, see the Go FAQ on using pointers to interfaces:

https://golang.org/doc/faq#pointer_to_interface

When should I use a pointer to an interface?

Almost never. Pointers to interface values arise only in rare, tricky situations involving disguising an interface value's type for delayed evaluation.

It is a common mistake to pass a pointer to an interface value to a function expecting an interface. The compiler will complain about this error but the situation can still be confusing, because sometimes a pointer is necessary to satisfy an interface. The insight is that although a pointer to a concrete type can satisfy an interface, with one exception a pointer to an interface can never satisfy an interface.

[...]

The one exception is that any value, even a pointer to an interface, can be assigned to a variable of empty interface type (interface{}). Even so, it's almost certainly a mistake if the value is a pointer to an interface; the result can be confusing.