SequenceType

We are all familiar with collection types. Array, probably, the most common way to represent collection of items. We can easily iterate through by using for loop.

let array: Array<Int> = [2, 3, 5, 7, 11, 13, 17]
for i in 0..<array.count {
  print(array[i])
}

Another Swift collections representations, like Dictionary, Set and others has one important thing in common: all of them are adopting SequenceType protocol. We can create custom sequences for very wide range of purposes. It can be finite or inifinite sequence. For instance, we may need the ‘powers of 2’ sequence or similar.

SequenceType is a type, that can be iterated with a for...in loop.

SequenceType protocol has two associated types and a bunch of extremely useful methods for getting subsequences, iterating and your lovely map and filter.

public protocol SequenceType {
    associatedtype Generator : GeneratorType
    associatedtype SubSequence

    public func generate() -> Self.Generator
    ...
    ...
}

The generate() -> Self.Generator method returns a generator over the elements of this sequence. Where Generator is a type that provides the sequence’s iteration interface and encapsulates its iteration state.

GeneratorType

GeneratorType is a simple protocol, which contains one associated type and one method - next()

public protocol GeneratorType {
    associatedtype Element
    public mutating func next() -> Self.Element?
}

Element is a type of an element generated by self, and next() returns an element if it exists, otherwise returns nil.

The most convenient way of sequences is the generation of some famous math function like Fibonaci sequence or Powers of 2 sequence. I want to demonstrate Sequences and Generators power by creating some convenience methods for NSDate.

Disclaimer: NSCalendar and NSDate are complex classes (or class clusters). Working with them, you need to take in concideration a lot of boilerplates, like time zone calculations, device locale and other important calculations. This article omits most of them. The purpose of it is Generators and sequences demonstration. Samples may be far-fetched.

Problem. Spanish lessons schedule

Let’s imagine, that we want to learn the new language. Spanish, for example. Your professor told you, that you will have one lesson each N days starting from today. But the bad thing – your professor doesn’t want to work on Sundays. So if the lesson is on Sunday, it will be rescheduled to the next day. We want to receive the schedule – Array<NSDate> for M days.

Solution

Small preparations

Lets start from adding some convenience functions to NSDate

First of all, we will extend Int with calendarUnit(:) function. This function returns NSDateComponents object depending on given NSCalendarUnit. For the sake of convenience, we add days var (that’s enough for our example, but you can add the same for all the calendar units you need).

extension Int {
  public var days: NSDateComponents {
    return self.calendarUnit(.Day)
  }

  private func calendarUnit(unit: NSCalendarUnit) -> NSDateComponents {
    let dateComponents = NSDateComponents()
    dateComponents.setValue(self, forComponent: unit)
    return dateComponents
  }
}

Next we will write small NSDate extension. For our convenience we will wrap NSDate to be able to get the value of the needed NSDateComponent.

extension NSDate {
  private func valueForUnit(unit: NSCalendarUnit) -> Int {
    return calendar.component(unit, fromDate: self)
  }
  
  var weekday: Int {
    return valueForUnit(.Weekday)
  }
}

print(NSDate().weekday)
// > prints current weekday index (1..7, where 1 is Sunday)

Then we define function + to have ability to add date components to our NSDate:

func + (date: NSDate, component: NSDateComponents) -> NSDate {
  return calendar.dateByAddingComponents(component, toDate: date, options: NSCalendarOptions(rawValue: 0))!
}

Now we are able to perform calculation like this:

let date = NSDate()
let nextDay = date + 1.days

Schedule generator

Our generator will look like this:

class DateGenerator: GeneratorType {
  var dayOffWeekday: Int = 1 // Sunday
  var N: Int = 3
  
  var lessonsCount: Int
  var startDate: NSDate
  
  private var numIterations = 0
  
  init(_ start: NSDate, _ numLessons: Int) {
    lessonsCount = numLessons
    startDate = start
  }
  
  func next() -> NSDate? {
    guard numIterations < lessonsCount else {
      return nil
    }
    numIterations += 1
    
    var next = startDate + N.days
    if next.weekday == dayOffWeekday {
      next = next + 1.days
    }
    startDate = next
    return next
  }
}

