101.02 - Higher Order Functions

Higher Order Functions

  • Functions are first-class values:
    • they can be passed as function parameters
    • they can be return as function results
  • Higher order functions:
    • take other functions as parameters
    • or return other functions as results
  • First order functions:
    • take regular data types as parameters
    • return regular data types as results
def sumInts(a: Int, b: Int) : Int =
  if (a > b) 0 else a + sumInts(a+1, b)

def cube(x: Int): Int = x * x * x

def sumCubes(a: Int, b: Int): Int = 
  if (a > b) 0 else cube(a) + sumCubes(a+1, b)

def fact(x: Int): Int = 
  if (x = 0) 1 else x * fact(x-1)

def sumFactorials(a: Int, b: Int): Int = 
  if (a > b) 0 else fact(a) + sumFactorials(a+1, b)

All the above are special cases of the following: $$ \sum_{n=a}^ b f(n) $$

First refinement:

def sum(f: Int => Int, a: Int, b: Int) =
  if (a > b) 0 else f(a) + sum(f, a+1, b)

def sumInts(a: Int, b: Int) = sum(id, a, b)
def sumCubes(a: Int, b: Int) = sum(cube, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)

def id(x: Int): Int = x
def cube(x: Int): Int = x * x * x
def fact(x: Int): Int = if (x = 0) 1 else x * fact(x-1)

Second refinement, using anonymous functions (literals):

def sum(f: Int => Int, a: Int, b: Int) =
  if (a > b) 0 else f(a) + sum(f, a+1, b)

def sumInts(a: Int, b: Int) = sum(x => x, a, b)
def sumCubes(a: Int, b: Int) = sum(x => x * x * x, a, b)
def sumFactorials(a: Int, b: Int) 
   = sum(x => {if (x = 0) 1 else x * fact(x-1)}, a, b)

Writing the sum function again as a tail recursive function:

def sum(f: Int => Int, a: Int, b: Int): Int = {
  def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, acc + f(a))
  }
  loop(a, 0)
}

Currying

All three functions above pass a and b as parameters, which is redundant. Third refinement:

def sum(f: Int => Int): (Int, Int) => Int = {
  def sumF(a: Int, b: Int): Int = 
    if (a > b) 0 else f(a) + sumF(a + 1, b)
  sumF
}

def sumInts(a: Int, b: Int) = sum(x => x)
def sumCubes(a: Int, b: Int) = sum(x => x * x * x)
def sumFactorials(a: Int, b: Int) 
   = sum(x => {if (x = 0) 1 else x * fact(x-1)})

sumCubes(1, 10)
sum(x => x * x * x) (1, 10)

sum is a function that takes the "operator" function as a parameter and returns the "summing" function. Note: sum is like a "custom" function builder.

sum(cube)(1,10)

is the same as:

(sum(cube))(1,10)

(sum(cube)) is a function and 1 and 10 are the arguments

Fourth refinement (syntactic sugar):

def sum(f: Int => Int) (a: Int, b:Int): Int =
  if (a > b) 0 else f(a) + sum(f)(a + 1, b)

Advantage: you can write

sum(cube)

and apply the parameters at a later stage (which wasn't possible with the earlier iterations).

Example:

def product(f: Int => Int)(a: Int, b: Int) = 
  if (a > b) 1 else f(a) * product(f)(a + 1, b)

Factorial expressed as a product:

def factorial(n: Int): Int = product(x => x)(1, n)

A more general function (than sum or product) leads to a version of map-reduce:

def mapReduce(f: Int => Int, 
              combine: (Int, Int) => Int, zero: Int)(a: Int, b: Int): Int = 
 if(a > b) zero else combine(f(a), mapReduce(f, combine)(a + 1, b))

combine is a general form of the inline + and *** functions (operators) and zero** is the unit value.

Scala syntax summary

Types:

  • numeric: Int, Double, Float, Long, etc
  • Boolean: true or false
  • String
  • function: Int => Int or (Int, Int) => Int

Expressions:

  • identifier: x or factorial
  • literal: 0 or 1.0 or "abc"
  • function application: sqrt(x)
  • operator: -x or y + x
  • selection: math.abs
  • conditional expression: if (x < 0) -x else x
  • block: {val x = math.abs(y); x * 2}
  • anoymous function: x => x + 1

Definitions:

  • function definition: def square(x: Int): Int = x*x
  • value definition: val y = square(2)

Parameters:

  • call-by-value parameter: (x: Int)
  • call-by-name parameter: (x: => Double)

Identifiers:

  • alphanumeric: starting with a letter
  • symbolic: starting with a symbol
  • underscore: underscore counts as a letter

Examples of identifiers:

  • x1
  • *
  • +?%&
  • vector_++
  • counter_=

Operator precedence:

  • (all letters)
  • |
  • ^
  • &
  • < >
  • = !
  • :
  • + -
  • * / %
  • (any other)

Functions and data = classes

class Rational(x: Int, y: Int) {
  def numer = x
  def denom = y
}
new Rational(1, 2)

This definition introduces:

  • a new type, named Rational
  • a constructor named Rational for this type

Scala uses different namespaces for types and values, therefore there is no collision.