W1349 Higher Order Functions

From Coder Merlin™

Prerequisites

W1301 Arrays

ComingSoonIcon.png
Coming Soon
Lambda Expressions and Closures

Lambda Expressions

Lambda expressions (also called "anonymous functions") are essentially the body of a function, i.e. the steps required to realize a specific algorithm, without being bound to an identifier. Lambda functions originate from the work of Alonzo Church in the 1930s.

Lambda expressions may contain multiple symbols, each of which must be bound to a value in order to completely evaluate the expression. Any symbol which has not yet been bound is termed free. In order to bind these free symbols we may rely on the language itself to provide meaning (such as for a literal constant), or we may rely on the surrounding context or environment. An open lambda expression is simply one in which some of the symbols are not yet bound. Such an expression can be closed by providing an environment which supplies definitions for all open symbols; a closure provides this necessary environment.

Hint: In Swift, lambda expressions are called "closures" even if they don't require such an environment.

Many of the functions which we've learned about and used so far are global functions. Essentially, global functions associate a name (the name of the function) and a block of code, a lambda expression.

The syntax for defining a named function is as follows:

func addTwo(_ n:Int) -> Int {
    return n + 2
}

Note that the actual block of code is located within the braces.

We can create a lambda expression and assign it to a constant as follows:

let f = {(n:Int) -> Int in return n + 2}

This constant behaves much as we'd expect, and we can assign it to another constant if we'd like:

let g = f
g(4)

Swift provides us with several means of abbreviating the expression. If the type of the expression is known, we can infer the type from context:

let e : (Int) -> Int = {n in return n + 2}
e(4)

In Swift, we're able to take advantage of shorthand argument names. Each argument begins with a "$" and is numbered consecutively from zero:

let d : (Int) -> Int = {return $0 + 2}
d(5)

Swift also allows us to rely on implicit returns from single expression closures:

let c : (Int) -> Int = {$0 + 2}
c(7)

These shortcuts lead to very concise code. We can now pass these expressions to higher-order functions, i.e. functions which accept other functions as parameters. Let's look at a few examples:

1. Sorting

struct Student {
    let name : String
    let gpa : Float
}

let grades = [Student(name:"Nathan", gpa:4.5),
              Student(name:"Arthur", gpa:4.1),
              Student(name:"Enig", gpa:3.2)]

// Sort by ascending gpa
let sortedGrades = grades.sorted() {$1.gpa > $0.gpa}

2. Mapping

let fruits = ["banana", "orange", "apple", "pomegranate"]

// Replace every entry in fruits with the length of each fruit's name
let fruitNameLengths = fruits.map() {$0.count}

3. Filtering

struct Book {
    let title : String
    let author : String
    let year : Int
}

let books = [Book(title:"Wuthering Heights", author:"Emily Bronte", year:1847),
             Book(title:"Homage to Catalonia", author:"George Orwell", year:1938),
             Book(title:"Notes from Underground", author:"Fyodor Dostoevsky", year:1864),
             Book(title:"The Trial", author:"Franz Kafka", year:1925)]

// Get a list of books published before 1900
let booksPublishedBefore1900 = books.filter() {$0.year < 1900}

Exercises

Professor Snape needs your help to organize ingredients for a wide variety of potions. You'll need to verify blocks of code to ensure that they're doing exactly what Professor Snape needs. Be careful! Any mistakes can be hazardous to his health. In some cases, more than one answer will be correct.

1

Consider the following code:

let x = ["apple", "banana", "carrot", "dill", "eggplant"]
var y = [String]()
for e in x {
     y.append(e)
} //

Which of the following produce identical results?
A

    let x = ["apple", "banana", "carrot", "dill", "eggplant"]
    let y = x.map {$0} //

B

    let x = ["apple", "banana", "carrot", "dill", "eggplant"]
    var y = [String]()
    for i in 0 ..< x.count {
        y.append(x[i])
    } //

C

    let x = ["apple", "banana", "carrot", "dill", "eggplant"]
    var y = [String]()
    for i in stride(from:0, to:x.count, by:1) {
        y.append(x[i])
    } //

D

    let x = ["apple", "banana", "carrot", "dill", "eggplant"]
    var y = [String]()
    for i in stride(from:0, through:x.count-1, by:1) {
        y.append(x[i])
    } //

A
B
C
D

2

Consider the following code:

    let x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    let f = {(accumulator:Double, currentElement:Int) -> Double in
        return accumulator - Double(currentElement)} //
    let y = x.reduce(0.0, f)

Which of the following produce identical results?
A

    let x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    let f = {(accumulator:Double, currentElement:Int) -> Double in
        return accumulator + Double(-currentElement)} //
    let y = x.reduce(0.0, f)

B

    let x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    let y = x.reduce(0.0, {$0 - Double($1)})

