Higher Order Functions (in Swift & Python etc)

Higher-Order Functions are functions that can take one or more functions as arguments, these functions may also return functions. in other words they take one or more functions as arguments (i.e. procedural parameters), and/or returns a function as their results. Functions that are not higher-order functions are called first-order functions.

For programmers, the first instances of Higher-Order Functions were seen in Functional programming languages like Erlang and were not originally found in so-called “pure” programming languages such as the older version of Java.

These days, however, we increasingly see Higher-Order Functions used in so-called “mixed” programming languages that introduce functional elements to previously non-functional language contexts.

This article will focus on using Higher-Order functions in programming, for the theory see my article on lambda calculus.

To elaborate on this further, we pass in functions to higher-order functions in the form of lambda-expressions which are called lambdas in python and closures in Swift (in Swift functions are closures). Higher-Order functions could be replaceable with first-order functions with recursion, yet the use of higher-order functions can be more expressive, and it can also reduce the need for recursion in our code (Ref#: J). Whilst an exploration of the lambda calculus will give you more of a theoretical understanding of this topic, this article will instead focus on use cases in programming languages (Ref#: H).

Higher-Order Functions can also be used to create “partial applications” of functions, or an application of a function to a particular subset of its arguments (Ref#: J).

Functions which take Functions as Arguments

Here is a Python example of using a function which takes a function as an argument:

def second_element(nums):
    return nums[1]

def summation(nums):
    return sum(nums)

def main(f, *args): # main takes a function as an argument
    result = f(*args)
    print(result)

if __name__ == "__main__": 
    main(summation, [1, 2, 3]) # main prints 6 
    main(second_element, [1, 2, 3]) # prints 2

def second_element(nums):

return nums[1]

def summation(nums):

return sum(nums)

def main(f, *args): # main takes a function as an argument

result = f(*args)

print(result)

if __name__ == "__main__":

main(summation, [1, 2, 3]) # main prints 6

main(second_element, [1, 2, 3]) # prints 2

Function Composition

Higher-Order Functions allow us to compose functions, this allows us to build together smaller functions to make larger functions. In other words composition “takes two functions as input and returns (evaluates to) a function which is their composition” (Ref#: J).

In Python this might look like:

# the "twice" function applies a function passed into it twice
def twice(f):
    return lambda x: f(f(x))
# this function adds 10 to a given value x
def plusten(x):
    return x + 10
# create a composition function using 'twice' and 'plusten'
together = twice(plusten)
print (together(5))

# the "twice" function applies a function passed into it twice

def twice(f):

return lambda x: f(f(x))

# this function adds 10 to a given value x

def plusten(x):

return x + 10

# create a composition function using 'twice' and 'plusten'

together = twice(plusten)

print (together(5))

To achieve function composition in swift, it’s easier if we add something extra to the language to help us, like this:

import UIKit

/// Define a precedence group so Swift can work out which operators take priority. The compiler will use
/// rules for operator precedence and associativity to resolve an expression into a single value.
precedencegroup CompositionPrecedence {
    associativity: left
}

/// Infix notation is the notation commonly used in arithmetical and logical formulae and statements.
/// It is characterized by the placement of operators between operands. Here we define a new infix
/// operator to use to enable function composition.
infix operator >>>: CompositionPrecedence

/// Compose functions
public func >>><T, U, V>(
    f: @escaping (T) -> U,
    g: @escaping (U) -> V
    ) -> ((T) -> V) {
    return { g(f($0)) }
}

private func twice (f: Int) -> Int {
    return f * 2
}

private func plusten(x: Int) -> Int {
    return x + 10
}

let together = twice >>> plusten

print (together(10))                   // 30

import UIKit

/// Define a precedence group so Swift can work out which operators take priority. The compiler will use

/// rules for operator precedence and associativity to resolve an expression into a single value.

precedencegroup CompositionPrecedence {

associativity: left

}

/// Infix notation is the notation commonly used in arithmetical and logical formulae and statements.

/// It is characterized by the placement of operators between operands. Here we define a new infix

/// operator to use to enable function composition.

infix operator >>>: CompositionPrecedence

/// Compose functions

public func >>><T, U, V>(

f: @escaping (T) -> U,

g: @escaping (U) -> V

) -> ((T) -> V) {

return { g(f($0)) }

}

private func twice (f: Int) -> Int {

return f * 2

}

private func plusten(x: Int) -> Int {

return x + 10

}

let together = twice >>> plusten

print (together(10)) // 30

Map, Filter, and Reduce

Map, Filter, and Reduce (and compactMap / flatMap) are pre-defined higher-order functions which can be really useful tools for working with collections (such as lists and other collection types like the “ArrayList” in Java or “Array” in Swift). There are quite a few programming languages that now have these built-in, including JavaScript, Python, Java 8 (which introduced language-level support for Lambda Expressions), and indeed Swift.

This provision by libraries of pre-defined functions like map is important to distinguish from the option of defining one’s own higher-order functions, but to do this the language needs support for the functional elements covered above.

Let’s explore what these functions are used for, and the benefits of each. The functions we shall talk about facilitate a so-called functional approach to programming.

Map

“Use map to loop over a collection and apply the same operation to each element in the collection.”

To explore the benefits of map, let us look at some examples. As we mentioned in the intro, the way we often use map is through the use of lambdas (aka lambda abstractions/blocks/closures/anonymous functions).

Looking at a real-world example which could be indeed useful, imagine you have a weather app: the source temperatures are in Fahrenheit but you want the app to work for European customers who expect their temperatures to be displayed to them in Celsius. One can apply map, using Python, to this situation as follows:

fahrenheit = [100, 120, 90]
celsius = list(map(lambda x: (float(5)/9)*(x-32), fahrenheit))
print (celsius)

fahrenheit = [100, 120, 90]

celsius = list(map(lambda x: (float(5)/9)*(x-32), fahrenheit))

print (celsius)

This would output temperatures as:

[37.77777777777778, 48.88888888888889, 32.22222222222222]

Similarly, in Swift you might do something like:

let fahrenheit = []

let celsius = fahrenheit.map({
  (value: Int) -> Float in
  return ((Float(5)/9) * Float(Float(value - 32))
})
// [37.77778, 48.88889, 32.22223]

let fahrenheit = []

let celsius = fahrenheit.map({

(value: Int) -> Float in

return ((Float(5)/9) * Float(Float(value - 32))

})

// [37.77778, 48.88889, 32.22223]

Whilst we might choose to round these down for display, we now have equivalent values in the alternative representational format. Essentially the map function has taken an anonymous function as an argument and it has proceeded to iterate over the input values and apply this function to each, in turn, creating then the output.

Similarly, we can also do something like this in Swift to get the square values for an array of values:

// square all elements of an array using map
let values = [2.0, 3.0, 5.0, 8.0]
let squares = values.map {$0 * $0}
print(squares) // [4.0, 9.0, 25.0, 64.0]

// square all elements of an array using map

let values = [2.0, 3.0, 5.0, 8.0]

let squares = values.map {$0 * $0}

print(squares) // [4.0, 9.0, 25.0, 64.0]

CompactMap

The keyword .compactMap is used in Swift is used to flatten a collection of collections, and it can even deal with optionals and thus useful where a particular sub-collection could be nil. Or in other words, it “returns an array containing the non-nil results of calling the given transformation with each element of this sequence”.

Example

let scoresA = ["1", "2", "three", "four", "5"]
let compactMapped: [Int] = scoresA.compactMap { str in Int(str) }
// gives [1, 2, 5] - The nil values for "three" and "four" are filtered out.

// Another example
let names: [String?] = ["Tom", nil, "Peter", nil, "Harry"]
let valid = names.compactMap { $0 }
// ["Tom", "Peter", "Harry"]

// Third example
let words = ["53", "nine", "hello","0"]
let values = words.compactMap { Int($0) }
// Returns [Int] // [53, 0]

// BUT: FlatMap is still used to flatten an array of arrays into a single collection
let scoresB = [[5,2,7], [4,8], [9,1,3]]
let allScores = scoresB.flatMap { $0 }
print (allScores) // [5, 2, 7, 4, 8, 9, 1, 3]

let scoresA = ["1", "2", "three", "four", "5"]

let compactMapped: [Int] = scoresA.compactMap { str in Int(str) }

// gives [1, 2, 5] - The nil values for "three" and "four" are filtered out.

// Another example

let names: [String?] = ["Tom", nil, "Peter", nil, "Harry"]

let valid = names.compactMap { $0 }

// ["Tom", "Peter", "Harry"]

// Third example

let words = ["53", "nine", "hello","0"]

let values = words.compactMap { Int($0) }

// Returns [Int] // [53, 0]

// BUT: FlatMap is still used to flatten an array of arrays into a single collection

let scoresB = [[5,2,7], [4,8], [9,1,3]]

let allScores = scoresB.flatMap { $0 }

print (allScores) // [5, 2, 7, 4, 8, 9, 1, 3]

Sources: https://useyourloaf.com/blog/replacing-flatmap-with-compactmap/

https://www.avanderlee.com/swift/compactmap-flatmap-differences-explained/

Filter

Use filter to loop over a collection and return an Array containing only those elements that match an include condition.

Let’s explore how we achieve this in code using Swift:

let integerArray = [1, 4, 10, 15]

// 1. The old way using a for loop
var evenInts = [Int]()
for anInt in integerArray {
    if (anInt % 2 == 0) {
        evenInts.append(anInt)
    }
}
print (eventInts)

// 2. ...but it's so much simpler using filter
let even = integerArray.filter { $0 % 2 == 0 }
print(even)

let integerArray = [1, 4, 10, 15]

// 1. The old way using a for loop

var evenInts = [Int]()

for anInt in integerArray {

if (anInt % 2 == 0) {

evenInts.append(anInt)

}

print (eventInts)

// 2. ...but it's so much simpler using filter

let even = integerArray.filter { $0 % 2 == 0 }

print(even)

Above, we look to create an array with the non-even numbers filters out. Part 1 shows the naive way of doing this using a for loop, whereas part 2 shows the much simpler syntax of using filter. We pass a closure (an anonymous function) to the filter function, and when doing this we use the placeholder “$0” to denote each element and we use the modulus operator (“%”) to check whether each int is divisible by 2, if so it’s kept. What’s going on under the hood here is that the closure is returning a boolean (true/false) value and where this is true the element (denoted by $0) is kept in, and where false it is left out.

We can equally do something similar in Python:

integer_list = [1, 4, 10, 15]
 
def even_numbers(the_ints):
  even_ints = []
  for number in the_ints:
      if number % 2 == 0:
          even_ints.append(number)
  return even_ints
 
print (even_numbers(integer_list)) # [4, 10]
 
# Or in a single line of code !
print (list(filter(lambda x: x % 2 == 0, integer_list))) # [4, 10]

integer_list = [1, 4, 10, 15]

def even_numbers(the_ints):

even_ints = []

for number in the_ints:

if number % 2 == 0:

even_ints.append(number)

return even_ints

print (even_numbers(integer_list)) # [4, 10]

# Or in a single line of code !

print (list(filter(lambda x: x % 2 == 0, integer_list))) # [4, 10]

Now we can also do something (kinda) similar in Java 8 using streams:

package com.somepackage;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
  public static void main (String[] args) {
    List<Integer> numbers = Arrays.asList(1, 4, 10, 15);
    List<Integer> result2 = numbers.stream() // convert list to stream
      .filter(num -> (num%2 ==0))            // only results divisible by 0
      .collect(Collectors.toList());
    result2.forEach(System.out::println);    // output: 4 10
    
  }
}

package com.somepackage;

import java.util.Arrays;

import java.util.List;

import java.util.stream.Collectors;

public class Main {

public static void main (String[] args) {

List<Integer> numbers = Arrays.asList(1, 4, 10, 15);

List<Integer> result2 = numbers.stream() // convert list to stream

.filter(num -> (num%2 ==0)) // only results divisible by 0

.collect(Collectors.toList());

result2.forEach(System.out::println); // output: 4 10

}

Reduce

The reduce function returns the result of combining the elements of the sequence using the given closure.

Let look at implementing reduce in Swift:

let numbers = [1, 2, 3, 4]

let numberSum = numbers.reduce(0, { x, y in
    x + y
})
// numberSum == 10

// Or in a single line you could do this, although this might less redable:

let singleLineNumSim = numbers.reduce(0, +)

//singleLineNumSim = 10

let numbers = [1, 2, 3, 4]

let numberSum = numbers.reduce(0, { x, y in

x + y

})

// numberSum == 10

// Or in a single line you could do this, although this might less redable:

let singleLineNumSim = numbers.reduce(0, +)

//singleLineNumSim = 10

Above we have combined all the numbers in an array of Ints to a single number, but instead of using a loop to do this or a static expression, we have used reduce.

In Python 3 (as opposed to Python 2) we now need to import this from the functools module to use the reduce function, as the language creator has said that using reduce for combining items in a collection is not his preferred syntax, as he believed that doing it explicitly in code is more readable, and thus that using higher-order function based solution is unnecessary.

#!/bin/python3
from functools import reduce

list = [1, 2, 3, 4, 5]
multiplier = lambda x, y: x * y
adder = lambda x, y: x + y

print (reduce(multiplier, list)) # 120
print (reduce(adder, list))      # 15

#!/bin/python3

from functools import reduce

list = [1, 2, 3, 4, 5]

multiplier = lambda x, y: x * y

adder = lambda x, y: x + y

print (reduce(multiplier, list)) # 120

print (reduce(adder, list)) # 15

Sorted

One extra build-in higher-order function in Swift is called “sorted” and is used to sort arrays in very few lines of code, or just a single line, like this:

// 1.
let array = [1, 5, 6, 12, 2, 0, 3, 4]
// 2.
let newArray = array.sorted(by: {S0 < $1})
// 3.
print (newArray)                     // [0, 1, 2, 3, 4, 5, 6, 12]
// 4.
let anotherArray = ["Left", "Blue", "Size", "Depends", "life"]
// 5. 
print (anotherArray.sorted(by: <))   // ["Blue", "Depends", "Left", "Size", "life"]

// 1.

let array = [1, 5, 6, 12, 2, 0, 3, 4]

// 2.

let newArray = array.sorted(by: {S0 < $1})

// 3.

print (newArray) // [0, 1, 2, 3, 4, 5, 6, 12]

// 4.

let anotherArray = ["Left", "Blue", "Size", "Depends", "life"]

// 5.

print (anotherArray.sorted(by: <)) // ["Blue", "Depends", "Left", "Size", "life"]

In the above we can see that we pass our sorting rule in as a closure such as {$0 < $1}, and swift also gives some interesting short-hand options for our sorting rules such as in section 5 above where we just say sorted(by: <) and Swift will actually infer what we mean.

Conclusion

In conclusion, we have seen what higher-order functions are and how we could use these in mixed programming languages. The use of higher-order functions where this is not the only way of coding a solution is controversial as some see it as unnecessary, but yet it’s good to know about this stuff and be able to read code using higher-order functions, and code solutions this way where appropriate.

References

A: [Socratica]. (2017, Sep 18). Map, Filter, and Reduce Functions || Python Tutorial || Learn Python Programming. Retrieved from”https://goo.gl/hgox2X”.

B: https://www.sitepoint.com/java-8-streams-filter-map-reduce/

C: http://web.mit.edu/6.005/www/fa15/classes/25-map-filter-reduce/

D: http://www.java67.com/2016/09/map-reduce-example-java8.html

E: https://useyourloaf.com/blog/swift-guide-to-map-filter-reduce/

F: https://www.youtube.com/watch?v=fbYMaJciMZY

G: https://www.tutorialspoint.com/java8/java8_streams.htm

H: https://en.wikipedia.org/wiki/Higher-order_function

I: https://clojure.org/guides/higher_order_functions

J: Craig, I. (2001). The Interpretation of Object-Oriented Programming Languages.

K: Cesarini, F. & Thompson, S. (2009). Erlang Programming: A Concurrent Approach to Software Development. O’Reilly Media, CA, USA.

L: 1.6 Higher-Order Functions. Retrived from: http://composingprograms.com/pages/16-higher-order-functions.html

M: Higher Order Functions and Decorators. Retrieved from: https://www.hackerearth.com/practice/python/functional-programming/higher-order-functions-and-decorators/tutorial/

N: Higher Order Functions In Xcode 8 (Swift 3) – Part 1/2. https://www.youtube.com/watch?v=p5-UFGO5e_0

O: Non-escaping error when implementing Church Numerals in Swift 3. Retrieved from: https://stackoverflow.com/questions/39810705/non-escaping-error-when-implementing-church-numerals-in-swift-3

P*: Functional Snippet #2: Function Composition. Retrieved from: https://www.objc.io/blog/2014/10/13/functional-snippet-2-function-composition/

Q: https://www.python-course.eu/python3_lambda.php

R: LAMBDA Functions: Powerful And Elegant Abstractions. Retrieved from: https://www.youtube.com/watch?v=OLH3L285EiY

S: https://www.youtube.com/watch?v=wB-bi8_rSLs