Sequence in Swift - A 🍻 Story

Generator跟Sequence是在許多語言之中常見的design pattern，有了這兩種patterns，你可以很清楚地把按需求取資料跟操作有順序的資料這兩件事情透過程式寫出來。

Swift在2.0時就已經提供了generatorType跟sequenceType兩種protocol來讓你實作，但在3.0之後，統一都改成了IteratorProtocol跟Sequence，所有跟generator有關的命名也都改成了Iterator。這讓這兩者的關係更為明確，而不再是長得像的兩個協定。

下面將從Iterator開始，利用範例來實做一個Swift的Sequence。

背景

現在要實做一台智慧型啤酒販賣機，販賣機依序裝著一罐一罐的啤酒。我們希望販賣機的UI能夠：

按照容量列出機器裡的啤酒
只列出大於400ml的啤酒
整台機器的總藏酒毫升數

基本類別是當然是Beer 🍻。

struct Beer {
	var brandName: String    //品牌
	var volume: Int               //容量
}

接下來我們要一步一步透過Sequence完成這台販賣機的開發。首先，我們需要一個核心結構BeerContainer來裝所有的啤酒：

struct BeerContainer {
	let elements: [Beer]
	var i = 0

	init(elements: [Beer]) {
		self.elements = elements
	}
}

變數elements是一個Array，放著我們的🍻。我們希望這個container不只能存東西，還能在我們需要的時候，一筆一筆地把啤酒列出來。這樣的行為模式在Swift就叫做Iterator，指的就是在遍歷某個容器時，，不是先把容器裡的物件全部攤開讓你去traverse，而是在下next()之後，才去計算它的下一筆資料並回傳。想要讓我們的BeerContainer能夠成為一個Iterator，就需要實作IteratorProtocol。

IteratorProtocol

IteratorProtocol長這樣：

protocol IteratorProtocol {
	associatedtype Element
	mutating func next() -> Element?
}

我們需要實作的method就只有一個，就是next()。這個next()需要在每次被呼叫的時候，都回傳下一筆資料，並且把這次的資料記下來，讓下次呼叫next()時能夠成功抓到再下一筆資料。在這邊的例子，我們利用BeerContainer的變數i來代表我們目前所在資料的位置，每call一次next()，我們都讓i加一，這樣就可以一次輸出一筆，並且一筆一筆往下移。

extension BeerContainer: IteratorProtocol {
	typealias Element = Beer

	mutating func next() -> Element? {
		defer {
			i+=1
		}
		return i<elements.count ? elements[i] : nil
	}
}

上面的程式中有幾個點要注意：

Element是這個protocol的associated type，在實作時我們需要明確指定我們的這個iterator是要針對那一種物件操作。
next()這個method是mutating的，也就是說在執行這個method後，會改變這個物件裡的某個變數，這點帶出了iterator的一個非常重要的特性，就是它本身不是immutable的，每次call next()都會有不一樣的結果。
defer是一個Swift的神奇語法，代表的是一個closure會在這個scope跑完之後，才執行closure裡面的內容。

在next()之中，每次執行都會回傳elements[i]，並且把i加一。

以下是實際上線的狀況：

let aOrionBeer = Beer(brandName: "Orion", volume: 300)
let aSaporoBeer = Beer(brandName: "Saporo", volume: 380)
let aTaiwanBeer = Beer(brandName: "TaiwanBeer", volume: 330)
let aAsahiBeer = Beer(brandName: "Asahi", volume: 420)


var aBeerContainer = BeerContainer(elements: [ aOrionBeer, aSaporoBeer, aTaiwanBeer, aAsahiBeer ])

// i=0
print(aBeerContainer.next())
// Orion: 300 ml, i=1

print(aBeerContainer.next())
// Saporo: 380 ml, i=2

print(aBeerContainer.next())
// TaiwanBeer: 330 ml, i=3

print(aBeerContainer.next())
// Asahi: 400 ml, i=4

print(aBeerContainer.next())
// nil, i=5