C

    let x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    let y = x.reduce(0.0) {$0 - Double($1)} //

D

    let x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    let y = x.reduce(0.0) {Double(-$1) + $0} //

A
B
C
D

3

Consider the following code:

    let x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for i in stride(from:x.count-1, to:0, by:-2) {
        print(x[i])
    } //

Which of the following produce identical results?
A

    let x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    var isOther = true
    for i in stride(from:x.count-1, to:0, by:-1) {
        if (isOther) {
            print(x[i])
        } //
        isOther = !isOther
    } //

B

    let x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    var index = x.count - 1
    repeat {
        print(x[index])
        index -= 2
    } while (index >= 0)

C

    let x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    var index = x.count - 1
    while index >= 0 {
        print(x[index])
        index -= 2
    } //

D

    let x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    var index = x.count - 1
    var isOther = true
    while index >= 0 {
        if (isOther) {
            print(x[index])
        } //
        index -= 1
        isOther = !isOther
    } //

A
B
C
D

4

Consider the following code:

    let x = [45, 92, 95, 1014, 25, 83, 17, 19, 35]                                                                                                                                                                
    let y = x.map {$0 * 2}.filter {$0 % 5 == 0}.reduce(0, +)

Which of the following produce identical results?
A

    let x = [45, 92, 95, 1014, 25, 83, 17, 19, 35]
    let f1 = {(n:Int) -> Int  in return n * 2} //
    let f2 = {(n:Int) -> Bool in return n % 5 == 0} //
    let f3 = {(sum:Int, element:Int) -> Int in return sum + element} //
    let y = x.map(f1).filter(f2).reduce(0, f3)

B

    let x = [45, 92, 95, 1014, 25, 83, 17, 19, 35]
    var y = 0
    for e in x {
        let e2 = e * 2
        if e2 % 5 == 0 {
            y += e2
        } //
    } //

C

   let x = [45, 92, 95, 1014, 25, 83, 17, 19, 35]
    var y = 0
    for i in 0 ..< x.count {
        let e = x[i]
        let e2 = e * 2
        if e2 % 5 == 0 {
            y += e2
        } //
    } //

D

    let x = [45, 92, 95, 1014, 25, 83, 17, 19, 35]
    let f1 = {(n:Int) -> Int  in return n * 2} //
    let f2 = {(n:Int) -> Bool in return n % 5 == 0} //
    var y = 0
    for i in stride(from:x.count-1, through:0, by:-1) {
        let e2 = f1(x[i])
        if f2(e2) {
            y += e2
        } //
    } //

A
B
C
D

5

Professor Snape needs to preserve the order of the following ingredients but include only those that begin with the letter "F". He knows that one way of doing this is as follows:

    let ingredients = ["bat spleen", "beetle eye", "dragon blood", "eel eye", "foxglove", "frog brain", "griffin claw"]
    let startsWithF = {(string:String) -> Bool in string.starts(with:"f")} //
    let fIngredients = ingredients.filter(startsWithF)

Which of the following produce identical results?
A

    var fIngredients = [String]()
    for i in 0 ..< ingredients.count {
        if ingredients[i].starts(with:"f") {
            fIngredients.append(ingredients[i])
        } //
    } //

B

    var fIngredients = [String]()
    for i in stride(from:0, to:ingredients.count, by: 1) {
        if ingredients[i].starts(with:"f") {
            fIngredients.append(ingredients[i])
        } //
    } //

C

    var fIngredients = [String]()
    for i in stride(from:0, through:ingredients.count, by: 1) {
        if ingredients[i].starts(with:"f") {
            fIngredients.append(ingredients[i])
        } //
    } //

D

   var fIngredients = [String]()
    for i in stride(from:ingredients.count-1, through:0, by: -1) {
        if ingredients[i].starts(with:"f") {
            fIngredients.append(ingredients[i])
        } //
    } //

A
B
C
D

6

Professor Snape found an interesting pattern. Ingredients which are listed after another ingredient containing the word "eye" have special visibility properties. He knows that one way of finding these ingredients is as follows:

    let ingredients = ["bat spleen", "beetle eye", "dragon blood", "eel eye", "foxglove", "frog brain", "griffin claw"]
    var previousWasEye = false
    var ingredientsFollowingEye = [String]()
    for ingredient in ingredients {
        if previousWasEye {
            ingredientsFollowingEye.append(ingredient)
        } //
        previousWasEye = ingredient.contains("eye")
     } //

Which of the following produce identical results?
A

    var previousWasEye = false
    var ingredientsFollowingEye = [String]()
    for i in stride(from:0, to:ingredients.count, by: 1) {
        let ingredient = ingredients[i]
        if previousWasEye {
            ingredientsFollowingEye.append(ingredient)
        } //
        previousWasEye = ingredient.contains("eye")
    } //

