5.6. 匿名函數

擁有函數名的函數隻能在包級語法塊中被聲明,通過函數字面量(function literal),我們可繞過這一限製,在任何表達式中表示一個函數值。函數字面量的語法和函數聲明相似,區别在於func關鍵字後沒有函數名。函數值字面量是一種表達式,它的值被成爲匿名函數(anonymous function)。

函數字面量允許我們在使用時函數時,再定義它。通過這種技巧,我們可以改寫之前對strings.Map的調用:

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

更爲重要的是,通過這種方式定義的函數可以訪問完整的詞法環境(lexical environment),這意味着在函數中定義的內部函數可以引用該函數的變量,如下例所示:

gopl.io/ch5/squares Go // squares返迴一個匿名函數。 // 該匿名函數每次被調用時都會返迴下一個數的平方。 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" }

函數squares返迴另一個類型爲 func() int 的函數。對squares的一次調用會生成一個局部變量x併返迴一個匿名函數。每次調用時匿名函數時,該函數都會先使x的值加1,再返迴x的平方。第二次調用squares時,會生成第二個x變量,併返迴一個新的匿名函數。新匿名函數操作的是第二個x變量。

squares的例子證明,函數值不僅僅是一串代碼,還記録了狀態。在squares中定義的匿名內部函數可以訪問和更新squares中的局部變量,這意味着匿名函數和squares中,存在變量引用。這就是函數值屬於引用類型和函數值不可比較的原因。Go使用閉包(closures)技術實現函數值,Go程序員也把函數值叫做閉包。

通過這個例子,我們看到變量的生命週期不由它的作用域決定:squares返迴後,變量x仍然隱式的存在於f中。

接下來,我們討論一個有點學術性的例子,考慮這樣一個問題:給定一些計算機課程,每個課程都有前置課程,隻有完成了前置課程才可以開始當前課程的學習;我們的目標是選擇出一組課程,這組課程必須確保按順序學習時,能全部被完成。每個課程的前置課程如下:

gopl.io/ch5/toposort Go // prereqs記録了每個課程的前置課程 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"}, }

這類問題被稱作拓撲排序。從概念上説,前置條件可以構成有向圖。圖中的頂點表示課程,邊表示課程間的依賴關繫。顯然,圖中應該無環,這也就是説從某點出發的邊,最終不會迴到該點。下面的代碼用深度優先蒐索了整張圖,獲得了符合要求的課程序列。

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
}

當匿名函數需要被遞歸調用時,我們必須首先聲明一個變量(在上面的例子中,我們首先聲明了 visitAll),再將匿名函數賦值給這個變量。如果不分成兩部,函數字面量無法與visitAll綁定,我們也無法遞歸調用該匿名函數。

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

在topsort中,首先對prereqs中的key排序,再調用visitAll。因爲prereqs映射的是切片而不是更複雜的map,所以數據的遍歷次序是固定的,這意味着你每次運行topsort得到的輸出都是一樣的。 topsort的輸出結果如下:

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這個例子。我們將代碼移動到了links包下,將函數重命名爲Extract,在第八章我們會再次用到這個函數。新的匿名函數被引入,用於替換原來的visit函數。該匿名函數負責將新連接添加到切片中。在Extract中,使用forEachNode遍歷HTML頁面,由於Extract隻需要在遍歷結點前操作結點,所以forEachNode的post參數被傳入nil。

gopl.io/ch5/links Go // 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 }

上面的代碼對之前的版本做了改進,現在links中存儲的不是href屬性的原始值,而是通過resp.Request.URL解析後的值。解析後,這些連接以絶對路徑的形式存在,可以直接被http.Get訪問。

網頁抓取的核心問題就是如何遍歷圖。在topoSort的例子中,已經展示了深度優先遍歷,在網頁抓取中,我們會展示如何用廣度優先遍歷圖。在第8章,我們會介紹如何將深度優先和廣度優先結合使用。

下面的函數實現了廣度優先算法。調用者需要輸入一個初始的待訪問列表和一個函數f。待訪問列表中的每個元素被定義爲string類型。廣度優先算法會爲每個元素調用一次f。每次f執行完畢後,會返迴一組待訪問元素。這些元素會被加入到待訪問列表中。當待訪問列表中的所有元素都被訪問後,breadthFirst函數運行結束。爲了避免同一個元素被訪問兩次,代碼中維護了一個map。

gopl.io/ch5/findlinks3 Go // 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)...) } } } }

就像我們在章節3解釋的那樣,append的參數“f(item)…”,會將f返迴的一組元素一個個添加到worklist中。

在我們網頁抓取器中,元素的類型是url。crawl函數會將URL輸出,提取其中的新鏈接,併將這些新鏈接返迴。我們會將crawl作爲參數傳遞給breadthFirst。

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

爲了使抓取器開始運行,我們用命令行輸入的參數作爲初始的待訪問url。

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

讓我們從 https://golang.org 開始,下面是程序的輸出結果:

$ 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

當所有發現的鏈接都已經被訪問或電腦的內存耗盡時,程序運行結束。

練習5.10: 重寫topoSort函數,用map代替切片併移除對key的排序代碼。驗證結果的正確性(結果不唯一)。

練習5.11: 現在線性代數的老師把微積分設爲了前置課程。完善topSort,使其能檢測有向圖中的環。

練習5.12: gopl.io/ch5/outline2(5.5節)的startElement和endElement共用了全局變量depth,將它們脩改爲匿名函數,使其共享outline中的局部變量。

練習5.13: 脩改crawl,使其能保存發現的頁面,必要時,可以創建目録來保存這些頁面。隻保存來自原始域名下的頁面。假設初始頁面在golang.org下,就不要保存vimeo.com下的頁面。

練習5.14: 使用breadthFirst遍歷其他數據結構。比如,topoSort例子中的課程依賴關繫(有向圖),個人計算機的文件層次結構(樹),你所在城市的公交或地鐵線路(無向圖)。

{% include “./ch5-06-1.md” %}