Swift Functional Programming Tutorial

The Magic Behind Reduce

In the previous section, you developed your own implementation of filter, which was surprisingly simple. You’ll now see that the same is true for reduce.

Add the following to your playground:

extension Array {
  func myReduce<T, U>(seed:U, combiner:(U, T) -> U) -> U {
    var current = seed
    for item in self {
      current = combiner(current, item as T)
    }
    return current
  }
}

The above adds a myReduce method to Array that mimics the built-in reduce function. This method simply iterates over each item in the array, invoking combiner at each step.

To test out the above, replace one of the reduce methods in your current playground with myReduce.

At this point, you might be thinking, “Why would I want to implement filter or reduce myself?” The answer is, “You probably wouldn’t!”

However, you might want to expand your use of the functional paradigm in Swift and implement your own functional methods. It’s encouraging (and important!) to see and understand just how easy it is to implement powerful methods like reduce.

Building an Index

It’s time to tackle a more difficult problem, and that means it’s time to open a new playground. You know you want to!

In this section, you’re going to use functional programming techniques to group a list of words into an index based on the first letter of each word.

Within your newly created playground, add the following:

import Foundation

let words = ["Cat", "Chicken", "fish", "Dog",
                      "Mouse", "Guinea Pig", "monkey"]

To accomplish this section’s task, you’re going to group these words by their first letters (case insensitive!).

In preparation, add the following to the playground:

typealias Entry = (Character, [String])

func buildIndex(words: [String]) -> [Entry] {
  return [Entry]()
}
println(buildIndex(words))

The Entry typealias defines the tuple type for each index entry. Using a typealias in this example makes the code more readable, removing the need to repeatedly specify the tuple type in full. You’re going to add your index-building code in buildIndex.

Building an Index Imperatively

Starting with an imperative approach, update buildIndex as follows:

func buildIndex(words: [String]) -> [Entry] {
  var result = [Entry]()
  
  var letters = [Character]()
  for word in words {
    let firstLetter = Character(word.substringToIndex(
      advance(word.startIndex, 1)).uppercaseString)

    if !contains(letters, firstLetter) {
      letters.append(firstLetter)
    }
  }
  
  for letter in letters {
    var wordsForLetter = [String]()
    for word in words {
      let firstLetter = Character(word.substringToIndex(
        advance(word.startIndex, 1)).uppercaseString)

      if firstLetter == letter {
        wordsForLetter.append(word)
      }
    }
    result.append((letter, wordsForLetter))
  }
  return result
}

This function has two halves, each with its own for loop. The first half iterates over each of the words to build an array of letters; the second iterates over these letters, finding the words that start with the given letter, to build the return array.

With this implementation in place, you’ll see the desired output:

[(C, [Cat, Chicken]),
 (F, [fish]),
 (D, [Dog]),
 (M, [Mouse, monkey]),
 (G, [Guinea Pig])]

(The above is formatted a little for clarity.)

This imperative implementation has quite a few steps and nested loops that can make it difficult to understand. Let’s see what a functional equivalent looks like.

Building an Index the Functional Way

Create a new playground file and add the same initial structure:

import Foundation

let words = ["Cat", "Chicken", "fish", "Dog",
                      "Mouse", "Guinea Pig", "monkey"]

typealias Entry = (Character, [String])

func buildIndex(words: [String]) -> [Entry] {
  return [Entry]();
}

println(buildIndex(words))

At this point, the println statement will output an empty array:

[]

The first step toward building an index is to transform the words into an array that contains only their first letters. Update buildIndex as follows:

func buildIndex(words: [String]) -> [Entry] {
  let letters = words.map {
    (word) -> Character in
    Character(word.substringToIndex(advance(word.startIndex, 1)
      ).uppercaseString)
  }
  println(letters)
  
  return [Entry]()
}

The playground now outputs an array of uppercase letters, each one corresponding to a word in the input array.

[C, C, F, D, M, G, M]

In the previous sections, you encountered filter and reduce. The above code introduces map, another functional method that’s part of the array API.

map creates a new array with the results of calls to the supplied closure for each element in the supplied array. You use map to perform transformations; in this case, map transforms an array of type [String] into an array of type [Character].

The array of letters currently contains duplicates, whereas your desired index has only a single occurrence of each letter. Unfortunately, Swift’s array type doesn’t have a method that performs de-duplication. It’s something you’re going to have to write yourself!

In the previous sections, you saw how easy it is to re-implement reduce and filter. It will come as no surprise that adding a de-duplication method of your own isn’t tricky, either.

Add the following function to your playground before buildIndex:

func distinct<T: Equatable>(source: [T]) -> [T] {
  var unique = [T]()
  for item in source {
    if !contains(unique, item) {
      unique.append(item)
    }
  }
  return unique
}

distinct iterates over all the items in an array, building a new array that contains only the unique items.

Update buildIndex to put distinct to use:

func buildIndex(words: [String]) -> [Entry] {
  let letters = words.map {
    (word) -> Character in
    Character(word.substringToIndex(advance(word.startIndex, 1)
      ).uppercaseString)
  }
  let distinctLetters = distinct(letters)
  println(distinctLetters)
  
  return [Entry]()
}

Your playground will now output the unique letters:

[C, F, D, M, G]

Now that you have an array of distinct letters, the next task in building your index is to convert each letter into an Entry instance. Does that sound like a transformation? That’ll be another job for map!

Update buildIndex as follows:

func buildIndex(words: [String]) -> [Entry] {
  let letters = words.map {
    (word) -> Character in
    Character(word.substringToIndex(advance(word.startIndex, 1)
      ).uppercaseString)
  }
  let distinctLetters = distinct(letters)
  
  return distinctLetters.map {
    (letter) -> Entry in
    return (letter, [])
  }
}

The second call to map takes the array of characters and outputs an array of Entry instances:

[(C, []), 
 (F, []), 
 (D, []), 
 (M, []), 
 (G, [])]

(Again, the above is formatted for clarity.)

You’re almost done. The final task is to populate each Entry instance with the words that begin with the given letter. Update the function to add a nested filter, as follows:

func buildIndex(words: [String]) -> [Entry] {
  let letters = words.map {
    (word) -> Character in
    Character(word.substringToIndex(advance(word.startIndex, 1)
      ).uppercaseString)
  }
  let distinctLetters = distinct(letters)
  
  return distinctLetters.map {
    (letter) -> Entry in
    return (letter, words.filter {
      (word) -> Bool in
     Character(word.substringToIndex(advance(word.startIndex, 1)
       ).uppercaseString) == letter
    })
  }
}

This provides the desired output:

[(C, [Cat, Chicken]),
 (F, [fish]),
 (D, [Dog]),
 (M, [Mouse, monkey]),
 (G, [Guinea Pig])]

In the second half of the function, there’s now a nested call to filter inside map. That will filter the list of words for each distinct letter, and thus identifies the words starting with the given letter.

The above implementation is already more concise and clear than its imperative equivalent, but there’s still room for improvement: this code extracts and capitalizes a word’s first letter multiple times. It would be good to remove this duplication.

If this were Objective-C code, you would have a few different options at your disposal: You could create a utility method that performs this functionality, or perhaps you could add this method directly to NSString via a class category. However, if you only ever need to perform this task within buildIndex, a utility method lacks semantic clarity and using a class category is overkill.

Fortunately, with Swift, there’s a better way!

Update buildIndex with the following:

func buildIndex(words: [String]) -> [Entry] {
  func firstLetter(str: String) -> Character {
    return Character(str.substringToIndex(
            advance(str.startIndex, 1)).uppercaseString)
  }
  
  let letters = words.map {
    (word) -> Character in
    firstLetter(word)
  }
  let distinctLetters = distinct(letters)
  
  return distinctLetters.map {
    (letter) -> Entry in
    return (letter, words.filter {
      (word) -> Bool in
      firstLetter(word) == letter
    })
  }
}

You’ll see exactly the same output as before.

The above code adds a firstLetter function that is nested within buildIndex and as a result, is entirely local to the outer function. This takes advantage of Swift’s first-class functions that you can treat much like variables, allowing for assignment and scoping.

The new code removes the duplicate logic, but there’s even more you can do to clean up buildIndex.

The first map step that constructs the array of letters takes a closure whose signature is (String) -> Character. You may notice this is exactly the same signature as the firstLetter function you just added, which means you can pass it directly to map.

Making use of this knowledge, you can rewrite the function as follows:

func buildIndex(words: [String]) -> [Entry] {
  func firstLetter(str: String) -> Character {
    return Character(str.substringToIndex(
            advance(str.startIndex, 1)).uppercaseString)
  }
  
  return distinct(words.map(firstLetter))
    .map {
      (letter) -> Entry in
      return (letter, words.filter {
        (word) -> Bool in
        firstLetter(word) == letter
      })
    }
}

The end result is concise, yet highly expressive.
Perhaps you’ve noticed an interesting side effect of the functional techniques you have employed so far. While your imperative solutions have relied on variables (as defined using the var keyword), you’ve defined everything in the functional equivalents as constants (via let).

You should strive for immutability; immutable types are easier to test and aid concurrency. Functional programming and immutable types tend to go hand in hand. As a result, your code will be more concise as well as less error-prone. And it will look cool and impress your friends!

Challenge: Currently, buildIndex returns an unsorted index; the order of the Entry instances depends on the order of the words in the input array. Your challenge is to sort the index into alphabetic order. For the example array of strings, this would give the following output:

[(C, [Cat, Chicken]),
 (D, [Dog]),
 (F, [fish]),
 (G, [Guinea Pig]),
 (M, [Mouse, monkey])]

[spoiler title=”Hint”]Swift’s Array type has a sort method, but this method mutates the array rather than returning a new, sorted instance, and it requires a mutable array on which to operate. In general, it’s safer to deal with immutable data, so I would advise against using this method! As an alternative, use the sorted method that returns a second sorted array.[/spoiler]