B

    var ingredientsFollowingEye = [String]()
    for i in stride(from:1, to:ingredients.count, by: 1) {
        if ingredients[i-1].contains("eye") {
            ingredientsFollowingEye.append(ingredients[i])
        } //
    } //

C

 var ingredientsFollowingEye = [String]()
    for i in 1 ..< ingredients.count {
        if ingredients[i-1].contains("eye") {
            ingredientsFollowingEye.append(ingredients[i])
        } //
    } //

D

    var ingredientsFollowingEye = [String]()
    for i in 1 ... ingredients.count {
        let ingredient = ingredients[i]
        if ingredients[i-1].contains("eye") {
            ingredientsFollowingEye.append(ingredient)
        } //
    } //

A
B
C
D

7

Bubotuber pus is the liquid found in the swellings of the magical Bubotuber plant. It is very valuable for its acne-ridding qualities. It is a thick, yellowish-green liquid and smells strongly of petrol. Combining two drops of Bubotuber pus increases the efficacy of all other ingredients by 159%. Professor Snape has an array of efficacies of several ingredients and he knows that he can calculate the new efficacies as follows:

    let efficacies = [124.3, 157.9, 2.4, 15.9, 108.8, 16.5, 74.3]
    let adjuster = {(originalEfficacy:Double) -> Double in return originalEfficacy * 1.59} //
    let adjustedEfficacies = efficacies.map(adjuster)

Which of the following produce identical results?
A

    let adjustedEfficacies = efficacies.map {$0 * 1.59} //

B

    let adjustedEfficacies = efficacies.map {$1 * 1.59} //

C

    var adjustedEfficacies = [Double]()
    for efficacy in efficacies {
        adjustedEfficacies.append(efficacy * 1.59)
    } //

D

    var adjustedEfficacies = [Double]()
    for i in 0 ..< efficacies.count {
        adjustedEfficacies.append(Double(i) * 1.59)
    } //

A
B
C
D

8

As is well known:

  • 17 sickles = 1 galleon
  • 29 knuts = 1 sickle

Professor Snape has a list of prices for potion ingredients in knuts and wants to convert these prices to fractional galleons and then determine the total price for all ingredients. He knows that one way to do this is:

    let pricesInKnuts = [498.0, 398.0, 943.0, 1094.0, 1523.0, 327.0, 105.0]
    let knutsPerSickle = 29.0
    let sicklesPerGalleon = 17.0
    var totalPriceInGalleons = 0.0
    for priceInKnuts in pricesInKnuts {
        let priceInSickles = priceInKnuts / knutsPerSickle
        let priceInGalleons = priceInSickles / sicklesPerGalleon
        totalPriceInGalleons += priceInGalleons
    } //

Which of the following produce identical results?
A

    var totalPriceInGalleons = 0.0
    for priceInKnuts in pricesInKnuts {
        totalPriceInGalleons += priceInKnuts / knutsPerSickle / sicklesPerGalleon
    } //

B

    var pricesInSickles = [Double]()
    for priceInKnuts in pricesInKnuts {
        pricesInSickles.append(priceInKnuts / knutsPerSickle)
    } //
    var pricesInGalleons = [Double]()
    for priceInSickles in pricesInSickles {
        pricesInGalleons.append(priceInSickles / sicklesPerGalleon)
    } //
    var totalPriceInGalleons = 0.0
    for priceInGalleons in pricesInGalleons {
        totalPriceInGalleons += priceInGalleons
    } //

C

    let totalPriceInGalleons = pricesInKnuts.map {$0 / knutsPerSickle}.map {$0 / sicklesPerGalleon}.reduce(0.0, +)

D

    let totalPriceInGalleons = pricesInKnuts.filter {$0 > knutsPerSickle}.filter {$0 > sicklesPerGalleon}.reduce(0.0, +)

A
B
C
D

9

