Generating sustainable code with: Generators

TL;DR: Generators can hide stateful operations for you.

No time for FP vs OOP. Instead we will concentrate on the clarity and reusability of Protocol-Oriented code, while enhancing the well known for in loop.

When you got such a loop, there is a chance that you might keep track of a certain value and change the related variable in each iteration.

Like, building a sum of all the elements up to the current element …

var sum = 0 
for i in 0.stride(to: 100, by: 5) {
  sum = sum + i
  print(i, sum)
}

These lines sum up the values in each iteration, e.g. to get the starting point when you draw a horizontal bar, and you want to know the starting x for each bar segment.

Extra shoutouts for using stride, but calculating the sum this way is not reusable at all. In those 5 lines of code, the word sum appears 4 times. Amazing how much visual space is dedicated to that simple operation. And worse, once you have more complicated conditions or even multiple things to keep track of, you enter the dark zone. This is where you code gets unmanageable, hard to understand at first sight and possibly dangerous.

Some people claim: “No, thats the easiest way to do. I don`t need another concept for this.”

Sure, we will find out.

Any generator is good enough 🤖

So the basic thing to understand at first is the SequenceType and the related Generator it has. When you look into the doc of SequenceType, the first line makes it clear:

A type that can be iterated with a for ... in loop.

Many protocols conform to this protocol (CollectionType, LazyCollectionType, … ), check out the Adopted By section in the docs.

So when you have a SequenceType you get a Generator from it, which returns an Element for each .next() call. Eventually the sequence is done, there is no more Element left, and you will get nil: The loop is done

/// A pretty useless Custom SequenceType
/// which is basically just wrapping the Sequence and is returning a Generator
struct CustomSequence<S where S: SequenceType>: SequenceType {
  let sequence: S
  func generate() -> AnyGenerator<S.Generator.Element> {
     // generator will be modified with each `next` call 
    var generator = sequence.generate()
    // use the init call of AnyGenerator which expects a closure like:
    // () -> Element?
    // the generator will be changed by each .next() call
    return AnyGenerator {
      // after the last element the generator will return nil 
      generator.next()
    }
  }
}
// [Int] conforms to SequenceType
for i in CustomSequence(sequence: [1,2,3]) {
  print(i)
  // -> 1
  // -> 2
  // -> 3
}

Attention: Swift 3 will rename Generator to Iterator and there are more changes to come

This is a great start to add some more sugar to the for in loop.

The sum of it 🎲

In order to build up SequenceTypes that provide more power we need protocols.

First we add a basic protocol which declares that two variables of a type can be combined:

/// Semigroup in disguise
protocol Addable {
  /// let me guess: Int is a good candidate, or Double, or String, ... 
  func + (lhs: Self, rhs: Self) -> Self
}
// like 1 + 1 or "a" + "b"

And one more protocol: Before we get the first element of the loop, we need to have an initial value for the sum - a zero.

/// Monoid in disguise
protocol ImplicitDefault {
  static func implicitDefault() -> Self
}
// e.g. 0 for Int or "" for String

To sum up:

  • ✅ We have a protocol to ‘get an initial value for a sum’
  • ✅ We have a protocol to ‘add a value to a sum’

An implementation looks like this:

// Addable is supported automagically by + func
extension Int: ImplicitDefault, Addable { 
  // expected from ImplicitDefault
  static func implicitDefault() -> Int {
    return 0
  }
}

Now we build a Sequence Type which knows about those two protocols.

/// A SequenceType where the Element from the Generator 
/// support Addable and ImplicitDefault
struct ZipWithSum<S where
  S: SequenceType,
  // the element should know whats it`s zero value is
  S.Generator.Element: ImplicitDefault,
  // the element should know how it can be added to another element 
  S.Generator.Element: Addable         
  >: SequenceType {
  // the wrapped sequence
  let sequence: S
  // btw: we return 2 values in each loop - the element and the sum 
  // which is of the same type as the element.
  func generate() -> AnyGenerator<(S.Generator.Element, S.Generator.Element)> {
    // here comes the initial state
    var generator = sequence.generate()
    // ImplicitDefault tells us how to start with the sum
    var sum = S.Generator.Element.implicitDefault()
    // just a generator, initialized with a trailing closure
    return AnyGenerator {
      // 1. getting next from the generator
      let element = generator.next()
      switch element {
      case let e?:
        // 2. adding to the sum
        // Addable allows us to add the sum and the element
        sum = sum + e
        return (e, sum)
      case .None:
        return nil
      }
    }
  }
}

Thats it.

What do we gain?

Compare:

/// Yes, you don`t need the Generators, you can master the mess
var sum = 0
for i in 0.stride(to: 100, by: 1) {
  sum = sum + i
  print(i, sum)
}

