Function Composition in Swift

16 January 2015 by James Smith

This post is an exploration of several functional programming concepts. We’ll use strings as our problem space, but we won’t concern ourselves with the intricacies of Unicode.

In the first part of the post, I’ll define several functions using concepts from functional programming: map, filter and reduce.

Towards the end of the post, I’ll demonstrate how to combine the functions together using function composition to create more complex functions.

Let’s start by replicating NSString’s uppercaseString method.

First we’ll implement a simple function that transforms a character into its uppercase equivalent.

func uppercase(c: Character) -> Character

Before we work on the implementation let’s add an extension to the Character type that will help us get the underlying Unicode value for a Character:

extension Character {
  var unicodeScalar: UnicodeScalar {
    let scalars = String(self).unicodeScalars
    return scalars[scalars.startIndex]
  }
}

Now we can use this extension to implement uppercase:

func uppercase(c: Character) -> Character {
  let uppercaseCharacterCode: UInt32 = c.unicodeScalar.value - UnicodeScalar(32).value
  let uppercaseCharacterUnicodeScalar = UnicodeScalar(uppercaseCharacterCode)
  return Character(uppercaseCharacterUnicodeScalar)
}

In order to transform a lowercase character into its uppercase equivalent, we utilize a simple trick: subtract 32 from the character’s underlying value. This trick is certainly not the correct way to perform case mapping in Unicode, but it will work just fine for this example.

After calculating the new character code, we initialize a UnicodeScalar and pass it into the corresponding Character initializer.

Working with these underlying values is a bit of a pain. We can alleviate this a bit by overloading the - operator for operands of type UnicodeScalar:

func - (lhs: UnicodeScalar, rhs: UnicodeScalar) -> UnicodeScalar {
  return UnicodeScalar(lhs.value - rhs.value)
}

Let’s go ahead and do the same for the + operator as we’ll be needing it later:

func + (lhs: UnicodeScalar, rhs: UnicodeScalar) -> UnicodeScalar {
  return UnicodeScalar(lhs.value + rhs.value)
}

Now we can rewrite our function to manipulate the UnicodeScalar values directly:

func uppercase(c: Character) -> Character {
  return Character(c.unicodeScalar - UnicodeScalar(32))
}

Much better, but we’re not finished just yet. Currently our function will return unexpected results if a non-lowercase character is passed in. Let’s define some functions that we can use in our uppercase function to avoid this:

func isUppercase(c: Character) -> Bool {
    return c >= "A" && c <= "Z"
}func isLowercase(c: Character) -> Bool {
    return c >= "a" && c <= "z"
}

Here’s the final implementation of uppercase:

func uppercase(c: Character) -> Character {
  if isLowercase(c) {
    return Character(c.unicodeScalar - UnicodeScalar(32))
  }
  return c
}

Now the function only transforms the input character if it is lowercase. The lowercase function can be defined similarly:

func lowercase(c: Character) -> Character {
  if isUppercase(c) {
    return Character(c.unicodeScalar + UnicodeScalar(32))
  }
  return c
}

Recursion

Now that we have functions to transform the cases of individual characters, we can move on to define functions that work on strings. In order to make use of the functions we defined earlier, we will utilize recursion.

We can decompose a string into two parts: head and tail. The head is the first character of the string, and the tail is the remaining string that follows it. Here’s an example:

For the string “Swift”:
The character ‘S’ is the head.
The string “wift” is the tail.

We can reify these concepts as a String extension:

extension String {
  var head: Character? { return first(self) }
  var tail: String { return isEmpty ? self : dropFirst(self) }
}

The head property will return the first character of a string, or nil if the string is empty. The tail property will return the result of dropping the first character, or an empty string if the original string was empty.

Now we can implement uppercase for strings:

func uppercase(s: String) -> String {
  if let head = s.head {
    return String(uppercase(head)) + uppercase(s.tail)
  }
  return s
}

If the string is not empty, then we uppercase the head using the function we defined earlier and concatenate it with the result of passing the string’s tail to our new uppercase function. We can visualize the recursion like so:

uppercase("Swift")
"S" + uppercase("wift")
"SW" + uppercase("ift")
"SWI" + uppercase("ft")
"SWIF" + uppercase("t")
"SWIFT" + uppercase("")
"SWIFT"

The lowercase function is defined similarly:

func lowercase(string: String) -> String {
  if let head = string.head {
    return String(lowercase(head)) + lowercase(string.tail)
  }
  return string
}

To further demonstrate recursion, let’s implement a function that replaces all occurrences of a given character with another character:

func replaceCharacter(char: Character, withCharacter newChar: Character, #string: String) -> String {
  if let head = string.head {
    if head == char {
      return String(newChar) + replaceCharacter(char, withCharacter: newChar, string: string.tail)
    }
    return String(head) + replaceCharacter(char, withCharacter: newChar, string: string.tail)
  }
  return string
}

