First-class objects and higher-order functions

Functions as values in variables, lists and dictionaries, passed as arguments and returned as results, lambdas, closures and a robot command table.

A13.3Functional programmingA level20 min

Do this lesson in the simulator

A number can be stored in a variable, put in a list, passed to a function and returned from one. So far you have treated functions as something different: code you call. In a functional language, a function is a value like any other. This one idea is what makes the rest of the paradigm work.

First-class objects

A first-class object (or first-class value) is one that can:

appear in expressions
be assigned to a variable
be passed as an argument to a function
be returned as the result of a function call

Integers, reals, characters and strings are first-class objects in almost every language. In functional languages, functions are first-class objects too. So are functions in many imperative languages, including Python and JavaScript.

def double(x):
    return 2 * x

f = double                    # no brackets: the function itself, not a call
print(f(21))                  # the variable can be called
print(f)                      # it holds a function object

ops = [double, abs, str]      # functions in a list
for op in ops:
    print(op(-4))

Run this in the simulator

f = double does not call double. It makes f refer to the same function, so f(21) is 42. double(21) with brackets is a call, and its value is a number; double without brackets is the function, and its value is a function. Mixing the two up is the most common bug in this style.

Functions as arguments

A function passed as an argument can be called inside the function that receives it:

def apply_twice(f, x):
    return f(f(x))

def add_ten(x):
    return x + 10

print(apply_twice(add_ten, 5))
print(apply_twice(str.upper, "go"))
print(apply_twice(lambda cm: cm / 2, 80))

Run this in the simulator

The first prints 25, the second GO, the third 20.0. apply_twice does not know or care what f is; it only needs something it can call with one argument.

lambda cm: cm / 2 is a lambda expression: a function with no name, written in one expression, for when a function is needed once. Python's lambda can only contain a single expression. In Haskell a lambda is written with a backslash, \cm -> cm / 2.

Functions as results

A function can make a new function and return it:

def make_scaler(factor):
    def scale(x):
        return x * factor
    return scale              # the function, not a call

to_mm = make_scaler(10)
to_m = make_scaler(0.01)
print(to_mm(42), to_m(42))

Run this in the simulator

make_scaler(10) returns a function that multiplies by 10. The inner function remembers factor from the call that made it, even after make_scaler has returned; a function that carries values from where it was made like this is called a closure. This prints 420 0.42.

Higher-order functions

A function is higher-order if it takes a function as an argument, returns a function as its result, or both. apply_twice and make_scaler are higher-order. Python's built-in sorted is too, when you give it a key function:

readings = [(0, 51.0), (90, 12.5), (180, 33.0), (270, 44.0)]   # (heading, cm)
print(sorted(readings, key=lambda r: r[1]))                     # nearest first

Run this in the simulator

In Haskell, apply_twice is one line, with its type above it:

applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)

Read the type from the left: the first argument is a function (a -> a) from some type a to the same type; the second is a value of type a; the result is of type a. The brackets round a -> a show that the first argument is itself a function. applyTwice (+10) 5 is 25.

The three higher-order functions every functional programmer uses, map, filter and fold, are lesson A13.5.

A command table

First-class functions give the robot a neat way to obey commands. Instead of a long if/elif chain, keep a dictionary from each command letter to the function that carries it out, and look the function up:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def go(cm):
    forward(50, distance=cm)

def spin(degrees):
    turn_right(30, angle=degrees)

TABLE = {"F": go, "R": spin}

for command in ["F20", "R90", "F10"]:
    action = TABLE[command[0]]       # a function, looked up by its letter
    action(int(command[1:]))         # applied to the number
    print(command[0], command[1:])

Run this in the simulator

To add a command, add an entry to the table; the loop does not change. The table is data, and the functions are values in it.

In the exam

Questions ask you to explain what a first-class object is and to show that functions are first-class in a given language, or to say what makes a function higher-order. List the four properties: appears in expressions, assigned to a variable, passed as an argument, returned from a function call.

AQA A level 4.12.1.2 4.12.2.1

AQA asks you to know that a function is a first-class object in functional languages, and in imperative languages that support it, so it can be an argument to another function and the result of a function call. It lists first-class objects as those that may appear in expressions, be assigned to a variable, be assigned as arguments and be returned in function calls, giving integers, floating-point values, characters and strings as examples. It defines a higher-order function as one that takes a function as an argument or returns a function as a result, or does both.

Eduqas A level 1.4

Eduqas covers the characteristics of programming paradigms. Treating functions as values that can be passed and returned is one of the defining features of functional languages to describe.

Task: the command table

Drive a route from a table of functions, with no if or elif anywhere in the program: the table does the choosing.

drive_forward(cm) drives forward cm centimetres at speed 50, and drive_back(cm) drives backward cm centimetres at speed 50.
make_turn(direction) takes "left" or "right" and returns a new function of one parameter, degrees, that turns that way by degrees at speed 30.
ACTIONS is a dictionary from the letters "F", "B", "L" and "R" to drive_forward, drive_back, make_turn("left") and make_turn("right").
run_route(actions, route) takes a table like ACTIONS and a list of commands, each a letter followed by a whole number such as "F25". For each command in order it prints the letter and the number separated by a space, such as F 25, and applies the letter's function to the number.

Call run_route(ACTIONS, ["F25", "R90", "F20", "L90", "B10"]).

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def run_route(route):
    for command in route:
        letter = command[0]
        amount = int(command[1:])
        if letter == "F":
            forward(50, distance=amount)
        elif letter == "R":
            turn_right(30, angle=amount)

run_route(["F25", "R90", "F20", "L90", "B10"])

Challenges

Add a command "S" that sidesteps right, using right(), by changing only the table.
Write make_repeat(action, times) that returns a function doing action times times with the same amount. Use it to add "D" for "forward, twice".
Write the type of make_turn in Haskell-style notation. Which part of it is a function type?