在 Golang 中为递归函数实现生成器（yield）的惯用方法

Question

在 Python / Ruby / JavaScript / ECMAScript 6 中，可以使用yield语言提供的关键字编写生成器函数。在 Go 中，它可以使用一个 goroutine 和一个通道来模拟。编码以下代码显示了如何实现置换函数（abcd、abdc、acbd、acdb、...、dcba）：// $src/lib/lib.gopackage lib// private, starts with lowercase "p"func permutateWithChannel(channel chan<- []string, strings, prefix []string) {    length := len(strings)    if length == 0 {        // Base case        channel <- prefix        return    }    // Recursive case    newStrings := make([]string, 0, length-1)    for i, s := range strings {        // Remove strings[i] and assign the result to newStringI        // Append strings[i] to newPrefixI        // Call the recursive case        newStringsI := append(newStrings, strings[:i]...)        newStringsI = append(newStringsI, strings[i+1:]...)        newPrefixI := append(prefix, s)        permutateWithChannel(channel, newStringsI, newPrefixI)    }}// public, starts with uppercase "P"func PermutateWithChannel(strings []string) chan []string {    channel := make(chan []string)    prefix := make([]string, 0, len(strings))    go func() {        permutateWithChannel(channel, strings, prefix)        close(channel)    }()    return channel}以下是它的使用方法：// $src/main.gopackage mainimport (    "./lib"    "fmt")var (    fruits  = []string{"apple", "banana", "cherry", "durian"}    banned = "durian")func main() {    channel := lib.PermutateWithChannel(fruits)    for myFruits := range channel {        fmt.Println(myFruits)        if myFruits[0] == banned {            close(channel)            //break        }    }}笔记：break不需要该语句（上面注释），因为close(channel)会导致在下一次迭代中range返回false，循环将终止。问题如果调用者不需要所有的排列，则需要close()显式地对通道进行处理，否则通道不会被关闭，直到程序终止（发生资源泄漏）。另一方面，如果调用者需要所有的排列（即range循环直到结束），调用者必须不是close()通道。这是因为close()-ing 一个已经关闭的通道会导致运行时恐慌（请参阅规范中的此处）。但是，如果判断是否应该停止的逻辑不像上图那么简单，我觉得还是使用defer close(channel).问题实现这样的生成器的惯用方法是什么？习惯上，谁应该close()对通道负责——库函数还是调用者？像下面这样修改我的代码是否是个好主意，以便调用者defer close()无论如何都要对频道负责？

Answer 1

一、替代方案

前言：我会使用一个更简单的生成器，因为问题不关心生成器的复杂性，而是关心生成器和消费者之间的信号，以及消费者本身的调用。这个简单的生成器只生成从0to的整数9。

1.带函数值

通过传递一个简单的消费者函数，生成消费者模式更加清晰，它还有一个优点，即如果需要中止或任何其他操作，它可以返回一个值信号。

由于在示例中只有一个事件要发出信号（“中止”），消费者函数将具有bool返回类型，在需要中止时发出信号。

所以看这个简单的例子，消费者函数值传递给生成器：

func generate(process func(x int) bool) {

    for i := 0; i < 10; i++ {

        if process(i) {

            break

        }

    }

}

func main() {

    process := func(x int) bool {

        fmt.Println("Processing", x)

        return x == 3 // Terminate if x == 3

    }

    generate(process)

}

输出（在Go Playground上试试）：

Processing 0

Processing 1

Processing 2

Processing 3

请注意，使用者 ( process) 不需要是“本地”函数，它可以在 之外声明main()，例如，它可以是全局函数或来自另一个包的函数。

该解决方案的潜在缺点是它仅使用 1 个 goroutine 来生成和使用值。

2. 有渠道

如果你仍然想用频道来做，你可以。请注意，由于通道是由生成器创建的，并且由于消费者对从通道接收到的值进行循环（最好使用for ... range构造），因此生成器有责任关闭通道。解决此问题还允许您返回仅接收通道。

是的，关闭生成器中返回的通道最好作为延迟语句完成，因此即使生成器发生恐慌，消费者也不会被阻塞。但请注意，这个延迟关闭不是在generate()函数中，而是在匿名函数中generate()，作为一个新的 goroutine启动并执行；否则通道将在返回之前关闭generate()- 根本没有用......

如果您想从消费者处向生成器发出信号（例如中止而不生成更多值），您可以使用例如另一个通道，该通道传递给生成器。由于生成器只会“侦听”此通道，因此它也可以声明为生成器的仅接收通道。如果你只需要发出一个事件信号（在我们的例子中是中止），不需要在这个通道上发送任何值，一个简单的关闭就可以了。如果您需要向多个事件发送信号，可以通过在此通道上实际发送一个值来完成，即要执行的事件/操作（其中中止可能是多个事件中的一个）。

并且您可以使用该select语句作为处理在返回通道上发送值并观察传递给生成器的通道的惯用方式。

这是一个带有abort频道的解决方案：

func generate(abort <-chan struct{}) <-chan int {

    ch := make(chan int)

    go func() {

        defer close(ch)

        for i := 0; i < 10; i++ {

            select {

            case ch <- i:

                fmt.Println("Sent", i)

            case <-abort: // receive on closed channel can proceed immediately

                fmt.Println("Aborting")

                return

            }

        }

    }()

    return ch

}