If the head of the string is equal to the character we want to replace, we return the new character concatenated with the result of passing the string’s tail into our new function. The character we wish to replace is replaced with the new character and we recursively do the same for the string’s tail.

If the head is not equal to the character we want to replace, we simply prepend the head to the result of passing the string’s tail into our new function.

Filter

filter takes an input sequence (an Array, for example) and a predicate. It then walks through the sequence and checks whether or not each element satisfies the predicate. If it does, the element is included in the filtered sequence. Here’s an example:

let names = ["James", "Terrence", "Joshua", "Daniel", "Hayden"]
let filteredNames = filter(names) { name in name.hasPrefix("J") }// filteredNames = ["James", "Joshua"]

We can use filter to create a function that removes all whitespace from a string:

func removeWhitespace(string: String) -> String {
  return String( filter(string) { $0 != Character(" ") } )
}

The $0 above is the current character that filter is checking. If the character is a space character, we exclude it from our new string. The result of filtering a string is a [Character] so we use a String initializer to return the correct type.

Reduce

reduce is an incredibly powerful function from the Swift standard library. It takes a sequence, an initial value and a combine closure. Here’s an example that demonstrates how to use reduce:

reduce("Swift", "") { str, char in str + String(uppercase(char)) }

“Swift” is the string we are reducing (the sequence)
An empty string is the initial value
The trailing closure is the combine closure
str is the accumulated value that is updated during each pass through the sequence
char is the character that is currently being operated on

In each pass through the string, we return the uppercased version of the current character concatenated with the accumulated value. This returned value becomes the accumulated value that used for the next pass through the string.

The code snippet above produces “SWIFT”. We could modify our implementation of uppercase to use reduce.

Here are two more functions that demonstrate reduce:

func length<T>(xs: [T]) -> Int {
  return reduce(xs, 0) { count, _ in count + 1 }
}func reverse(string: String) -> String {
  return reduce(string, "") { str, char in String(char) + str }
}

Map

map takes a sequence and a function that operates on each element of the sequence. It walks through the sequence and applies the function to each element. Here’s how we could implement uppercase using map:

String( map("Swift", uppercase) )

Function Composition

We have now built up a collection of small, useful functions that build upon functions included in the standard library. Using function composition, we can combine these small functions together to produce more complex functions. To demonstrate this idea, let’s replicate NSString’s capitalizeString:

func capitalize(string: String) -> String {
  let stringComponents = string.componentsSeparatedByString(" ")
  let capitalizedComponents = stringComponents.map {
    uppercase($0.head ?? Character("")) + $0.tail
  }
  return " ".join(capitalizedComponents)
}

First we get each word from the string and assign it to a constant called stringComponents. We then map over the array of words, uppercasing the head of each one. Finally we use the join method from the String type to interpose a space between each capitalized word, producing a single string.

Let’s try and rewrite this function as a series of function calls:

func capitalize(string: String) -> String {
  return " ".join(
    string.componentsSeparatedByString(" ")
    .map { uppercase($0.head ?? Character("")) + $0.tail }
  )
}

This implementation works, but it reveals too much how and not enough what. The code is dense and the order of operations is dictated by the semantics of the join method. What we really want is something like this:

get words -> uppercase each word’s head -> join words with a space

Let’s see what we can do. First, let’s create a new function that decomposes a string into words:

func words(string: String) -> [String] {
  return string.componentsSeparatedByString(" ")
}

It’s simple, but it clarifies our intent.

Next let’s create a new join function that better fits our domain:

func join(separator: String)(strings: [String]) -> String {
  return reduce(strings, "", { $0 + separator + $1 }).tail
}

This function is curried. A curried function accepts a single parameter and returns a function that takes the next parameter. Once all parameters are satisfied, the function is called. If we were to call our join function above, passing in a separator, we would get back a new function of type [String] -> String. If we call the returned function and pass in an array of strings, all parameters are then satisfied and the function is called. Here’s a code snippet that demonstrates this idea:

let words = ["Hello", "There"]
let joinUsingSpaces = join(separator: " ")
println(joinUsingSpaces(components: words))
// Prints "Hello There"

In join’s implementation we take the tail of our result, because an additional space is added to the beginning during the first pass of reduce.

Let’s define one last function who’s responsibility is to capitalize a single word:

func capitalizeWord(word: String) -> String {
  if let head = word.head {
    return String(uppercase(head)) + word.tail
  }
  return word
}

Finally, before we rewrite our function, let’s define a custom operator that will help us compose our functions.

infix operator >>> { associativity left }
func >>><A, B, C>(f: A -> B, g: B-> C) -> A -> C {
  return { x in
    g(f(x))
  }
}

The >>> operator takes a function from A to B, a function from B to C, and produces a function from A to C.

Now let’s rewrite our capitalize function. We’ll define our function as a composition of our existing functions:

let capitalize = words >>> { $0.map(capitalizeWord) } >>> join(separator: " ")