let dg = DateGenerator(NSDate(), 10)
dg.N = 3 // we will have one lesson each 3 days
dg.dayOffWeekday = 1
while let date = dg.next() {
  print(date)
}

As you see in the code sample above, in some point our generator returns nil. This is a very important moment! If you remove nil termination, generator will continue to produce values while your computer has free memory.

Another important moment is, if you try to iterate through dg one more time, it will not work as expected, because the instance of the generator is already exhausted.

while let date = dg.next() { // Exhausted
  print(date)
}
// does nothing. 

We implemented DateGenerator to build a sequence on it.

class DateSequece: SequenceType {
  var lessonsCount: Int
  var startDate: NSDate
  
  init(_ start: NSDate, _ numLessons: Int){
    lessonsCount = numLessons
    startDate = start
  }
  
  func generate() -> DateGenerator {
    return DateGenerator(startDate, lessonsCount)
  }
}

As you see, sequence code is very simple and understandable. Actually, our Spanish schedule problem is solved :)

// Contains needed dates for the next 10 lessons
let schedule = Array(DateSequece(NSDate(), 10))

It’s not always needed to write your own generator. Apple guys are smart, and for the most cases you can use AnyGenerator. Rewrited with AnyGenerator, our sequence will look like this:

class SimpleDateSequece: SequenceType {
  var lessonsCount: Int
  var startDate: NSDate
  var daysStep: Int = 1
  private var numIterations = 0
  
  init(_ start: NSDate, _ numLessons: Int, step: Int){
    lessonsCount = numLessons
    startDate = start
    daysStep = step
  }
  
  func generate() -> AnyGenerator<NSDate> {
    return AnyGenerator(body: {
      guard self.numIterations < self.lessonsCount else {
        return nil
      }
      self.numIterations += 1
      
      let next = self.startDate + self.daysStep.days
      self.startDate = next
      return next
    })
  }
}

let simpleSequence = Array(SimpleDateSequece(NSDate(), 5, step: 4))

Infinite sequences

Remember, we were afraid to remove nil termination? This is the time to do it:

class InfiniteDateGenerator: GeneratorType {
  var startDate: NSDate
  
  private var numIterations = 0
  
  init(_ start: NSDate) {
    startDate = start
  }
  
  func next() -> NSDate? {
    let next = startDate + 1.days
    startDate = next
    return next
  }
}

class InfiniteDateSequece: SequenceType {
  var startDate: NSDate
  
  init(_ start: NSDate){
    startDate = start
  }
  
  func generate() -> InfiniteDateGenerator {
    return InfiniteDateGenerator(startDate)
  }
}

let infiniteSequence = Array(InfiniteDateSequece(NSDate()))

If you are using a playground, then you can see an infinite loop right after you hit Cmd+S shortcut. No worries, we can get needed amount of elements from the infinite sequence:

let tenFirstLessonsDates = Array(InfiniteDateSequece(NSDate()).prefix(10))

One of the key benefit of infinite sequences is ability to modify all it’s elements according to the rule. For instance, i want first 10 dates of our infinite sequence, but I hate Mondays. So I want to throw Mondays away:

let mondayIndex = 2
let noMondaysSequence = Array( InfiniteDateSequece(NSDate()).filter({$0.weekday != mondayIndex}).prefix(10) ) // Infinite

Surprizingly, but this approach will not work, because we have infinite sequence. LazySequenceType is the same as SequenceType, with the key difference, that the elements of the result function, such as map, filter, e. t. c. are computed on-demand as the result is used. To make sequence lazy use the lazy property of the sequence:

let lazyNoMondaysSequence = Array( InfiniteDateSequece(NSDate()).lazy.filter({$0.weekday != mondayIndex}).prefix(10) ) 

Voila! We have finite dates sequence without Mondays.

Conclusion

SequenceType and GeneratorType are one of the most used protocols (even if you don’t see it). It is also correct and elegant solution for dealing with difficult data collections generating and iterating.

Resources

Article Playground

Where to go from here?

Check official Apple documentation for more GeneratorType, SequenceType and AnyGenerator info. Another good explanations of sequences and generators you can find in “Functional Swift” book by Chris Eindhoff.