作者:uraimo,原文鏈接羞延,原文日期:2015-11-12
譯者:CoderAFI渣淳;校對:Cee;定稿:numbbbbb
在這篇文章中我們將介紹 Swift 2 自定義序列肴楷,并舉例說明有限序列和無限序列的區(qū)別水由,本文是 Swift and the functional approach 系列其中一篇。
SequenceType
標準協(xié)議在官方文檔中被定義為一種簡單的數據類型砂客,該類型可以用 for...in
來循環(huán)遍歷。協(xié)議中最重要的定義是在上半部分:
public protocol SequenceType {
typealias Generator : GeneratorType
/// Return a *generator* over the elements of this *sequence*.
///
/// - Complexity: O(1).
public func generate() -> Self.Generator
...
...
}
上面的協(xié)議中關聯了另一個 GeneratorType
協(xié)議類型(Swift 讓協(xié)議泛型化的獨特方式)呵恢。當我們要自定義序列的時候鞠值,我們同時也要自定義一個實現這個協(xié)議的生成器,保證我們自定義的 SequenceType
在調用 generate()
方法時能夠返回指定元素類型的生成器渗钉。
序列協(xié)議中提供了許多有意思的方法彤恶,這些方法很多都已經在擴展中實現了钞钙,例如 map、flatmap(深入了解可以參看 map and flatMap)声离、filter芒炼、reduce、subsequence functions 等术徊。
這些方法讓 SequenceType
協(xié)議的作用遠遠大于只進行 for each 遍歷本刽。
讓我們來看下 GeneratorType
的定義:
public protocol GeneratorType {
typealias Element
/// Advance to the next element and return it, or `nil` if no next
/// element exists.
public mutating func next() -> Self.Element?
}
這個簡單的協(xié)議只包含了一個 next()
方法,該方法用來返回生成器管理的下一個元素赠涮。至關重要的一點是子寓,當序列遍歷到最后時,生成器應該返回 nil笋除。接下來當我們構造一個無限序列的時候斜友,來看看為什么這里要返回 nil
。
首先垃它,我們來寫一個簡單的斐波那契數序列生成器:
class FibonacciGenerator : GeneratorType {
var last = (0,1)
var endAt:Int
var lastIteration = 0
init(end:Int){
endAt = end
}
func next() -> Int?{
guard lastIteration<endAt else {
return nil
}
lastIteration++
let next = last.0
last = (last.1,last.0+last.1)
return next
}
}
為了定義一個有限序列鲜屏,我們需要一個自定義構造函數來指定一個序列長度。當到達這個長度時 next()
方法就返回 nil国拇。這里我們用元組(Tuple)實現起來會節(jié)省很多代碼量墙歪,讓我們看下如何使用這個生成器:
var fg = FibonacciGenerator(end:10)
while let fib = fg.next() {
print(fib)
}
用這種方式我們就可以遍歷生成器中的元素,直到生成器返回 nil贝奇。
根據這個生成器實現一個 SequenceType
輕而易舉。
class FibonacciSequence : SequenceType {
var endAt:Int
init(end:Int){
endAt = end
}
func generate() -> FibonacciGenerator{
return FibonacciGenerator(end: endAt)
}
}
let arr = Array(FibonacciSequence(end:10))
for f in FibonacciSequence(end: 10) {
print(f)
}
上面的序列正如預期那樣靠胜,可以在 foreach 遍歷中使用掉瞳,同樣也可以用來生成其他類型的序列,比如數組浪漠。
其實我們沒有必要單獨定義一種生成器類型陕习,我們可以用 anyGenerator
工具方法和 AnyGenerator<T>
類來降低序列定義的耦合性:
class CompactFibonacciSequence : SequenceType {
var endAt:Int
init(end:Int){
endAt = end
}
func generate() -> AnyGenerator<Int> {
var last = (0,1)
var lastIteration = 0
return anyGenerator({
guard lastIteration<self.endAt else {
return nil
}
lastIteration++
let next = last.0
last = (last.1,last.0+last.1)
return next
})
}
}
這種定義方式跟上面序列的最終效果是一樣的。唯一的區(qū)別就是 generate
方法返回了 AnyGenerator<Int>
類型址愿。它已經不是我們開始的時候定義的簡單生成器類型该镣。
這種做法在這里看起來可能沒太大用處,但是在很多情況下响谓,相較于讓一個生成器嵌入一個序列集合中损合,用一個簡單 anyGenerator()
方法來生成的序列更具擴展性。
例如娘纷,我們用 Lucas 序列的前 10 個數來創(chuàng)建一個序列嫁审。Lucas 序列與斐波那契序列非常相似,不同之處是斐波那契序列以 0赖晶,1 開頭而 Lucas 序列以 2律适,1 開頭,所以當然最終會生成截然不同的序列,例如:2捂贿,1纠修,3,4厂僧,7扣草,11,18吁系,29...下面我們只定義一個生成器德召,并用它來初始化一個數組。
var last = (2,1)
var c = 0
let lucas = anyGenerator{
()->Int? in
guard c<10 else {
return nil
}
c++
let next = last.0
last = (last.1,last.0+last.1)
return next
}
let a = Array(lucas) //[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
看起來不錯汽纤,我們刪除了一些無用的代碼上岗,我們也可以擴展我們的算法,讓它返回一個黃金分割比蕴坪,讓我們試試:
import Darwin
let Phi = (sqrt(5)+1.0)/2
let phi = 1/Phi
func luc(n:Int)->Int {
return Int(pow(Phi, Double(n))+pow(-phi,Double(n)))
}
c = 0
var compactLucas = anyGenerator{ c<10 ? luc(c++): nil }
let a2 = Array(compactLucas) //[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
這樣確實行得通嗎肴掷?當然,你可以下載 playground 或打包的 zip 文件來驗證背传。
為了嘗試 SequenceType
提供的一些特性方法呆瞻。我們構建一個只返回偶數的 Lucas 數字序列:
c = 0
var evenCompactLucas = anyGenerator{ c<10 ? luc(c++): nil }.filter({$0 % 2 == 0})
let a3 = Array(evenCompactLucas) //[2, 4, 18, 76]
注意,這里我們其實是重新定義了 AnyGenerator
径玖,由于前面的序列是有限的痴脾,當遍歷到最后時,就會產生另一個有限的序列梳星。這從另一方面也可以說明赞赖,我們很容易就能改變原有序列,返回一組新的數據集冤灾。我們也可以用 map 方法來做一些更直接的轉換前域。
無限序列
現在,我們移除 nil 的返回值限制韵吨,這樣就能根據 Lucas 算法生成一個無限序列匿垄。
c = 0
var infiniteLucas = anyGenerator{luc(c++)}
可見,將一個有限序列轉換成無限序列是非常容易的」榉郏現在我們生成了一個沒有數量限制的新序列椿疗。但是我們需要另外一種方式來限制序列元素數,從而讓無限序列元素數更可控盏浇。
幸運的是 SequenceType
協(xié)議提供了一個方法來解決這個問題:
let a4 = Array(infiniteLucas.prefix(10)) //[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
for var f in infiniteLucas.prefix(10){
print(f)
}
這種方式將會從當前序列篩選出 10 個元素并添加到一個新的序列中变丧,而且新序列使用起來跟前面的無限序列是一樣的。
讓我們進一步來看一下 filter 方法的用法绢掰,看看怎么樣用它來獲取 Lucas 偶數痒蓬。
var onlyEvenLucas = infiniteLucas.filter({$0 % 2 == 0})
for var f in onlyEvenLucas.prefix(10){
print(f)
}
然而童擎,上面的代碼并不會像預期那樣工作。
如果是在 playground 運行攻晒,在聲明 onlyEventLucas
時你會看到高亮報錯顾复。如果是在應用程序中寫了這段代碼,你的應用程序會崩潰鲁捏。
要了解問題的原因芯砸,必須要了解 filter 函數的工作原理。 當對一個序列進行 filter 操作時给梅,我們
必須要把序列的所有元素都獲取到假丧,但是如果沒有 nil 限制,序列元素是無限的动羽,就無法確認元素的遍歷操作什么時候結束包帚。
讓我們在每次從生成器獲取元素時都打印一段文本,來更形象的看下原因:
class InfiniteSequence :SequenceType {
func generate() -> AnyGenerator<Int> {
var i = 0
return anyGenerator({
print("# Returning "+String(i))
return i++
})
}
}
var fs = InfiniteSequence().filter({$0 % 2 == 0}).generate()
for i in 1...5 {
print(fs.next())
}
如果你運行這段代碼运吓,會發(fā)現在 InfiniteSequence
上的過濾處理一直在運行渴邦,直到一段時間后處理器無法再繼續(xù)運行,程序就崩潰了拘哨。
幸運的是谋梭,解決上面的問題也很容易。我們只需要延遲計算(Lazily evaluate)這個無限的 Lucas 序列:
var onlyEvenLucas = infiniteLucas.lazy.filter({$0 % 2 == 0})
for var f in onlyEvenLucas.prefix(10){
print(f)
}
使用無限序列的 .lazy
屬性就能獲取一個新的 LazySequenceType
類型倦青,該類型會讓 map瓮床、flatmap、reduce 或者 filter 這些方法延遲執(zhí)行产镐,也就是說真正的計算會等到例如 next
這樣的終端操作(Terminal Operation)(其他語言是這么叫的)執(zhí)行時才會被執(zhí)行纤垂。
讓無限序列支持延遲計算是一個必要步驟,默認情況下 Swift 的序列不能延遲計算(該特性是在 Swift 1.0 發(fā)布的)磷账。具體你可以通過官方文檔來詳細了解如何自定義一個 LazySequence(大多數情況可能是解決問題的最好辦法),我也會就該內容進行講解贾虽,敬請期待逃糟。
本文由 SwiftGG 翻譯組翻譯,已經獲得作者翻譯授權蓬豁,最新文章請訪問 http://swift.gg绰咽。