Higher-order functions

Function `printList1` to print each element of an integer list

def printList1(xs: List[Int]) : Unit =
  // for-comprehension
  // for x <- xs do println(x)

  // iterative loop
  // var current = xs
  // while current != Nil do
  //   println(current.head)
  //   current = current.tail
  // end while

  // recursive
  xs match
    case Nil => ()
    case y :: ys =>
      println(y)
      printList1(ys)
  end match
end printList1

Function `printList2` to print each element of an integer list with a prefix

def printList2(xs: List[Int]) : Unit =
  xs match
    case Nil => ()
    case y :: ys =>
      println("x = " + y)
      printList2(ys)
  end match
end printList2

The functions printList1 and printList2 duplicate the entire list traversal code and differ only in their way of processing an element. Reducing such code duplication helps building clean, elegant, and maintanable code. The following generalization attempt adds a function argument that lets us select an implementation.

def printList3(xs: List[Int], how: String) : Unit =
  // poor maintenance: changing how to print requires extending printList3
  xs match
    case Nil => ()
    case y :: ys =>
      if how == "verbatim" then println(y)
      else if how == "prefixed" then println("x = " + y)
      else if how == "incremented" then println(y+1)
      else throw RuntimeException("Unknown option " + how)
      printList3(ys, how)
end printList3

The downside of this approach is poor maintanability: whenever a function client needs a new feature, we need to extend the function printList3. If only we could pass functions as arguments…

Generalize to a higher-order function `foreach`

Functional programming languages allow us to pass functions as arguments. We use this feature to generalize printList1 and printList2 into a single higher-order function foreach, which works for any type of list (not just integer lists).

def foreach [X] (xs: List[X], f: X=>Unit) : Unit =
  xs match
    case Nil => ()
    case y :: ys =>
      f(y)
      foreach(ys, f)
end foreach

Function foreach traverses any list and applies a compatible function to each element. Below, we traverse a list of strings List[String], which means that we must provide as a second argument a function that accepts a String.

foreach(List("a", "b", "c"), (x: String) => println("Hello, " + x))

We can now implement printList1 and printList2 in terms of the higher-order function foreach:

def printList1(xs: List[Int]) : Unit =
  // foreach(xs, (x:Int) => println(x))
  foreach(xs, println)
end printList1

def printList2(xs: List[Int]) : Unit =
  foreach(xs, x => println("x = " + x))
end printList2

Higher-order function `map` that applies a function to each element of a list and returns a new list

def map [X,Y] (xs: List[X], f: X=>Y) : List[Y] =
  xs match
    case Nil => Nil
    case y :: ys =>
      // val result: Y = f(y)
      // val listResult: List[Y] = map(ys, f)
      // result :: listResult
      f(y) :: map(ys, f)
end map

Here are some examples of using map: - increment each element of a list of integers, - turn each element of a list of integers into a string, - collect the lengths of a list of lists of strings, - variations of multiplying each element by ten.

val xs = List(1,2,3)
val incremented: List[Int] = map(xs, (x: Int) => x+1)
val printed: List[String] = map(xs, (x: Int) => "x = " + x)

val xss = List(List("a", "b", "c"), Nil, List("d", "e"))
val lengths: List[Int] = map(xss, (xs: List[String]) => xs.length)

def timesTen(x: Int) = x*10

// pass a named function
val timesTenList1 = map(xs, timesTen)

// pass an anonymous function, explicit argument name and type
val timesTenList2 = map(xs, (x: Int) => x*10)

// pass an anonymous function, explicit argument name
val timesTenList3 = map(xs, x => x*10)

// pass an anonymous function, argument is identified by position in body
val timesTenList4 = map(xs, _ * 10)

// pass a more complicated anonymous function
val timesTenList5 = map(xs, (x: Int) => {
  val timesTwo = x+x
  val timesThree = timesTwo + x
  timesThree + 7*x
})

Higher-order function `filter` that returns a new list containing only the elements that satisfy a given predicate function

def filter [X] (xs: List[X], f: X=>Boolean) : List[X] =
  xs match
    case Nil => Nil
    // case y :: ys =>
    //   if f(y) then y :: filter(ys, f)
    //   else filter(ys, f)
    case y :: ys if f(y) => y :: filter(ys, f)
    case _ :: ys         => filter(ys, f)      
end filter

Function types

// a type for functions that take multiple arguments and return a list of string
type Fn = (Int, String) => List[String]
// a function of the above type that takes arguments x,y and arranges their string representations into a list
val f: Fn = (x, y) => x.toString :: y :: Nil
f(1, "hello")

Higher-order function `fold` to aggregate elements

Compute the sum of the elements of a list:

