recursion – 在Golang中为递归函数实现生成器(yield)的惯用方法

在Python / Ruby / JavaScript / ECMAScript 6中,可以使用语言提供的yield关键字编写生成器函数.在Go中,可以使用goroutine和channel模拟它.

代码

以下代码显示了如何实现置换函数(abcd,abdc,acbd,acdb,…,dcba)：

// $src/lib/lib.go

package 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,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,len(strings))
    go func() {
        permutateWithChannel(channel,prefix)
        close(channel)
    }()
    return channel
}

以下是它的使用方法：

// $src/main.go

package main

import (
    "./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() – 已经关闭的通道会导致运行时混乱(见here in the spec).但是,如果确定它是否应该停止的逻辑并不像上面所示那么简单,我认为最好使用延迟关闭(通道).

问题

>实现这样的生成器的惯用方法是什么？
>惯用,谁应该负责关闭()频道 – 库函数或调用者？
>如下所示修改我的代码是一个好主意,这样调用者有责任推迟关闭()无论如何？

在库中,修改：

go func() {
        permutateWithChannel(channel,prefix)
        close(channel)
    }()

对此：

go permutateWithChannel(channel,prefix)

在调用者中,修改：

func main() {
    channel := lib.PermutateWithChannel(fruits)
    for myFruits := range channel {
        fmt.Println(myFruits)
        if myFruits[0] == banned {
            close(channel)
        }
    }
}

对此：

func main() {
    channel := lib.PermutateWithChannel(fruits)
    defer close(channel)    // <- Added
    for myFruits := range channel {
        fmt.Println(myFruits)
        if myFruits[0] == banned {
            break           // <- Changed
        }
    }
}

>尽管通过执行上面的代码无法观察到,并且算法的正确性不受影响,但在调用者close()s通道之后,运行库代码的goroutine在尝试发送到关闭的通道时应该会发生混乱.下一次迭代,如here in the spec所述,导致它终止.这会导致任何负面副作用吗？
>库函数的签名是func(strings [] string)chan [] string.理想情况下,返回类型应为< -chan []字符串,以将其限制为仅接收.但是,如果是负责关闭()频道的呼叫者,则无法将其标记为“仅接收”,因为close()内置函数不适用于仅接收频道.解决这个问题的惯用方法是什么？