Swift函數(shù)式編程 惰性計算

Swift函數(shù)式編程－惰性計算

Swift支持函數(shù)式編程，這一篇介紹Swift的惰性計算。

惰性計算

惰性計算是函數(shù)式編程語言的一個特性。在使用惰性計算時，表達式不在它被綁定到變量之后就立即求值，而是在該值被取用的時候求值。惰性計算有如下優(yōu)點：

• 首先，你可以用它們來創(chuàng)建無限序列這樣一種數(shù)據(jù)類型。因為直到需要時才會計算值，這樣就可以使用惰性集合模擬無限序列。

• 第二，減少了存儲空間。因為在真正需要時才會發(fā)生計算。所以，節(jié)約了不必要的存儲空間。

• 第三，減少計算量，產(chǎn)生更高效的代碼。因為在真正需要時才會發(fā)生計算。例如，尋找數(shù)組中第一個符合某個條件的值。

在純函數(shù)式編程語言，如Haskell中是默認進行惰性求值的。所以，Haskell被稱為惰性語言。而與之相對的大多數(shù)編程語言如Java，C++ 的求值都是嚴格的，或者說是及早求值。Swift默認是嚴格求值的，也就是每一個表達式都需要求值，而不論這個表達式在實際中是否確實需要求值。但是，Swift作為支持多種范型的編程語言，也同時提供語法來支持惰性求值。

內(nèi)建 lazy 函數(shù)

Swift中，如果需要惰性計算，就要顯式地將一個序列轉(zhuǎn)化為惰性序列。轉(zhuǎn)化方法是使用Swift內(nèi)建的lazy函數(shù)。它有四個重載實現(xiàn)。編譯器會為你選擇最正確的實現(xiàn)。

如果傳入lazy的是Sequence（實現(xiàn)了SequenceType協(xié)議的類或者結(jié)構(gòu)體），返回的會是LazySequence；如果傳入一個Collection（實現(xiàn)了CollectionType協(xié)議的的類或者結(jié)構(gòu)體），返回的會是LazyForwardCollection, LazyBidirectionalCollection, 或者LazyRandomAccessCollection。 下面是lazy函數(shù)的四個函數(shù)重載函數(shù)的函數(shù)原型：

func lazy<S: SequenceType>(s: S) -> LazySequence<S>
func lazy<S: CollectionType where S.Index: ForwardIndexType>(s: S) -> LazyForwardCollection<S>
func lazy<S: CollectionType where S.Index: BidirectionalIndexType>(s: S) -> LazyBidirectionalCollection<S>
func lazy<S: CollectionType where S.Index: RandomAccessIndexType>(s: S) -> LazyRandomAccessCollection<S>

如果，傳入一個Array，返回的將是LazyRandomAccessCollection類型。LazyRandomAccessCollection是惰性集合。下面展示了一個將Array變?yōu)槎栊孕蛄械睦樱?/p>

let r = 1...3
let seq = lazy(r).map {
    (i: Int) -> Int in
    println("mapping \(i)")
    return i * 2
}

for i in seq {
    println(i)
}

將獲得如下結(jié)果：

mapping 1
2
mapping 2
4
mapping 3
6

這顯示了seq是一個惰性序列。它的值只有在需要時才會真正發(fā)生計算。

Generator

Swift中，Generator是任何實現(xiàn)了GeneratorType協(xié)議的類或者結(jié)構(gòu)體。Generator可以理解為一個序列生成器。GeneratorType協(xié)議要求定義一個名為Element的別名，并實現(xiàn)一個next方法。

GeneratorType協(xié)議實現(xiàn)如下：

protocol GeneratorType {
    typealias Element
    mutating func next() -> Element?
}

語句typealias Element要求實現(xiàn)這個協(xié)議的類必須定義一個名為Element的別名，這樣一定程度上實現(xiàn)了泛型協(xié)議。協(xié)議同時要求實現(xiàn)next函數(shù)，其返回值是別名中定義的Element類型，next函數(shù)代表生成器要生成的下一個元素。

