Go 語(yǔ)言 匿名函數(shù)

原文鏈接：https://gopl-zh.github.io/ch5/ch5-06.html

5.6. 匿名函數(shù)

擁有函數(shù)名的函數(shù)只能在包級(jí)語(yǔ)法塊中被聲明，通過(guò)函數(shù)字面量（function literal），我們可繞過(guò)這一限制，在任何表達(dá)式中表示一個(gè)函數(shù)值。函數(shù)字面量的語(yǔ)法和函數(shù)聲明相似，區(qū)別在于func關(guān)鍵字后沒(méi)有函數(shù)名。函數(shù)值字面量是一種表達(dá)式，它的值被稱為匿名函數(shù)（anonymous function）。

函數(shù)字面量允許我們?cè)谑褂煤瘮?shù)時(shí)，再定義它。通過(guò)這種技巧，我們可以改寫之前對(duì)strings.Map的調(diào)用：

strings.Map(func(r rune) rune { return r + 1 }, "HAL-9000")

更為重要的是，通過(guò)這種方式定義的函數(shù)可以訪問(wèn)完整的詞法環(huán)境（lexical environment），這意味著在函數(shù)中定義的內(nèi)部函數(shù)可以引用該函數(shù)的變量，如下例所示：

gopl.io/ch5/squares

// squares返回一個(gè)匿名函數(shù)。
// 該匿名函數(shù)每次被調(diào)用時(shí)都會(huì)返回下一個(gè)數(shù)的平方。
func squares() func() int {
    var x int
    return func() int {
        x++
        return x * x
    }
}
func main() {
    f := squares()
    fmt.Println(f()) // "1"
    fmt.Println(f()) // "4"
    fmt.Println(f()) // "9"
    fmt.Println(f()) // "16"
}

函數(shù)squares返回另一個(gè)類型為 func() int 的函數(shù)。對(duì)squares的一次調(diào)用會(huì)生成一個(gè)局部變量x并返回一個(gè)匿名函數(shù)。每次調(diào)用匿名函數(shù)時(shí)，該函數(shù)都會(huì)先使x的值加1，再返回x的平方。第二次調(diào)用squares時(shí)，會(huì)生成第二個(gè)x變量，并返回一個(gè)新的匿名函數(shù)。新匿名函數(shù)操作的是第二個(gè)x變量。

squares的例子證明，函數(shù)值不僅僅是一串代碼，還記錄了狀態(tài)。在squares中定義的匿名內(nèi)部函數(shù)可以訪問(wèn)和更新squares中的局部變量，這意味著匿名函數(shù)和squares中，存在變量引用。這就是函數(shù)值屬于引用類型和函數(shù)值不可比較的原因。Go使用閉包（closures）技術(shù)實(shí)現(xiàn)函數(shù)值，Go程序員也把函數(shù)值叫做閉包。

通過(guò)這個(gè)例子，我們看到變量的生命周期不由它的作用域決定：squares返回后，變量x仍然隱式的存在于f中。

接下來(lái)，我們討論一個(gè)有點(diǎn)學(xué)術(shù)性的例子，考慮這樣一個(gè)問(wèn)題：給定一些計(jì)算機(jī)課程，每個(gè)課程都有前置課程，只有完成了前置課程才可以開始當(dāng)前課程的學(xué)習(xí)；我們的目標(biāo)是選擇出一組課程，這組課程必須確保按順序?qū)W習(xí)時(shí)，能全部被完成。每個(gè)課程的前置課程如下：

gopl.io/ch5/toposort

// prereqs記錄了每個(gè)課程的前置課程
var prereqs = map[string][]string{
    "algorithms": {"data structures"},
    "calculus": {"linear algebra"},
    "compilers": {
        "data structures",
        "formal languages",
        "computer organization",
    },
    "data structures":       {"discrete math"},
    "databases":             {"data structures"},
    "discrete math":         {"intro to programming"},
    "formal languages":      {"discrete math"},
    "networks":              {"operating systems"},
    "operating systems":     {"data structures", "computer organization"},
    "programming languages": {"data structures", "computer organization"},
}