def sum(xs: List[Int]) : Int =
  xs match
    case Nil     => 0
    case y :: ys => y + sum(ys)
  end match
  foldRight(xs, 0, _ + _)
end sum

Compute the product of the elements of a list:

def product(xs: List[Int]) : Int =
  xs match
    case Nil     => 1
    case y :: ys => y * product(ys)
  end match  
end product

Functions sum and product share many, but differ in their base element (0 vs 1) and in their aggregation function (+ vs *). We generalize these elements using additional arguments:

def foldRight [X,Y] (xs: List[X], z: Y, f: (X,Y)=>Y) : Y =
  xs match
    case Nil     => z // 0 vs. 1
    case y :: ys => f(y, product(ys)) // * vs. +
  end match
end foldRight

val s: Int = foldRight(List(1,2,3), 0, _ + _) // 6
val listString: String = 
  foldRight(List(1,2,3), "!", (x:Int,y:String) => x.toString + y) // "123!"

Now we can implement sum and product using foldRight:

def sum(xs: List[Int]) : Int =
  foldRight(xs, 0, _ + _)
end sum

def product(xs: List[Int]) : Int =
  foldRight(xs, 1, _ * _)
end product

A tail-recursive way of aggregating elements from the left:

def foldLeft [X,Y] (xs: List[X], z: Y, f: (X,Y)=>Y) : Y =
  xs match
    case Nil     => z // 0 vs. 1
    case y :: ys => foldLeft(ys, f(y, z), f)
  end match
end foldLeft

val listString2: String =
  foldLeft(List(1,2,3), "!", (x:Int,y:String) = y + x.toString) // "!123"

Examples

// or: true if at least one element is true, false if all elements are false
// and: false if at least one element is false, true if all elements are true
// Boolean disjunction: ||
// Boolean conjunction: &&
def or          (xs: List[Boolean]) : Boolean = foldLeft(xs, false, _ || _)
def and         (xs: List[Boolean]) : Boolean = foldLeft(xs, true, _ && _)

// xs ::: ys
def append  [X] (xs: List[X])(ys: List[X]) : List[X] = foldRight(xs, ys, _ :: _)

Functions and Methods

Methods belong to objects or classes:

object Methods:
  def add(x: Int, y: Int) : Int =
    x + y
  end add
end Methods

They require a name, argument names and types, and have a return type that can often be inferred (required for recursive methods). Functions, in contrast, can be defined in any context:

// add 2 numbers
val add: (Int,Int)=>Int = 
  (x: Int, y: Int) => x + y
// concatenate 3 numbers into a string
val add3: (Int,Int,Int)=>String = 
  // "Hello: " + x.toString + " + " + y.toString + " + " + z.toString
  (x: Int, y: Int, z: Int) => s"Hello: $x + $y + $z"

Infer argument types:

val add21: (Int,Int)=>Int = 
  (x, y) => x + y

Omit argument names:

val add22: (Int,Int)=>Int   = _ + _ // add 2 ints
val f: (String,Int)=>String = _ + _ // append to a string

add22(1,2) // 3
f("1",2)   // "12"

Inline argument types:

val add23 = (_: Int) + (_: Int)

Methods can be converted to functions:

Methods.add(1,2)
val addf /*: (Int,Int)=>Int */ = Methods.add

Curried definitions separate a single argument list into multiple argument lists:

// tupled definitions
val add2fn: (Int,Int)=>Int = _ + _
val add3fn: (Int,Int,Int)=>Int = _ + _ + _

// curried definitions
val add2curried: Int => (Int => Int) =
  (x: Int) => {
    (y: Int) => x + y
  }

add2fn(1,2) == add2curried(1)(2)

Partial function application:

val add17 = add2curried(17)
add17(5)
add17(10)
add17(13)

// add2fn: (Int,Int) => Int
val add13: Int=>Int = add2fn(13, _)
add13(4)
add13(8)
add13(12)

Some functional languages omit () in curried function calls:

add(1)(2)
add 1 2

Partial function application can use wildcard operator _:

val fn(x:Int, y: String, z: List[Double]) => Boolean = ???
val fn2: (String,List[Double]) => Boolean = weird(x=2, y=_, z=_)
val fn3: String => Boolean = weird2(_, List(1.0))

Syntactic conventions (e.g., name of method apply can be omitted) allows us to mimic functions using object-oriented programming:

val fn = new Function[(Int,Int),Int] {
  def apply(x: Int, y:Int) : Int = x+y
}
fn.apply(1,2)
fn(1,2) // fn.apply(1,2)

Higher-order functions

Function printList1 to print each element of an integer list

Function printList2 to print each element of an integer list with a prefix

Generalize to a higher-order function foreach

Higher-order function map that applies a function to each element of a list and returns a new list

Higher-order function filter that returns a new list containing only the elements that satisfy a given predicate function