All Articles

Higher Order Functions

Intro

A higher order function is a function for whom at least one of the following statements is true:

  1. It returns a function
  2. At least one of its arguments is itself a function

Functions with arguments which are themselves functions are typically called functionals.

Recall from the previous post that the output of the curry of a function is itself a function. The curry of a function is therefore a higher-order-function.

The examples below demonstrate the case where the argument of the function is a function. Namely, the function takes itself as an argument and outputs the composition of itself with itself.

Haskell

main :: IO ()
twice :: (Int -> Int) -> (Int -> Int)
twice f = f . f -- note that . is the composition operator
f :: Int -> Int
f x = 2 * x
main = print (twice f 1) -- 4

Scala

  def twice(f: Int => Int) = f compose f
  def f(x: Int): Int = 2 * x
  println(twice(f)(1))	// 4

map

One of the most important examples of a higher-order-function is the map function. The map function is a binary function. It takes as its arguments a list xx and a function ff and returns a new list yy such that yi=f(xi)y_i = f(x_i).

map f [x1, ... ,xn] == [f x1, ... ,f xn]

Haskell

scale xs factor = map f xs
  where f x = factor * x

main :: IO ()
main = print(scale [1,2,3] 2) -- [2,4,6]

Scala

  def scale(xs: List[Int], factor: Int): List[Int] = {
    xs map (x => x * factor)
  }

  println(scale(List(1, 2, 3), 2)) // List(2,4,6)

Or we could apply map directly to a list on the fly.

val a = List(1,2,3)
val b = a.map((x: Int) => x*2)
println(b) // List(2,4,6)
Published 20 Jun 2018