每次呼叫next()，這個iterator才會回傳目前i指向的值，並且把i加一為下一次呼叫next()做準備。在呼叫的過程中，i一直都在改變，也就是這個BeerContainer物件本身一直都在變化，等全部都取完之後，就再也拿不到值了。

上面的code可以寫成更常見的型式：

while let aBeer = aBeerMContainer.next() {
	print(aBeer)
}

到這邊我們就了解了IteratorProtocol要怎樣實作，可以按一個鈕next()就噴出一罐啤酒了😎

但Iterator只是一個基本的資料結構，如果我們想要做一些如排序、過濾等等變化，就必須要再把Iterator打包成更高層的資料結構：Sequence。

Sequence protocol

在Swift之中，Sequence代表的是一個有序的資料結構。像我們常見的Array就有符合Sequence，可以用for..in的方法來取用內容：

let bugs = ["Aphid", "Bumblebee", "Cicada", "Damselfly", "Earwig"]
for bug in bugs {
	print(bug)
}

你可以把Sequence理解成像Array一樣的有序結構，而Iterator比較像是一個需要呼叫才會有動靜的指標。

接下來，我們要來動手製作我們的VendorMachine了！

struct VendorMachine {
	let elements: [Beer]
}

好的，現在這台販賣機毫無疑問，就是一台可以裝東西的機器。再來我們需要讓它成為Sequence，才能夠做出對裡面的啤酒排序、選擇等等動作。要成為一個Sequence非常簡單，只需要conform一個methodmakeIterator()：

protocol Sequence {
	associatedtype Iterator : IteratorProtocol    
	func makeIterator() -> Iterator
}

這個makeIterator()是做甚麼用的？Sequence的核心，就是這個Iterator，Sequence靠著Iterator來做到依序讀取資料，並且在這樣的基礎之上，再加入許多方便使用的方法如map()、reduce()、跟filter()。

讓我們來把VendorMachine實作成 Sequence吧！下面是一個非常基本的實作：

extension VendorMachine: Sequence {
	typealias Iterator = IndexingIterator<[Beer]>

	func makeIterator() -> Iterator {
		return elements.makeIterator()
	}
}

typealias的作用，跟我們在IteratorProtocol章節提到的一樣，是為了指定實作型別用的。在這個實作中，我們取了個捷徑，直接使用Array中已經定義好的IndexingIterator來當做我們的Iterator。IndexingIterator就是一個會按照index=1, 2, 3, 4...來讀取資料的Iterator，其實功能等同於我們上面的BeerContainer。利用這個既有的Iterator，我們設定我們的Sequence，要利用這個Iterator來執行Sequence的其它method。終於可以來實作我們的啤酒販賣機了！

首先先建立好我們的VendorMachine，並且塞一些啤酒進去：

let aMachine = VendorMachine(elements: [ aOrionBeer, aSaporoBeer, aTaiwanBeer, aAsahiBeer ])

還記得我們的需求嗎？

按照容量列出機器裡的啤酒

這邊我們要做的就是把VendorMachine裡的東西排序，身為一個Sequence，Swift有提供sorted()讓Sequence能夠回傳排序過的資料，使用方式如下：

let sortedBeers = aMachine.sorted { $0.volume>$1.volume }
// [Asahi: 420 ml, Saporo: 380 ml, TaiwanBeer: 330 ml, Orion: 300 ml]

sorted這個method用了不少Swift syntactic sugar，如果不熟的可以參考小弟拙作Swift Syntactic Sugar 偏方可恥但有用，懶得說明就用工商服務取代，是一個blogger應有的態度。

回到正題，sorted這個method會回傳排序過的Sequence內容，排序的方式是甚麼？就是利用sorted唯一的參數by，它是一個回傳Bool的closure，sorted method會依照這邊回傳的Bool來判斷兩個元素之間的大小關係。

只列出大於400ml的啤酒

這裡則是會使用Sequence定義好的filter()這個method，這個method只有一個closure參數，利用closure回傳的Bool，來決定那些元素要留下：

let largeBeers = aMachine.filter { $0.volume>400 }
// [Asahi: 420 ml]

整台機器的總藏酒毫升數