這類問(wèn)題被稱作拓?fù)渑判?。從概念上說(shuō)，前置條件可以構(gòu)成有向圖。圖中的頂點(diǎn)表示課程，邊表示課程間的依賴關(guān)系。顯然，圖中應(yīng)該無(wú)環(huán)，這也就是說(shuō)從某點(diǎn)出發(fā)的邊，最終不會(huì)回到該點(diǎn)。下面的代碼用深度優(yōu)先搜索了整張圖，獲得了符合要求的課程序列。

func main() {
    for i, course := range topoSort(prereqs) {
        fmt.Printf("%d:\t%s\n", i+1, course)
    }
}

func topoSort(m map[string][]string) []string {
    var order []string
    seen := make(map[string]bool)
    var visitAll func(items []string)
    visitAll = func(items []string) {
        for _, item := range items {
            if !seen[item] {
                seen[item] = true
                visitAll(m[item])
                order = append(order, item)
            }
        }
    }
    var keys []string
    for key := range m {
        keys = append(keys, key)
    }
    sort.Strings(keys)
    visitAll(keys)
    return order
}

當(dāng)匿名函數(shù)需要被遞歸調(diào)用時(shí)，我們必須首先聲明一個(gè)變量（在上面的例子中，我們首先聲明了 visitAll），再將匿名函數(shù)賦值給這個(gè)變量。如果不分成兩步，函數(shù)字面量無(wú)法與visitAll綁定，我們也無(wú)法遞歸調(diào)用該匿名函數(shù)。

visitAll := func(items []string) {
    // ...
    visitAll(m[item]) // compile error: undefined: visitAll
    // ...
}

在toposort程序的輸出如下所示，它的輸出順序是大多人想看到的固定順序輸出，但是這需要我們多花點(diǎn)心思才能做到。哈希表prepreqs的value是遍歷順序固定的切片，而不再試遍歷順序隨機(jī)的map，所以我們對(duì)prereqs的key值進(jìn)行排序，保證每次運(yùn)行toposort程序，都以相同的遍歷順序遍歷prereqs。

1: intro to programming
2: discrete math
3: data structures
4: algorithms
5: linear algebra
6: calculus
7: formal languages
8: computer organization
9: compilers
10: databases
11: operating systems
12: networks
13: programming languages

讓我們回到findLinks這個(gè)例子。我們將代碼移動(dòng)到了links包下，將函數(shù)重命名為Extract，在第八章我們會(huì)再次用到這個(gè)函數(shù)。新的匿名函數(shù)被引入，用于替換原來(lái)的visit函數(shù)。該匿名函數(shù)負(fù)責(zé)將新連接添加到切片中。在Extract中，使用forEachNode遍歷HTML頁(yè)面，由于Extract只需要在遍歷結(jié)點(diǎn)前操作結(jié)點(diǎn)，所以forEachNode的post參數(shù)被傳入nil。

gopl.io/ch5/links

// Package links provides a link-extraction function.
package links
import (
    "fmt"
    "net/http"
    "golang.org/x/net/html"
)
// Extract makes an HTTP GET request to the specified URL, parses
// the response as HTML, and returns the links in the HTML document.
func Extract(url string) ([]string, error) {
    resp, err := http.Get(url)
    if err != nil {
        return nil, err
    }
    if resp.StatusCode != http.StatusOK {
    resp.Body.Close()
        return nil, fmt.Errorf("getting %s: %s", url, resp.Status)
    }
    doc, err := html.Parse(resp.Body)
    resp.Body.Close()
    if err != nil {
        return nil, fmt.Errorf("parsing %s as HTML: %v", url, err)
    }
    var links []string
    visitNode := func(n *html.Node) {
        if n.Type == html.ElementNode && n.Data == "a" {
            for _, a := range n.Attr {
                if a.Key != "href" {
                    continue
                }
                link, err := resp.Request.URL.Parse(a.Val)
                if err != nil {
                    continue // ignore bad URLs
                }
                links = append(links, link.String())
            }
        }
    }
    forEachNode(doc, visitNode, nil)
    return links, nil
}

