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

Design Patterns in Swift: Builder

cover7

The problem:

Our customers at YourMechanic request quotes through our website or through their YourMechanic App. A quote is a complicated object. It must have a car, at least one service, the customer’s contact information, a mechanic capable of doing the services, picked automatically by the system or selected by the user and a coupon code that a quote may or may not have. We need a system that can build our quote and guarantee its validity. The system should be extendable and capable of dealing with changes to our quote creation process, ideally without having to change anything in the quote object itself.

The solution:

A quote is a composite of specific data from multiple different objects. Some these objects may not be all available at once, so we cannot have a valid quote object until all the needed data points are collected. Our first step is to figure out the data we need, then we will use a builder that will take these data points and builds the quote from the ground up. We are also going to task our builder with verifying the validity of our object, which can be as specific or as broad as we want. For our case, beside ensuring the presences of all the specific data required to create a quote, we are also going to ensure that our quote has a valid mechanic. This means we will check against the minimum required skill to complete a set of services against the mechanic selected by the user. If the mechanic cannot perform the jobs, the builder will complain that the quote object is invalid.

Continue reading “Design Patterns in Swift: Builder”

Design Patterns in Swift: Adapter

cover11

The problem:

YourMechanic is expanding to Canada. Now our friends to the north can have their cars fixed at their home or office by one of our professional mechanics. To finalize our expansion, we need to make major changes to our system. Providing support for the Canadian currency and the metric system would be a lot of work and we are short on time. Therefore we want an easy way to interface with our current Quote API. The Quote API can add and remove parts, set labor times for a quote, calculate a total price and track a car’s mileage. There also two properties, tax rates and labor rates which cannot be set but are derived from some external data source that we do not have access. All these values are assumed in USD/Imperial by our current system. We need a way to both display and input values in CAD and the metric system and have it remain consistent throughout our system. Also tax rates and labor rates are different in Canada so we need to adapt for those changes as well.

The solution:

We will define an adapter that will implement the same set of functions as our original API. This new adapter will take an instance of our original API as a parameter and will act as a middleman between calls. If a function call in our original API needs to be manipulated in anyway to deal with our new Canadian requirements, the adapter will take care of it. If not, the adapter will simply call the original API function with the same parameters passed to it.

Continue reading “Design Patterns in Swift: Adapter”

Design Patterns in Swift: Prototype

cover10

The problem:

Beside having qualified mechanics working for the general public, YourMechanic has several contracts with various businesses. The appointments for these jobs for the most part follow the same configuration (same mechanics, same set of services, same parts, same number of cars and prices). What’s different is the name of the client, the address and the start time. Building a corporate appointment over and over again with the same configuration is time consuming and heavy on our servers. We would like a solution where the same appointment type can be re-created without having to look up our mechanic directory, parts directory or service directory.

The solution:

We will solve this problem by creating a prototype of our corporate appointment object (for the sake of consistency between all our previous articles we will call this corporate quote). This prototype will have all its heavy configuration pre-set. This way, every time we need to create a specific corporate quote we simply clone our prototype and set its client name, address and start time. This way, once we build an appointment with the same set of mechanics, services, parts etc we can clone the quote for different clients instead of rebuilding it from the ground up.

Continue reading “Design Patterns in Swift: Prototype”

Design Patterns in Swift: Interpreter

cover9

The problem:

Our customers at YourMechanic  request quotes through our website or through their YourMechanic App. The final price for a quote is a combination of two variables, the cost of parts and the cost of labor. We want the ability to apply specific adjustments to either parts or labor prices. These adjustments could come from coupons, gift certificates or discounts. We need a simple language that can express these custom adjustments. For example, we should be able to define an expression that can add a 20% discount for parts. Or a another code that reduces $10 on labor. Or one that does both.

The solution:

We will define a simple language for adjustments. We will have a set of rules that will cover addition, subtraction, multiplication and division. We will also define two variables that our language will map for parts and labor prices. Once the language is defined, our users can express adjustments through a string that abides by our grammar. For example, to subtract $10 dollars from parts we would use:

var expression = "l + p - 10.00"
//adjustment: total price is labor + partsPrice - $10

Continue reading “Design Patterns in Swift: Interpreter”

Design Patterns in Swift: Visitor

cover8

The Problem:

Our customers at YourMechanic can request quotes through our website or through their YourMechanic App. We send out an email and create an internal report when such quotes are requested. After the customer views the quote and decides to book it, that quote becomes an appointment. We send out an email and create an internal report when that happens as well. The content of the email and the report are dynamically generated from the information contained in the quote and the appointment.  We need a system that can provide us with an easy and straightforward way of composing these documents. Ideally we hope to achieve this without adding repeated report/email functionality to our already cluttered Quote and Appointment class.

The solution:

We define our quote and appointment class to accept visitor object. We then define these objects for emails and reports. When these objects are accepted into their respective visiting classes, they can generate the documents needed without having to be part of that class. The Visitor design pattern has always been a little counter intuitive to understand so we are going to approach this step by step, with as much details as possible.

Continue reading “Design Patterns in Swift: Visitor”

Design Patterns in Swift: State

cover6

The Problem:

A quote goes through many phases before it is completed by a mechanic. Initially a customer request a quote, once received, our system attempts to automatically provide a quote for the customer. If our system doesn’t have enough information, the quote becomes pending. At this state a member of our customer support team finds out what’s needed to provide a ready quote. Once a quote is ready, the customer can use it to book an appointment. Once an appointment is booked a mechanic is assigned to the quote. We need to be able to retrieve this mechanic’s information. When the appointment is completed we generate a receipt and send it to the customer.

We need a system that can provide us with an interface to get the price, get a customized message that’s dependant on the quotes’s state, and provide the receipt when the appointment is complete.

The solution:

We will define a context that will hold our quotes’s current state. We will then define a class for every state in which our quote can be in and have our context be responsible for changing its state. Our context will also provide us with an interface for the common functionalities that we expect from our quote, regardless of the state it’s in.

Continue reading “Design Patterns in Swift: State”