func main() {

    abort := make(chan struct{})

    ch := generate(abort)

    for v := range ch {

        fmt.Println("Processing", v)

        if v == 3 { // Terminate if v == 3

            close(abort)

            break

        }

    }

    // Sleep to prevent termination so we see if other goroutine panics

    time.Sleep(time.Second)

}

输出（在Go Playground上试试）：

Sent 0

Processing 0

Processing 1

Sent 1

Sent 2

Processing 2

Processing 3

Sent 3

Aborting

这个解决方案的明显优势是它已经使用了 2 个 goroutines（1 个生成值，1 个消耗/处理它们），并且很容易扩展它以使用任意数量的 goroutines 作为返回的通道来处理生成的值生成器可以同时从多个 goroutine 中使用 - 通道可以安全地同时接收，数据竞争不会发生，按照设计；更多阅读：如果我正确使用通道，我是否需要使用互斥锁？

二、未解决问题的答案

goroutine 上的“未捕获”恐慌将结束 goroutine 的执行，但不会导致资源泄漏问题。但是，如果作为单独的 goroutine 执行的函数会在非恐慌的情况下释放由它分配的资源（在非延迟语句中），那么该代码显然不会运行并且会导致例如资源泄漏。

您没有观察到这一点，因为程序在主协程终止时终止（并且它不会等待其他非主协程完成 - 因此您的其他协程没有机会恐慌）。请参阅规范：程序执行。

但是要知道，panic()并且recover()是针对例外情况，它们不适用于诸如try-catchJava 中的异常和块之类的一般用例。例如，应该通过返回错误（并处理它们！）来避免恐慌，并且恐慌绝对不应该离开包的“边界”（例如panic()，recover()可能有理由在包实现中使用，但恐慌状态应该被“捕获” " 放在包裹里面，不要从里面拿出来）。

Answer 2

在我看来，生成器通常只是内部封闭的包装器。像这样的东西

package main

import "fmt"

// This function `generator` returns another function, which

// we define anonymously in the body of `generator`. The

// returned function _closes over_ the variable `data` to

// form a closure.

func generator(data int, permutation func(int) int, bound int) func() (int, bool) {

    return func() (int, bool) {

        data = permutation(data)

        return data, data < bound

    }

}

// permutation function

func increment(j int) int {

    j += 1

    return j

}

func main() {

    // We call `generator`, assigning the result (a function)

    // to `next`. This function value captures its

    // own `data` value, which will be updated each time

    // we call `next`.

    next := generator(1, increment, 7)

    // See the effect of the closure by calling `next`

    // a few times.

    fmt.Println(next())

    fmt.Println(next())

    fmt.Println(next())

    // To confirm that the state is unique to that

    // particular function, create and test a new one.

    for next, generation, ok := generator(11, increment, 17), 0, true; ok; {

        generation, ok = next()

        fmt.Println(generation)

    }

}

它看起来不像“范围”那么优雅，但对我来说在语义和句法上非常清晰。它有效http://play.golang.org/p/fz8xs0RYz9

Answer 3

我同意icza的回答。总结一下，有两种选择：

映射函数：使用回调来迭代集合。. 这样做的缺点是让控制流发挥作用。不是 Pythonic 生成器，因为它不返回可迭代序列。func myIterationFn(yieldfunc (myType)) (stopIterating bool)myGeneratormyIterationFn

通道：使用通道并警惕泄漏的 goroutine。可以转换myIterationFn为返回可迭代序列的函数。以下代码提供了此类转换的示例。

myMapper := func(yield func(int) bool) {

    for i := 0; i < 5; i++ {

        if done := yield(i); done {

            return

        }

    }

}

iter, cancel := mapperToIterator(myMapper)

defer cancel() // This line is very important - it prevents goroutine leaks.

for value, ok := iter(); ok; value, ok = iter() {

    fmt.Printf("value: %d\n", value)

}

这里以一个完整的程序为例。mapperToIterator做从映射函数到生成器的转换。Go 缺乏泛型需要从interface{}to 进行转换int。

package main

import "fmt"

// yieldFn reports true if an iteration should continue. It is called on values

// of a collection.

type yieldFn func(interface{}) (stopIterating bool)

// mapperFn calls yieldFn for each member of a collection.

type mapperFn func(yieldFn)

// iteratorFn returns the next item in an iteration or the zero value. The

// second return value is true when iteration is complete.

type iteratorFn func() (value interface{}, done bool)

// cancelFn should be called to clean up the goroutine that would otherwise leak.

type cancelFn func()

// mapperToIterator returns an iteratorFn version of a mappingFn. The second

// return value must be called at the end of iteration, or the underlying

// goroutine will leak.

func mapperToIterator(m mapperFn) (iteratorFn, cancelFn) {

    generatedValues := make(chan interface{}, 1)

    stopCh := make(chan interface{}, 1)

    go func() {

        m(func(obj interface{}) bool {

            select {

            case <-stopCh:

                return false

            case generatedValues <- obj:

                return true

            }

        })

        close(generatedValues)

    }()

    iter := func() (value interface{}, notDone bool) {

        value, notDone = <-generatedValues

        return

    }

    return iter, func() {

        stopCh <- nil

    }

}

func main() {

    myMapper := func(yield yieldFn) {

        for i := 0; i < 5; i++ {

            if keepGoing := yield(i); !keepGoing {

                return

            }

        }

    }

    iter, cancel := mapperToIterator(myMapper)

    defer cancel()

    for value, notDone := iter(); notDone; value, notDone = iter() {

        fmt.Printf("value: %d\n", value.(int))

    }

}