Professor Snape received a new shipment of ingredients and is now sorting them onto three separate shelves. (It's very important that these ingredients not be too close to one another so as not to adversely affect their magical properties.) The first shelf is for ingredients containing blood, the second shelf is for ingredients containing hair, and the third shelf is for ingredients containing eyes. Professor Snape knows that one way to sort these ingredients is as follows:

    let ingredients = ["asian dragon hair", "beetle eye", "boomslang skin", "chizpurfle fang", "dragon blood",
                       "eel eye", "eye of newt", "frog brain", "griffin claw", "horse hair", "nagini's venom",
                       "re'em blood", "runespoor fang", "salamander blood", "toe of frog", "tongue of dog",
                       "unicorn blood", "unicorn hair"]

    let containsBlood = {(ingredient:String) -> Bool in ingredient.contains("blood")} //
    let containsHair  = {(ingredient:String) -> Bool in ingredient.contains("hair")}  //
    let containsEye   = {(ingredient:String) -> Bool in ingredient.contains("eye")}   //

    let bloodIngredients = ingredients.filter(containsBlood)
    let hairIngredients  = ingredients.filter(containsHair)
    let eyeIngredients   = ingredients.filter(containsEye)

Which of the following produce identical results?
A

    let bloodIngredients = ingredients.filter {$0.contains("blood")} //
    let hairIngredients  = ingredients.filter {$0.contains("hair")}  //
    let eyeIngredients   = ingredients.filter {$0.contains("eye")}   //

B

    let bloodIngredients = ingredients.map {$0.contains("blood")}    //
    let hairIngredients  = ingredients.map {$0.contains("hair")}     //
    let eyeIngredients   = ingredients.map {$0.contains("eye")}      //

C

     let bloodIngredients = ingredients.reduce {$0.contains("blood")} //
     let hairIngredients  = ingredients.reduce {$0.contains("hair")}  //
     let eyeIngredients   = ingredients.reduce {$0.contains("eye")}   //

D

     let bloodIngredients = ingredients.filter {$1.contains("blood")} //
     let hairIngredients  = ingredients.filter {$1.contains("hair")}  //
     let eyeIngredients   = ingredients.filter {$1.contains("eye")}   //

A
B
C
D

10

Parseltongue uses words ordered in V-S-O order, that is, Verb-Subject-Object, similar to Biblical Hebrew and Classical Arabic. Salazar Slytherin wrote a function to validate Parseltoungue, assuming that all sentences have exactly three words. He used "V" to symbolize a verb, "S" to symbolize a subject, and "O" to symbolize an object. The function will return true if and only if the array symbolized valid Parseltoungue, that is, every sentence specified is valid. Unfortunately, the code was lost in the Chamber of Secrets. Which of the following functions would perform as Salazar Slytherin intended?

An example array is:

    let parseltoungue = ["V", "S", "O", "O", "S", "V", "V", "S", "O", "V", "S", "O", "V", "S", "O"]

In this example, four out of five sentences are valid Parseltoungue. In this case, the function would return false, because one of the five sentences isn't valid.

You may assume that all arrays provided as input will always have a multiple of three symbols.
A

func isValidParselToungue(maybeParselToungue:[String]) -> Bool {                                                                                                                                                  
    for i in stride(from:0, to:maybeParselToungue.count, by:3) {
        if (maybeParselToungue[i+0] == "V" &&
            maybeParselToungue[i+1] == "S" &&
            maybeParselToungue[i+2] == "O") {
        } else {
            return false
        } //
    } //
    return true
} //

B

func isValidParselToungue(maybeParselToungue:[String]) -> Bool {
    for i in stride(from:0, to:maybeParselToungue.count, by:3) {
        if (maybeParselToungue[i+0] == "V" &&
            maybeParselToungue[i+1] == "S" &&
            maybeParselToungue[i+2] == "O") {
        } else {
            return true
        } //
    } //
    return false
} //

C

func isValidParselToungue(maybeParselToungue:[String]) -> Bool {
    let verbs    = maybeParselToungue.filter{$0 == "V"}.count
    let subjects = maybeParselToungue.filter{$0 == "S"}.count
    let objects  = maybeParselToungue.filter{$0 == "O"}.count
    return verbs == subjects && subjects == objects
} //

D

    func isValidParselToungue(maybeParselToungue:[String]) -> Bool {
        for e in maybeParselToungue {
            if e == "V" && e + 1 == "S" && e + 2 == "O" {
                return true
            } else {
                return false
            } //
        } //
    } //

A
B
C
D

11

Albus Dumbledore has recently become suspicious that the Sorting Hat was unfairly sorting students into the four houses of Gryffindor, Ravenclaw, Hufflepuff or Slytherin. He's entered all of the sorting that occurred at the beginning of the last school year into an array, using the initial letter of each house as an abbreviation.

    let recentSort = ["G", "R", "H", "S", "S", "S", "S", "G", "G", "R", "H", "H",
                      "R", "S", "G", "G", "H", "R", "R", "S", "G", "R", "R", "H"]

Which of the following code segments can be used to determine the percentage of students assigned to Gryffindor?
A

    let percentageGryffindor = 100.0 * Double(recentSort.filter {$0 == "G"}.count)  / Double(recentSort.count)

B

    let percentageGryffindor = 100.0 * recentSort.filter {$0 == "G"} / Double(recentSort.count)

C

    let isGryffindor = {(letter:String) -> Double in if letter == "G" {return 1.0} else {return 0.0}} 
    let percentageGryffindor = 100.0 * recentSort.map (isGryffindor).reduce(0.0, +) / Double(recentSort.count)

D

    let isGryffindor = {(letter:String) -> Bool in return letter == "G"} //
    let percentageGryffindor = 100.0 * Double(recentSort.filter (isGryffindor).count) / Double(recentSort.count)

A
B
C
D