// No, you can do way better
for (i, sum) in 0.stride(to: 100, by: 1).zipWithSum() {
  print(i, sum)
}

The zipWithSum is concise and meaningful at the same time. And the best part: You will never ever have to calculate a sum in a loop again. The calculation went into a sequence type function. All that is left is the code you really want to focus on.

Btw: If you wonder why am i using stride instead of a range? There is no reason. Of course you can also take a simple range.

Fold all the things 🗺

Now it is up to you. You can stop reading and say: “It`s enough, I don`t want more abstraction in my code”. Or we can go one step further. (And i bet there a lot of ways to make this concept even better).

But first - one step back: when we try to describe what “building a sum” is, in an abstract way, we can use the following (curried) type signature:

/// THIS IS PSEUDO SWIFT 
/// Accumulator means Sum
let buildingSum: (Accumulator, Element) -> Accumulator = { $0 + $1 }

The type signature is the interesting part: A -> E -> A (curried notation). If you are a category theory fan - i will call it a Catamorphism. What`s so interesting about this signature? Well you can build up anything by destroying the previous structured value: Like group by, filter, sum, difference and so forth.

Gimme the protocol to start from!

protocol Foldable {
  // should be associatedtype but syntax highlighting did not work
  typealias A
  typealias B
  // the initial value to start of Type A. 
  var initial: A { get }
  // Thats the way to take each element (B) 
  // and put it into your accumulator (A)
  // and you get back a .... accumulator (A)
  func fold(a: A, b: B) -> A
}

You can see a rebuild of the sum example in the following code.
Interestingly, the sum operation now becomes a Type. And types are awesome.

struct Sum<A: Addable>: Foldable {
  // init w/o named arguments
  init(_ initial: A) {
    self.initial = initial
  }
  let initial: A
  // the constraint Addable lets us add all Elements
  // and in this case A and B are the same type!
  // b/c Int + Int -> Int
  func fold(a: A, b: A) -> A {
    return a + b
  }
}

Next we add a new SequenceType which has a Generator that returns the result of the current fold in each iteration….

struct ZipFold<S, F where
  S: SequenceType,
  F: Foldable,
  // we make sure the 2nd arg in the fold can take the Element
  S.Generator.Element == F.B
  >: SequenceType {
  
  let sequence: S
  let f: F
  
  func generate() -> AnyGenerator<(S.Generator.Element, F.A)> {
    // initial state
    var generator = sequence.generate()
    var fold = f.initial
    // the generator for each loop
    return AnyGenerator {
      let element = generator.next()
      switch element {
      case let e?:
        // here we are folding the element into the fold 
        let b = self.f.fold(fold, b: e)
        fold = b
        return (e, b)
      case .None:
        return nil
      }
    }
  }
}
/// the handy shortcut to make the zip with fold available to every sequence type.
extension SequenceType {
  /// a function to call zipFold on any sequence by providing a fold
  /// again: the B Type of the fold needs to match the Element Type
  func zipFold<F: Foldable where F.B == Self.Generator.Element>(f: F) -> ZipFold<Self, F> {
    return ZipFold(sequence: self, f: f)
  }
}

The Proof of Pudding 🍮

The zip fold is done. The motivation is to abstract away the operations you want to perform on every loop. You will find all the implementations in the Gist at the end.

let list = [1, 4, 10, 15, -4, -10, 0, -3, 8, 22, 55, -14, -24, 0]

Question: What does the result for sum look like?

for (i, sum) in list.zipFold(Sum(0)) {
  print(i, sum)
}

Question: Want to start the sum at 100?

for (i, sum) in list.zipFold(Sum(100)) {
  print(i, sum)
}

Question: Want to see the min value up to each position?

for (i, min) in list.zipFold(Min(0)) {
  print(i, min)
}

Question: Want to see the worst three values on each position?

for (i, worstThree) in list.zipFold(Worst(3)) {
  print(i, worstThree)
}

Question: Want to see the Min and the Sum at each position?

let minSum = Both((Min(0), Sum(0)))

for (i, (min, sum)) in list.zipFold(minSum) {
  print(i, min, sum)
}

Question: What is the lowest value when we reach a sum of 100?

let minSum = Both((Min(0), Sum(0)))

for (i, (min, sum)) in list.zipFold(minSum) where sum >= 100 {
  print(i, min, sum)
}

Question: Is it better than writing the loop manually?

Of course. This is a great way to abstract away code that smells in front of your nose.

To the naysayers 🕵

/// still valid swift 
var sum = 0
var min = 0
for i in list {
  if i < min {
    min = i
  }
  sum = sum + i
  print(i, sum, min)
}

Ah yes - the playground - s’il vous plaît.

👻 Feel free to hit me on twitter. @elmkretzer