相信大家對reduce都已經很熟悉了，不熟的一樣可以參考上面提到的拙作(不放棄打歌)。下面這個程式就利用reduce，把所有的volume都總和起來並且輸出：

let totalVolume = aMachine.reduce(0) { return $0+$1.volume }
// 1430

以上就是一個Sequence所會有的基本功能，而我們也利用這些基本功能完成了我們的任務！🍻 🍻 🍻

等等，這個東西跟存成[ Beer ]有甚麼不一樣？沒錯，正如冰雪聰明的你所猜到的，這完全就是一個Array的簡易實作，並且我們還取巧地用了Array的Iterator來達到我們的目的，來摸著你的良心，請問你想這樣就交差嗎？想！(完全沒考慮)

接下來要真正進入這篇冗長文章的主題(是有多少主題)，幫Sequence裝上自製的Iterator，成為真正的天然手作Sequence。我們把上面的implementation改成下面這樣，把剛剛寫好的BeerContainer裝到makeIterator()裡面：

extension VendorMachine: Sequence {
	typealias Iterator = BeerContainer

	func makeIterator() -> Iterator {
		return BeerContainer(elements: self.elements)
	}
}

這樣我們就完成了我們的販賣機，並且用自己寫好的Iterator來實現Sequence了！(主題不到十行)

AnyIterator

接下來進行同場加映，也就是真正實用上最常遇到的Sequence跟Iterator搭配用法。一般實用上我們不太會為了這個Sequence特別立一個Iterator，而是會利用一個AnyIterator，來簡單地把makeIterator()給實作出來。

AnyIterator是一種Iterator，它可以輸入一個closure，當成是這個Iterator的next()。下面的程式會在AnyIterator的closure之中，實作一個每跑一次next()就把index加一的function：

struct VendorMachine: Sequence {
	typealias Iterator = AnyIterator<Beer>

	let elements: [Beer]

	func makeIterator() -> Iterator {
		var i = self.elements.startIndex
		return AnyIterator {
			defer {
				i+=1
			}
			return i<self.elements.count ? self.elements[i] : nil
		}
	}
}

上面就是把整個iterator寫在makeIterator裡面的例子，在AnyIterator之中，每跑一次這個closure，就會回傳elements之中第i個變數，並且i會被加一。這樣我們就成功地把整個BeerContainer搬到這個makeIterator裡面了！其它的code都跟我們在BeerContainer上實作的一樣，只是要注意的是，AnyIterator的參數是一個@escaping closure，所以必須要明確地把self給標出來。

以上就是Iterator跟Sequence的介紹，故事的最後，要來做一下總結：

Iterator就是一個按需求依序噴出資料的容器。
Sequence則是利用Iterator實作出來的、更高階的有序資料結構。
實作了Sequence之後，就能夠使用map、reduce、filter等等method。
AnyIterator能夠把next()拉到外面成為一個參數，方便Iterator的建立。

如果有誤的話歡迎隨時提出來，也歡迎討論喔！所有的程式碼都可以在這邊抓得到，是一個Playground。

PS 1. Iterator pattern很常被用在像讀取大檔案這種無法一次全部取出來，只能一筆一筆列的情況，上面的實作有許多更方便的做法，我們只是希望透過簡化使用方式來解釋這個pattern。

PS 10. Sequence在定義上，並不能完全當成像Array一樣使用，甚麼意思？以下是官方範例：

for element in sequence {
	if ... some condition { break }
}

for element in sequence {
	// No defined behavior
}

第一個for..in就正常使用它，而在第二個for..in，如果對象是一個Array的話，那就是從頭到尾遍歷一次，但如果是個Sequence，裡面的行為模式就是未定義！也就是說，Swift不保證Sequence在重覆讀取時資料會維持一樣，如果你希望它可以像Array一樣能重覆存取，有個protocol需要被實作：Collection。

PS 11. Collection我們就等春暖花開時再來寫吧....

PS 100. Norah Jones這局得一百分！貢獻了這篇文章100%的背景音樂！聽首歌吧：https://www.youtube.com/watch?v=ROditq3L8w4

PS 101. 如果你的生存三元素是陽光、空氣、啤酒，那歡迎來分享在台北的求生之路。