capitalize is now the result of composing three functions: words, an inline closure that utilizes our capitalizeWord function, and join. When composing functions it’s useful to visualize the types:

words
String -> [String]

Inline closure
[String] -> [String]

join
[String] -> String

You’ll notice that if we write the types in order, they match up. This is what allows function composition to work. Each function takes the type that the previous function returns.

The inline closure may be a bit confusing at first but it’s useful to examine its type based on where it is placed in our function composition. Since it is placed after words, it takes a String array and since it is placed before join, it must return a String array. Inside the closure is a call to the map method that exists in the Array type. The $0 is the return value of the previous function, words. We map through each element in the array and call capitalizeWord on each string, producing an array of capitalized words that we can feed into our join function.

Let’s try another example. Say we have a credit card field in our app and we need to validate that the number entered is a valid card number. When the user enters their card number, the textfield automatically formats the number like this:

"1234 5678 9123 4567"

In order to be valid, a card number must satify the following conditions:
* Card number must contain only integers
* Card number must be the correct length, where length is variable (Amex and Mastercard have different card number lengths)

In an ideal world, we would like to write something like this:
Card number contains only integers and card number is correct length

Let’s get started by defining some functions:

func isNumeric(c: Character) -> Bool {
    return c >= "1" && c <= "9"
}func isNumeric(s: String) -> Bool {
  if let head = s.head {
    if isNumeric(head) { return isNumeric(s.tail) }
    return false
  }
  return true
}

Next, we need a function that can extract an array of numbers from a string:

func digits(string: String) -> [Int] {
  if let head = string.head {
    if let digit = toInt(head) { return [digit] + digits(string.tail) }
    return digits(string.tail)
  }
  return []
}func toInt(c: Character) -> Int? {
  return String(c).toInt()
}

Now we can write a function to get the length of a card number by composing functions:

let cardLength = removeWhitespace >>> digits >>> length

Now we’re ready to implement our isValidCreditCard function:

func isValidCreditCard(validLength: Int)(cardNumber: String) -> Bool {
  if (removeWhitespace >>> isNumeric)(cardNumber) {
    return cardLength(cardNumber) == validLength
  }
  return false
}

First we check if the card number contains only integers. To do this, we compose a new function that removes all whitespace and then checks if the string passed in contains only integers. We then get the card length and compare it with the validLength parameter. By defining isValidCreditCard as a curried function, we can derive new functions that provide validation for different cards:

let isValidMasterCard = isValidCreditCard(16)
let isValidAmex = isValidCreditCard(15)

We can use these derived functions like so:

let amex = "1234 123456 12345"
let masterCard = "1234 1234 1234 1234"isValidAmex(cardNumber: amex) // true
isValidMasterCard(cardNumber: masterCard) // true

Because our composed function, (removeWhitespace >>> isNumeric), and our cardLength function both accept the same parameter, we can simplify our isValidCreditCard even further.

Let’s define a new function that takes two functions of type A -> Bool and returns a function of type A -> Bool. When we call our resulting function and pass in an A, both input functions are evaluated and the result of using && on the results is returned.

func and<A>(f: A -> Bool, g: A -> Bool) -> A -> Bool {
  return { a in
    f(a) && g(a)
  }
}

and allows us to compose our existing validation functions into a single function.

Now we can rewrite our isValidCreditCard function:

func isValidCreditCard(validLength: Int) -> (cardNumber: String) -> Bool {
  return and({cardLength($0) == validLength}, removeWhitespace >>> isNumeric)
}

The first parameter is a closure of type String -> Bool. The second is a composed function of type String -> Bool. Instead of returning a Bool indicating whether or not a card is valid, we return a new function that takes a string (the card number) and returns a Bool.

We can derive new functions, and use them the same way as before:

let isValidMasterCard = isValidCreditCard(16)
let isValidAmex = isValidCreditCard(15)let amex = "1234 123456 12345"
let masterCard = "1234 1234 1234 1234"isValidAmex(cardNumber: amex) // true
isValidMasterCard(cardNumber: masterCard) // true

Conclusion

We’ve learned how to use several concepts from functional programming such as recursion, map, filter and reduce. We’ve then used function composition to combine these functions together to create more complex functions. I hope you’ve found this post useful. If you would like a more gentle introduction to functional programming, I recommend reading some of the posts that I linked to last week. I’ve added a few more links that introduce map, filter and reduce more slowly than I’ve done here.

If you’d like to provide feedback, feel free to leave a comment below or message me on twitter at @jmecsmith. Thanks for reading! Be sure to check out the playground for this post below.

Note:

Previously this post claimed to utilize tail recursion for the implementation of uppercase, lowercase and replaceCharacter. Thanks to Fritz Anderson for pointing out that this is in fact just plain old recursion, not tail recursion. If you’d like to learn more about tail recursion, you can check out this link or read the comments below.