Problems understanding usage of `interface{}` in Go

Question

I'm trying to port an algorithm from Python to Go. The central part of it is a tree built using dicts, which should stay this way since each node can have an arbitrary number of children. All leaves are at the same level, so up the the lowest level the dicts contain other dicts, while the lowest level ones contain floats. Like this:

tree = {}
insert(tree, ['a', 'b'], 1.0)
print tree['a']['b']

So while trying to port the code to Go while learning the language at the same time, this is what I started with to test the basic idea:

func main() {
    tree := make(map[string]interface{})
    tree["a"] = make(map[string]float32)
    tree["a"].(map[string]float32)["b"] = 1.0
    fmt.Println(tree["a"].(map[string]float32)["b"])
}

This works as expected, so the next step was to turn this into a routine that would take a "tree", a path, and a value. I chose the recursive approach and came up with this:

func insert(tree map[string]interface{}, path []string, value float32) {
    node := path[0]
    l := len(path)
    switch {
    case l > 1:
        if _, ok := tree[node]; !ok {
            if l > 2 {
                tree[node] = make(map[string]interface{})
            } else {
                tree[node] = make(map[string]float32)
            }
        }
        insert(tree[node], path[1:], value) //recursion
    case l == 1:
        leaf := tree
        leaf[node] = value
    }
}

This is how I imagine the routine should be structured, but I can't get the line marked with "recursion" to work. There is either a compiler error, or a runtime error if I try to perform a type assertion on tree[node]. What would be the correct way to do this?

Answer 1

Go is perhaps not the ideal solution for generic data structures like this. The type assertions make it possible, but manipulating data in it requires more work that you are used to from python and other scripting languages.

About your specific issue: You are missing a type assertion in the insert() call. The value of tree[node] is of type interface{} at that point. The function expects type map[string]interface{}. A type assertion will solve that.

Here's a working example:

package main

import "fmt"

type Tree map[string]interface{}

func main() {
    t := make(Tree)
    insert(t, []string{"a", "b"}, 1.0)

    v := t["a"].(Tree)["b"]
    fmt.Printf("%T %v\n", v, v)

    // This prints: float32 1
}

func insert(tree Tree, path []string, value float32) {
    node := path[0]
    len := len(path)

    switch {
    case len == 1:
        tree[node] = value

    case len > 1:
        if _, ok := tree[node]; !ok {
            tree[node] = make(Tree)
        }

        insert(tree[node].(Tree), path[1:], value) //recursion
    }
}

Note that I created a new type for the map. This makes the code a little easier to follow. I also use the same 'map[string]interface{}` for both tree nodes and leaves. If you want to get a float out of the resulting tree, another type assertion is needed:

leaf := t["a"].(Tree)["b"]  // leaf is of type 'interface{}`.
val := leaf.(float32)

Answer 2

well... the problem is that you're trying to code Go using Python idioms, and you're making a tree with... hashtables? Huh? Then you have to maintain that the keys are unique and do a bunch of otherstuff, when if you just made the set of children a slice, you get that sort of thing for free.

I wouldn't make a Tree an explicit map[string]interface{}. A tree and a node on a tree are really the same thing, since it's a recursive datatype.

type Tree struct {
    Children []*Tree
    Value    interface{}
}

func NewTree(v interface{}) *Tree {
    return &Tree{
        Children: []*Tree{},
        Value:    v,
    }
}

so to add a child...

func (t *Tree) AddChild(child interface{}) {
    switch c := child.(type) {
    case *Tree:
        t.Children = append(t.Children, c)
    default:
        t.Children = append(t.Children, NewTree(c))
    }
}

and if you wanted to implement some recursive function...

func (t *Tree) String() string {
    return fmt.Sprint(t.Value)
}

func (t *Tree) PrettyPrint(w io.Writer, prefix string) {
    var inner func(int, *Tree)
    inner = func(depth int, child *Tree) {
        for i := 0; i < depth; i++ {
            io.WriteString(w, prefix)
        }
        io.WriteString(w, child.String()+"\n") // you should really observe the return value here.
        for _, grandchild := range child.Children {
            inner(depth+1, grandchild)
        }
    }
    inner(0, t)
}

something like that. Any node can be made the root of some tree, since a subtree is just a tree itself. See here for a working example: http://play.golang.org/p/rEx43vOnXN

There are some articles out there like "Python is not Java" (http://dirtsimple.org/2004/12/python-is-not-java.html), and to that effect, Go is not Python.