Can an anonymous go function call itself?

Question

I'm just running through the Tour of Go, and got to the tree walker exercise. Its obvious recursion, but closing the channel is a special case after the final pop off the call stack. Anyway, I ended up implementing it thusly:

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
    var walker func(t *tree.Tree, ch chan int)
    walker = func(t *tree.Tree, ch chan int) {
        if (t.Left != nil) {
            walker(t.Left, ch)
        }
        ch <- t.Value
        if (t.Right != nil) {
            walker(t.Right, ch)
        }
    }
    walker(t, ch)
    close(ch)
}

So far my impression of go is that they prefer to avoid saying things if they can, so the declaration of var walker before the definition seems off. Perhaps I missed some detail that would allow a function to refer to itself without the declaration? It would be a little nicer if it could be:

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
    func(t *tree.Tree, ch chan int) {
        if (t.Left != nil) {
            __me__(t.Left, ch)
        }
        ch <- t.Value
        if (t.Right != nil) {
            __me__(t.Right, ch)
        }
    }(t, ch)
    close(ch)
}

This is a simple trivia question, but I'm new enough to the language that I am not finding the answer...

There is no such feature in the language. See this : https://github.com/golang/go/issues/226 — eugenioy, Jul 23 '17 at 18:31
Possible duplicate of [Define a recursive function within a function in Go](https://stackoverflow.com/questions/28099441/define-a-recursive-function-within-a-function-in-go/28099510#28099510). — icza, Jul 24 '17 at 05:51
`So far my impression of go is that they prefer to avoid saying things if they can` That's an odd impression. Most people observe the opposite, and in fact, it's pretty much the exact opposite of a core Go philosophy, which is: "don't hide complexity". — Jonathan Hall, Jul 24 '17 at 09:09
@Flimzy, I am admittedly new to `go`, but just going through the tour, things like `for (i := 0; i < 10; i++)` -> `for i := 0; i < 10; i++` -> `for ; sum < 1000;` -> `for sum < 1000` -> `for`, and `var thing := x*x; if x > 10` -> `if v := x*x; x > 10`... Thats what i meant by _avoid saying things if they can_. In any case I get your point about _don't hide complexity_. Thanks! — Lucas, Jul 24 '17 at 18:37
@icza, yup, definitely a duplicate. My `googling` skillz failed me. Thanks for pointing it out. — Lucas, Jul 24 '17 at 18:42

score 5 · Answer 1 · answered Jul 23 '17 at 18:13

5

You cannot use a variable before it is declared, and it is not yet declared inside its initialization statement.

So yes, the declaration line is required, and no, there is no way to avoid it.

answered Jul 23 '17 at 18:13

Milo Christiansen

3,204
2
23
36

Jonathan · Accepted Answer · 2017-07-24T15:35:53.953

I agree with @milo-chirstiansen that it isn't possible for an anonymous func to refer to its instance in its declaration.

If you're trying to get a feel for writing idiomatic Go code, it might look a bit more like this, doing away with the anonymous func:

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
    Walker(t, ch)
    close(ch)
}

// Walker does the things, made to be called recursively
func Walker(t *tree.Tree, ch chan int) {
    if t.Left != nil {
        Walker(t.Left, ch)
    }
    ch <- t.Value
    if t.Right != nil {
        Walker(t.Right, ch)
    }
}

You might find this interesting...

Go allows some interesting things that aren't possible in other languages. This sometimes requires thinking a little differently about your code.

Frances Campoy gave a talk at GopherCon 2016 about his storied history with the concept of nil in Go. One of his examples of how nil can be used beautifully and idiomatically, involved a solution to receiving the sum for a binary tree. Below is a link starting with this piece of his talk and I'd recommend checking it out if you have the time. ref: https://youtu.be/ynoY2xz-F8s?t=16m28s

I realize you don't have control over the Tree struct in your example, but if you did, here's how your code might look: https://play.golang.com/p/iM10NQXfgw

package main

import "fmt"

// A Tree is a binary tree with integer values.
type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}

// Walk loads value into channel; caller is responsible for providing and closing chan
func (t *Tree) Walk(ch chan int) {

    // Super interesting: Go supports the calling of a func on a nil instance of a struct
    if t == nil {
        return // return nothing
    }

    t.Left.Walk(ch)  // recursively call Walk on left node
    ch <- t.Value
    t.Right.Walk(ch) // recursively call Walk on right node
}

func main() {
    // Initial value for our tree; I'm not being very idiomatic with this
    tree := &Tree{
        Left:  &Tree{Value: 2},
        Value: 1,
        Right: &Tree{Left: &Tree{Value: 4}, Value: 3},
    }

    ch := make(chan int)

    // Load values into chan in separate goroutine
    // to prevent blocking
    go func() {
        tree.Walk(ch)
        close(ch)
    }()

    // Write each val added to chan until all values
    // have been written and chan is closed
    for val := range ch {
        fmt.Println(val)
    }
}

1

2

3

4

Just for clarity, `Walker` should be `walker`, right? You wouldn't want to expose the implementation detail... Also, perhaps I am confused, but in your method example, shouldn't left walk come before the value? — Lucas, Jul 23 '17 at 23:29
Walker/walker: As you probably know, using `walker` with lower-case would mean the func isn't exported (i.e. can't be called by another package). Whether or not this should be exported would depend on your planned use of this func, which I'm unaware of. However, it's also the case that having the `Walker` func is entirely unnecessary and I included it only to show how the small change of splitting the anonymous func out of `Walker` makes a difference in clarity and (from my perspective) adds to simplicity/maintainability, which is a key focus for Go. — Jonathan, Jul 24 '17 at 15:30
left walk before value: hmm.. it didn't occur to me that you might be wanting to feed values from left-to-right. My background is in file systems and online storage, so I always visualize moving from the root out to the nodes - perhaps this isn't the proper way to view a walker. I researched a bit and it appears there are different patterns for approaching this. I used the "Pre-Order" pattern while you were using "In-Order" traversal. I should've followed the pattern you were already using - making adjustments to code now. — Jonathan, Jul 24 '17 at 15:34
sweet, not nitpicking, just trying to get the idioms/patterns right and ensure I am understanding... Thanks for the reply — Lucas, Jul 24 '17 at 18:30

score 1 · Answer 3 · answered Jul 24 '17 at 11:13

1

It should be possible to avoid this, by combining runtime.Caller and reflect.Call.

But this is nothing even resembling idiomatic Go, so I don't think it applies to your practical situation, although it does address the letter of your question. :)

answered Jul 24 '17 at 11:13

Jonathan Hall

75,165
16
143
189

Can an anonymous go function call itself?

3 Answers3

You might find this interesting...