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

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

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

惰性計(jì)算

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

• 首先，你可以用它們來(lái)創(chuàng)建無(wú)限序列這樣一種數(shù)據(jù)類型。因?yàn)橹钡叫枰獣r(shí)才會(huì)計(jì)算值，這樣就可以使用惰性集合模擬無(wú)限序列。

• 第二，減少了存儲(chǔ)空間。因?yàn)樵谡嬲枰獣r(shí)才會(huì)發(fā)生計(jì)算。所以，節(jié)約了不必要的存儲(chǔ)空間。

• 第三，減少計(jì)算量，產(chǎn)生更高效的代碼。因?yàn)樵谡嬲枰獣r(shí)才會(huì)發(fā)生計(jì)算。例如，尋找數(shù)組中第一個(gè)符合某個(gè)條件的值。

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

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

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

如果傳入lazy的是Sequence（實(shí)現(xiàn)了SequenceType協(xié)議的類或者結(jié)構(gòu)體），返回的會(huì)是LazySequence；如果傳入一個(gè)Collection（實(shí)現(xiàn)了CollectionType協(xié)議的的類或者結(jié)構(gòu)體），返回的會(huì)是LazyForwardCollection, LazyBidirectionalCollection, 或者LazyRandomAccessCollection。 下面是lazy函數(shù)的四個(gè)函數(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>

如果，傳入一個(gè)Array，返回的將是LazyRandomAccessCollection類型。LazyRandomAccessCollection是惰性集合。下面展示了一個(gè)將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是一個(gè)惰性序列。它的值只有在需要時(shí)才會(huì)真正發(fā)生計(jì)算。

Generator

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

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

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

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

下面代碼實(shí)現(xiàn)了一個(gè)菲波那契數(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個(gè)菲波那契數(shù)列，以顯示如何使用生成器：

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

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

Sequence

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

SequenceType協(xié)議如下：

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

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

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

class FibonacciSequence: SequenceType
{
    typealias GeneratorType = FibonacciGenerator

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

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

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

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

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

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

Collection

Collection是實(shí)現(xiàn)了CollectionType協(xié)議的協(xié)議的類或者結(jié)構(gòu)體。CollectionType協(xié)議繼承了SequenceType協(xié)議。所以，Collection也都實(shí)現(xiàn)了SequenceType，它同時(shí)也是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é)議首先實(shí)現(xiàn)了SequenceType協(xié)議，并要求實(shí)現(xiàn)一個(gè)subscript方法以獲取序列中每個(gè)位置的元素值。

Swift中，大量?jī)?nèi)置類如Dictionary，Array，Range，String都實(shí)現(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)默認(rèn)是嚴(yán)格求值的。但是，Swift也提供了惰性語(yǔ)法，在需要惰性時(shí)，你需要顯式聲明。這為開(kāi)發(fā)者在Swift中使用惰性提供了條件。

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