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

Covers AQA 7517 4.12.1.2 First-class object · AQA 7517 4.12.2.1 Functional language programs · Eduqas A500QS 1.4 Principles of programming

Print it: worksheet (PDF) · answers (PDF) · as a web page

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.

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

1. Add a command "S" that sidesteps right, using right(), by changing only the table.
2. 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".
3. Write the type of make_turn in Haskell-style notation. Which part of it is a function type?