上面的代碼對(duì)之前的版本做了改進(jìn)，現(xiàn)在links中存儲(chǔ)的不是href屬性的原始值，而是通過(guò)resp.Request.URL解析后的值。解析后，這些連接以絕對(duì)路徑的形式存在，可以直接被http.Get訪問(wèn)。

網(wǎng)頁(yè)抓取的核心問(wèn)題就是如何遍歷圖。在topoSort的例子中，已經(jīng)展示了深度優(yōu)先遍歷，在網(wǎng)頁(yè)抓取中，我們會(huì)展示如何用廣度優(yōu)先遍歷圖。在第8章，我們會(huì)介紹如何將深度優(yōu)先和廣度優(yōu)先結(jié)合使用。

下面的函數(shù)實(shí)現(xiàn)了廣度優(yōu)先算法。調(diào)用者需要輸入一個(gè)初始的待訪問(wèn)列表和一個(gè)函數(shù)f。待訪問(wèn)列表中的每個(gè)元素被定義為string類型。廣度優(yōu)先算法會(huì)為每個(gè)元素調(diào)用一次f。每次f執(zhí)行完畢后，會(huì)返回一組待訪問(wèn)元素。這些元素會(huì)被加入到待訪問(wèn)列表中。當(dāng)待訪問(wèn)列表中的所有元素都被訪問(wèn)后，breadthFirst函數(shù)運(yùn)行結(jié)束。為了避免同一個(gè)元素被訪問(wèn)兩次，代碼中維護(hù)了一個(gè)map。

gopl.io/ch5/findlinks3

// breadthFirst calls f for each item in the worklist.
// Any items returned by f are added to the worklist.
// f is called at most once for each item.
func breadthFirst(f func(item string) []string, worklist []string) {
    seen := make(map[string]bool)
    for len(worklist) > 0 {
        items := worklist
        worklist = nil
        for _, item := range items {
            if !seen[item] {
                seen[item] = true
                worklist = append(worklist, f(item)...)
            }
        }
    }
}

就像我們?cè)谡鹿?jié)3解釋的那樣，append的參數(shù)“f(item)...”，會(huì)將f返回的一組元素一個(gè)個(gè)添加到worklist中。

在我們網(wǎng)頁(yè)抓取器中，元素的類型是url。crawl函數(shù)會(huì)將URL輸出，提取其中的新鏈接，并將這些新鏈接返回。我們會(huì)將crawl作為參數(shù)傳遞給breadthFirst。

func crawl(url string) []string {
    fmt.Println(url)
    list, err := links.Extract(url)
    if err != nil {
        log.Print(err)
    }
    return list
}

為了使抓取器開始運(yùn)行，我們用命令行輸入的參數(shù)作為初始的待訪問(wèn)url。

func main() {
    // Crawl the web breadth-first,
    // starting from the command-line arguments.
    breadthFirst(crawl, os.Args[1:])
}

讓我們從 https://golang.org 開始，下面是程序的輸出結(jié)果：

$ go build gopl.io/ch5/findlinks3
$ ./findlinks3 https://golang.org
https://golang.org/
https://golang.org/doc/
https://golang.org/pkg/
https://golang.org/project/
https://code.google.com/p/go-tour/
https://golang.org/doc/code.html
https://www.youtube.com/watch?v=XCsL89YtqCs
http://research.swtch.com/gotour

當(dāng)所有發(fā)現(xiàn)的鏈接都已經(jīng)被訪問(wèn)或電腦的內(nèi)存耗盡時(shí)，程序運(yùn)行結(jié)束。

練習(xí)5.10： 重寫topoSort函數(shù)，用map代替切片并移除對(duì)key的排序代碼。驗(yàn)證結(jié)果的正確性（結(jié)果不唯一）。

練習(xí)5.11： 現(xiàn)在線性代數(shù)的老師把微積分設(shè)為了前置課程。完善topSort，使其能檢測(cè)有向圖中的環(huán)。

練習(xí)5.12： gopl.io/ch5/outline2（5.5節(jié)）的startElement和endElement共用了全局變量depth，將它們修改為匿名函數(shù)，使其共享outline中的局部變量。

