Swift: Infinite SequenceType

NOTE: Most of x-Type and Generator protocols have their name changed on Swift 3.0. For example SequenceType is now Sequence and Generator is now Iterator.

I spent most of my weekend playing around with Swift. I recently finished implementing an AVL tree that conforms to SequenceType, CollectionType and ArrayLiteralConvertible. One of the beauties of Swift is that you have access to the same technologies behind Arrays, Dictionaries and Sets. Or perhaps the correct way of saying is that those technologies themselves are written in Swift and you can use the same powerful features for your own custom data structure. There are concrete definition for what it takes to be a sequences or a collections. Protocols that if you conform to provides you many features that seem restricted to arrays or dictionaries. One of my favourite protocols is SequenceType. Within the scope of Arrays and Dictionaries, SequenceType represent a finite sequence, but things get much more interesting with infinite sequences. For example, check out these sequences: Even numbers, Powers of two, Prime numbers and Fibonacci.


//Sequence of positive even numbers
struct Even: SequenceType {
  func generate() -> AnyGenerator<Int> {
    var _first = 0
    return AnyGenerator<Int> {
      _first += 2
      return _first
    }
  }
}

//Sequence of powers of two
struct PowersOfTwo: SequenceType {
  
  func generate() -> AnyGenerator<Int> {
    var _item: Int = 0
    
    return AnyGenerator<Int> {
      _item = _item == 0 ? 1 : _item
      _item = _item << 1
      return _item
    }
  }
}

//Sequence of prime numbers
struct PrimeNumbers: SequenceType {

  func generate() -> AnyGenerator<Int> {
    var _pastPrimes: [Int] = []
    var _current: Int = 2
    return AnyGenerator<Int> {
      if _current == 2 {
        _current += 1
        return 2
      }
      var found: Bool = false
      var _result: Int = 2
      while !found {
        
        guard !(_current % 2 == 0) else {
          _current += 1
          continue
        }
        
        let hits = _pastPrimes.filter {_current % $0 == 0}
        
        guard hits.count == 0 else {
          _current += 1
          continue
        }
        
        _pastPrimes.append(_current)
        _result = _current
        found = true
        _current += 1
        
      }
      return _result
    }
  }
}

//Sequence of Fibonacci numbers
struct Fibonacci: SequenceType {
  func generate() -> AnyGenerator<Int> {
    var _last: Int = 1
    var _laster: Int = 1
    var _count: Int = 0
    var _result: Int = 0
    return AnyGenerator {
      _count += 1
      guard _count != 1 else {
        return _laster
      }
      guard _count != 2 else {
        return _last
      }
      _result = _last + _laster
      _laster = _last
      _last = _result
      return _result
    }
  }
}

They conform to SequenceType which requires a func named generator that returns a GeneratorType. For these examples I used an AnyGenerator, but the GeneratorType itself can be as complicated or simple as you want.
Each one of these SequenceTypes creates a generator that iterates through the sequence, giving the next item each time next(), the function a GeneratorType needs to implement is called.

The sequences I’ve written start out fairly simple and gets a bit more complicated, but overall the process is not too difficult.

But since our objects conform to Sequence type we can use them in Swift’s “For In” loops.


var evenSequence = Even()
for even in evenSequence {
  print (even)
}

var powerSequence = PowersOfTwo()
for power in powerSequence {
  print(power)
}

var fibonacciSequence = Fibonacci()
for fib in fibonacciSequence {
 print(fib)
}

var primeSequence = PrimeNumbers()

for prime in primeSequence {
  print(prime)
}

If you were to run the code above, it would never get passed the for loop for the first sequence. Since there are infinite even numbers, the sequence would never end. (Technically it would end after 18446744073709551614 but that’s offtopic right now). What’s interesting about our sequences are that unlike arrays or dictionaries, they are not finite. Since we only have to provide the next value in our generator, it’s possible to have a sequence that never runs out. We can easily remedy this for our for loop by taking the generator and calling next directly ourselves. Then we have control over how far in our sequence we want to go:

var even = Even().generate()
for _ in 0..<10 {
  if let val = even.next(){
    print(val)
  }
}

var power = PowersOfTwo().generate()
for _ in 0..<10 {
  if let val = power.next(){
    print(val)
  }
}

var fibo = Fibonacci().generate()
for _ in 0..<50 {
  if let val = fibo.next(){
    print(val)
  }
}

var prime = PrimeNumbers().generate()
for _ in 0..<200 {
  if let val = prime.next(){
    print(val)
  }
}

Conforming to SequenceTypes, beside giving us the ability to iterate over our sequence items in a “for in” loop, gives us a ton of other functionalities for free.
Taken from NSHipster at (http://nshipster.com/swift-collection-protocols/)

    • contains: Returns true if (1) a particular given element is found in the sequence or (2) an element satisfies the given predicate closure.
    • enumerate: Converts a sequence into a sequence of tuples, where each tuple is made up of a zero-based index and the value at that index in the sequence.
    • filter: Converts a sequence to an Array, keeping only the elements that match the given predicate closure.
    • join: Creates a collection from the sequence, with a given initial collection interposed between each element of the sequence. The initial element must be an ExtensibleCollectionType, described below.
    • lazy: Creates a “lazy sequence” from the given sequence. Subsequent calls to map, filter, and reverse on the sequence will be evaluated lazily—that is, until you access or iterate over the sequence, none of the transformations will be executed.
    • map: Converts a sequence to an Array after mapping each element with the transforming closure given.
    • maxElement: Returns the maximum value of a sequence of Comparable elements.
    • minElement: Returns the minimum value of a sequence of Comparable elements.
    • reduce: Given an initial value and a combining closure, this “reduces” a sequence to a single element through repeated calls to the closure.
    • sorted: Returns a sorted Array of the sequence’s elements. Sorting is automatically ascending for sequences of Comparable elements, or it can be based on a comparison closure.
    • startsWith: Returns true if one sequence starts with another sequence.
    • underestimateCount: Returns an underestimate of the number of elements in a sequence (SequenceTypes give no hints about length, so this will be zero for a sequence). Returns the actual count for CollectionType instances.
    • zip: Converts two sequences into a sequence of tuples, where each tuple is made up of one element from each sequence

.

Taken from NSHipster at (http://nshipster.com/swift-collection-protocols/)

Again, since our sequences are infinite, calling map, reduce or filter on it would break our code. This is where we would use lazy to get a lazy sequence. Here is how it would work:

Assume you want your sequence to be all the even number above 100, naturally you would want to use filter on your sequence, however filter on its own would try to go through the whole sequence and come back with a complete collection of even numbers above 100. This is where we would use lazy to get a lazy sequence which instead of bringing back a collection of all the even numbers above 100, would provide us with a sequence

var even = Even().generate()
var evenGreaterThanHundered = even.lazy.filter {$0 > 100}
var greaterThanHundered = evenGreaterThanHundered.generate()
print(greaterThanHundered.next())

our lazy sequence evenGreaterThanHundered will give us a new sequence which will potentially have all the even numbers above 100. Calling next on its generator will begin with 102 (as an optional of course)

"Optional(102)\n"

NOTE: Most of x-Type and Generator protocols have their name changed on Swift 3.0. For example SequenceType is now Sequence and Generator is now Iterator.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s