Swift中序列的实现方式

原文日期：2015/08/22

译者：Prayer 校对：shanksyang 定稿：numbbbbb

SequenceType

GeneratorType

let nums = [1, 2, 3]

var numGenerator = nums.generate()

numGenerator.next() 
numGenerator.next() 
numGenerator.next() 
numGenerator.next() 

for i in nums {
  
}

var g = nums.generate()
while let i = g.next() {

}

extension IndexingGenerator : SequenceType {
  func generate() -> IndexingGenerator {
    return self
  }
}

extension SomeGenerator : SequenceType {}

AnyGenerator

var i = 1
var upToThree = anyGenerator { i <= 3 ? i++ : nil }
upToThree.next() 
upToThree.next() 
upToThree.next() 
upToThree.next() 

生成一个序列

struct UpTo : SequenceType {
  private let from, to: Int
  func generate() -> AnyGenerator<Int> {
    var i = from
    return anyGenerator { i <= self.to ? nil : i++ }
  }
}

enum List<Element> : GeneratorType, SequenceType {
  case Nil
  indirect case Cons(Element, List<Element>)

  mutating func next() -> Element? {
    guard case let .Cons(x, xs) = self else { return nil }
    self = xs
    return x
  }
}

let list = List.Cons(1, .Cons(2, .Cons(3, .Nil)))
list.dropFirst()

extension List {
  func dropFirst(n: Int = 1) -> List {
    switch (n, self) {
    case (0, _), (_, .Nil): return self
    case let (_, .Cons(_, xs)): return xs.dropFirst(n - 1)
    }
  }
}

public protocol SequenceType {
    typealias Generator : GeneratorType
    typealias SubSequence
    public func generate() -> Self.Generator
    public func underestimateCount() -> Int
    public func map<T>(@noescape transform: (Self.Generator.Element) -> T) -> [T]
    public func filter(@noescape includeElement: (Self.Generator.Element) -> Bool) -> [Self.Generator.Element]
    public func forEach(@noescape body: (Self.Generator.Element) -> ())
    public func dropFirst(n: Int) -> Self.SubSequence
    public func dropLast(n: Int) -> Self.SubSequence
    public func prefix(maxLength: Int) -> Self.SubSequence
    public func suffix(maxLength: Int) -> Self.SubSequence
    public func split(maxSplit: Int, allowEmptySlices: Bool, @noescape isSeparator: (Self.Generator.Element) -> Bool) -> [Self.SubSequence]
}

Indexable

typealias Index : ForwardIndexType
public var startIndex: Self.Index { get }
public var endIndex: Self.Index { get }
public subscript (position: Self.Index) -> Self._Element { get }

struct IndexingGenerator<Base : Indexable> : GeneratorType {
  private let base: Base
  private var i: Base.Index
  mutating func next() -> Base._Element? {
    return i == base.endIndex ? nil : base[i++]
  }
  init(_ base: Base) {
    self.base = base
    i = base.startIndex
  }
}

mutating func next() -> Base._Element? {
  return i <= base.endIndex ? base[i++] : nil
}

let word = "hello".characters

for (index, value) in word.enumerate() {
  print(value)
  word[index] 
}

extension CollectionType {
  func forEachIndex(@noescape body: (Index, Generator.Element) -> ()) {
    for (i, v) in zip(indices, self) {
      body(i, v)
    }
  }
}

extension CollectionType {
  func forEachIndex(@noescape body: (Index, Generator.Element) -> ()) {
    for i in indices {
      body(i, self[i])
    }
  }
}

extension List : Indexable {
  var startIndex: Int { return 0 }
  var endIndex: Int {
    guard case let .Cons(_, xs) = self else { return 0 }
    return xs.endIndex + 1
  }
  subscript(i: Int) -> Element {
    switch (i, self) {
    case (0, .Cons(let v, _)): return v
    case (_, .Cons(_, let x)): return x[i - 1]
    default: fatalError()
    }
  }
}

CollectionType

public protocol CollectionType : Indexable, SequenceType {
    typealias Generator : GeneratorType = IndexingGenerator<Self>
    public func generate() -> Self.Generator
    typealias SubSequence : Indexable, SequenceType = Slice<Self>
    public subscript (position: Self.Index) -> Self.Generator.Element { get }
    public subscript (bounds: Range<Self.Index>) -> Self.SubSequence { get }
    public func prefixUpTo(end: Self.Index) -> Self.SubSequence
    public func suffixFrom(start: Self.Index) -> Self.SubSequence
    public func prefixThrough(position: Self.Index) -> Self.SubSequence
    public var isEmpty: Bool { get }
    public var count: Self.Index.Distance { get }
    public var first: Self.Generator.Element? { get }
}

struct UpTo: CollectionType {
  let startIndex = 0
  let endIndex: Int
  subscript(i: Int) -> Int { return i }
}

UpTo(endIndex: 10)[3...7] 

UpTo(endIndex: 10)[3...7].startIndex 

RangeReplaceableCollectionType

public protocol RangeReplaceableCollectionType : CollectionType {
    public init()
    public mutating func replaceRange<C : CollectionType where C.Generator.Element == Generator.Element>(subRange: Range<Self.Index>, with newElements: C)
    public mutating func reserveCapacity(n: Self.Index.Distance)
    public mutating func append(x: Self.Generator.Element)
    public mutating func extend<S : SequenceType where S.Generator.Element == Generator.Element>(newElements: S)
    public mutating func insert(newElement: Self.Generator.Element, atIndex i: Self.Index)
    public mutating func splice<S : CollectionType where S.Generator.Element == Generator.Element>(newElements: S, atIndex i: Self.Index)
    public mutating func removeAtIndex(i: Self.Index) -> Self.Generator.Element
    public mutating func removeFirst() -> Self.Generator.Element
    public mutating func removeFirst(n: Int)
    public mutating func removeRange(subRange: Range<Self.Index>)
    public mutating func removeAll(keepCapacity keepCapacity: Bool)
}

reserveCapacity

underestimateCount()

延迟加载

译者注：严格求值（strict evaluation）

1. 你可以为你的方法写 4 个版本，每个版本对应标准库中延迟加载序列的方法。

2. 定义一个新的协议类型 LazySequenceType，让标准库的结构体遵循该协议：
public protocol LazySequenceType : SequenceType {}
extension LazySequence : LazySequenceType {} extension LazyForwardCollection : LazySequenceType {} extension LazyBidirectionalCollection : LazySequenceType {} extension LazyRandomAccessCollection : LazySequenceType {}