練習(xí)5.13： 修改crawl，使其能保存發(fā)現(xiàn)的頁(yè)面，必要時(shí)，可以創(chuàng)建目錄來(lái)保存這些頁(yè)面。只保存來(lái)自原始域名下的頁(yè)面。假設(shè)初始頁(yè)面在golang.org下，就不要保存vimeo.com下的頁(yè)面。

練習(xí)5.14： 使用breadthFirst遍歷其他數(shù)據(jù)結(jié)構(gòu)。比如，topoSort例子中的課程依賴關(guān)系（有向圖）、個(gè)人計(jì)算機(jī)的文件層次結(jié)構(gòu)（樹）；你所在城市的公交或地鐵線路（無(wú)向圖）。

5.6.1. 警告：捕獲迭代變量

本節(jié)，將介紹Go詞法作用域的一個(gè)陷阱。請(qǐng)務(wù)必仔細(xì)的閱讀，弄清楚發(fā)生問(wèn)題的原因。即使是經(jīng)驗(yàn)豐富的程序員也會(huì)在這個(gè)問(wèn)題上犯錯(cuò)誤。

考慮這樣一個(gè)問(wèn)題：你被要求首先創(chuàng)建一些目錄，再將目錄刪除。在下面的例子中我們用函數(shù)值來(lái)完成刪除操作。下面的示例代碼需要引入os包。為了使代碼簡(jiǎn)單，我們忽略了所有的異常處理。

var rmdirs []func()
for _, d := range tempDirs() {
    dir := d // NOTE: necessary!
    os.MkdirAll(dir, 0755) // creates parent directories too
    rmdirs = append(rmdirs, func() {
        os.RemoveAll(dir)
    })
}
// ...do some work…
for _, rmdir := range rmdirs {
    rmdir() // clean up
}

你可能會(huì)感到困惑，為什么要在循環(huán)體中用循環(huán)變量d賦值一個(gè)新的局部變量，而不是像下面的代碼一樣直接使用循環(huán)變量dir。需要注意，下面的代碼是錯(cuò)誤的。

var rmdirs []func()
for _, dir := range tempDirs() {
    os.MkdirAll(dir, 0755)
    rmdirs = append(rmdirs, func() {
        os.RemoveAll(dir) // NOTE: incorrect!
    })
}

問(wèn)題的原因在于循環(huán)變量的作用域。在上面的程序中，for循環(huán)語(yǔ)句引入了新的詞法塊，循環(huán)變量dir在這個(gè)詞法塊中被聲明。在該循環(huán)中生成的所有函數(shù)值都共享相同的循環(huán)變量。需要注意，函數(shù)值中記錄的是循環(huán)變量的內(nèi)存地址，而不是循環(huán)變量某一時(shí)刻的值。以dir為例，后續(xù)的迭代會(huì)不斷更新dir的值，當(dāng)刪除操作執(zhí)行時(shí)，for循環(huán)已完成，dir中存儲(chǔ)的值等于最后一次迭代的值。這意味著，每次對(duì)os.RemoveAll的調(diào)用刪除的都是相同的目錄。

通常，為了解決這個(gè)問(wèn)題，我們會(huì)引入一個(gè)與循環(huán)變量同名的局部變量，作為循環(huán)變量的副本。比如下面的變量dir，雖然這看起來(lái)很奇怪，但卻很有用。

for _, dir := range tempDirs() {
    dir := dir // declares inner dir, initialized to outer dir
    // ...
}

這個(gè)問(wèn)題不僅存在基于range的循環(huán)，在下面的例子中，對(duì)循環(huán)變量i的使用也存在同樣的問(wèn)題：

var rmdirs []func()
dirs := tempDirs()
for i := 0; i < len(dirs); i++ {
    os.MkdirAll(dirs[i], 0755) // OK
    rmdirs = append(rmdirs, func() {
        os.RemoveAll(dirs[i]) // NOTE: incorrect!
    })
}

如果你使用go語(yǔ)句（第八章）或者defer語(yǔ)句（5.8節(jié)）會(huì)經(jīng)常遇到此類問(wèn)題。這不是go或defer本身導(dǎo)致的，而是因?yàn)樗鼈兌紩?huì)等待循環(huán)結(jié)束后，再執(zhí)行函數(shù)值。