下面代碼實現(xiàn)了一個菲波那契數(shù)列生成器：

class FibonacciGenerator : GeneratorType {

    var current = 0, nextValue = 1  

    typealias Element = Int

    func next() -> Element? {
        let ret = current
        current = nextValue
        nextValue = nextValue + ret
        return ret
    }
}

下面代碼打印出10個菲波那契數(shù)列，以顯示如何使用生成器：

var n = 10
var generator = FibonacciGenerator()
while n-- > 0 {
    println(generator.next()!)
}

Generator是Sequence和Collection的基礎(chǔ)。

Sequence

Sequence是任何實現(xiàn)了SequenceType協(xié)議的類或者結(jié)構(gòu)體。Sequence可以理解為一個序列。SequenceType協(xié)議要求定義一個名為Generator，類型為GeneratorType的別名，并要求實現(xiàn)一個返回生成器Generator的函數(shù)。

SequenceType協(xié)議如下：

protocol SequenceType : _Sequence_Type {
    typealias Generator : GeneratorType
    func generate() -> Generator
}

類似于GeneratorType協(xié)議，typealias Generator : GeneratorType要求實現(xiàn)這個協(xié)議的類必須定義一個名為Generator類型為GeneratorType的別名。協(xié)議同時要求實現(xiàn)一個名為generate的函數(shù)，其返回值為別名Generator定義的類型，這個類型應(yīng)該實現(xiàn)了上文提到的GeneratorType協(xié)議。也就是說Sequence其實是包含一個生成Generator的函數(shù)的類。

下面代碼使用上文中提到的菲波那契數(shù)列生成器，實現(xiàn)了一個菲波那契數(shù)列：

class FibonacciSequence: SequenceType
{
    typealias GeneratorType = FibonacciGenerator

    func generate() -> FibonacciGenerator {
        return FibonacciGenerator()
    }
}

下面代碼打印了10個菲波那契數(shù)列，以顯示如何使用該序列：

let fib = FibonacciSequence().generate()
for _ in 1..<10 {
    println(fib.next()!)
}

符合SequenceType的序列有可能成為惰性序列。成為惰性序列的方法是對其顯示的調(diào)用lazy函數(shù)：

let r = lazy(stride(from: 1, to: 8, by: 2))

函數(shù)stride返回一個結(jié)構(gòu)體StrideTo，這個結(jié)構(gòu)體是Sequence。所以，lazy函數(shù)返回一個lazySequence對象。

Collection

Collection是實現(xiàn)了CollectionType協(xié)議的協(xié)議的類或者結(jié)構(gòu)體。CollectionType協(xié)議繼承了SequenceType協(xié)議。所以，Collection也都實現(xiàn)了SequenceType，它同時也是Sequence。

CollectionType協(xié)議如下：

protocol _CollectionType : _SequenceType {
    typealias Index : ForwardIndexType
    var startIndex: Index { get }
    var endIndex: Index { get }
    typealias _Element
    subscript (_i: Index) -> _Element { get }
}

protocol CollectionType : _CollectionType, SequenceType {
    subscript (position: Self.Index) -> Self.Generator.Element { get }
}

所以，CollectionType協(xié)議首先實現(xiàn)了SequenceType協(xié)議，并要求實現(xiàn)一個subscript方法以獲取序列中每個位置的元素值。

Swift中，大量內(nèi)置類如Dictionary，Array，Range，String都實現(xiàn)了CollectionType協(xié)議。所以，Swift大部分容器類都可以變?yōu)槎栊孕蛄小?/p>

// a will be a LazyRandomAccessCollection
// since arrays are random access
let a = lazy([1,2,3,4])

// s will be a LazyBidirectionalCollection
let s = lazy("hello")

總結(jié)

Swift里的集合數(shù)據(jù)結(jié)構(gòu)默認是嚴格求值的。但是，Swift也提供了惰性語法，在需要惰性時，你需要顯式聲明。這為開發(fā)者在Swift中使用惰性提供了條件。

原文出處：http://lincode.github.io/Swift-Lazy
作者：LinGuo