Function types and function application

Functions as mappings, function type f: A to B, domain and co-domain, and function application with arguments from a Cartesian product.

A13.2Functional programmingA level20 min

At GCSE a function was a named block of code that could return a value. Functional programming takes its idea of a function from maths, where a function is defined by what it maps to what, and every function has a type that says which values can go in and which can come out. This lesson gives you the vocabulary exam questions use: function type, domain, co-domain and function application.

A function is a mapping

A function takes each value from one set and maps it to exactly one value in another set. BugBot's compass function takes a heading in whole degrees and gives the nearest compass point:

Function type, domain and co-domain

A function f has a function type, written

f : A → B

A is the argument type, the set of values the function can be applied to, and is called the domain. B is the result type, the set its results are taken from, and is called the co-domain. For the compass:

compass : {0, 1, 2, ..., 359} → {N, E, S, W}

The domain and co-domain are always subsets of some data type. The domain here is a subset of the integers and the co-domain a subset of the strings. Some more types:

The co-domain says what results could be; a function need not produce all of them. square has co-domain integer, but it never gives a negative number. The results a function actually produces for its domain are sometimes called its range or image, a subset of the co-domain.

Writing the type in code

Haskell programs usually state a function's type on the line above its definition, with :: meaning "has type":

compass :: Int -> String
compass degrees = ["N", "E", "S", "W"] !! (((degrees + 45) `mod` 360) `div` 90)

Python does not enforce types, but you can write the same information as type hints: the argument's type after a colon, and the result type after ->.

def compass(degrees: int) -> str:
    return "NESW"[((degrees + 45) % 360) // 90]

for d in (10, 80, 100, 200, 350):
    print(d, "->", compass(d))

Run this in the simulator

Adding 45 before dividing by 90 centres each compass point on its direction: 315 to 359 and 0 to 44 give N, 45 to 134 give E, 135 to 224 give S and 225 to 314 give W. The % 360 wraps 315 + 45 = 360 back round to 0.

Function application

Giving a function particular arguments is called function application. compass(200) is the application of compass to the argument 200, and its value is "S". In Haskell there are no brackets: application is just the function name followed by its argument, compass 200.

What about a function of two arguments? add(3, 4) applies add to the integers 3 and 4. Its type is written

add : integer × integer → integer

where integer × integer is the Cartesian product of the set of integers with itself: the set of every pair of integers. So although we say add takes two arguments, strictly it takes one argument, the pair (3, 4), from the set integer × integer.

def add(pair: tuple[int, int]) -> int:
    a, b = pair
    return a + b

p = (3, 4)
print(add(p))            # one argument: the pair
print(add((10, -2)))

Run this in the simulator

In Haskell the same function is written add (x, y) = x + y, with type (Integer, Integer) -> Integer. Haskell programmers more often write add x y = x + y, with type Integer -> Integer -> Integer; that is a different idea, partial application, and is lesson A13.4.

Applying a type to the robot

heading() gives a real number of degrees, so to use compass on it, first map it into compass's domain. Rounding and % 360 turn any real heading into a whole number from 0 to 359:

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

def compass(degrees: int) -> str:
    return "NESW"[((degrees + 45) % 360) // 90]

turn_right(30, angle=100)
h = heading()
print("heading", h, "is in the domain?", h == int(h) and 0 <= h <= 359)
print("compass", compass(round(h) % 360))

Run this in the simulator

A function applied to a value outside its domain has no defined result. Python may still return something, or crash; in a strongly typed language like Haskell, applying compass to a string is rejected before the program even runs.

Task: the compass type

Write compass with its type hints, exactly as def compass(degrees: int) -> str:. Its domain is the whole numbers 0 to 359, and it returns "N" for 0 to 44 and 315 to 359, "E" for 45 to 134, "S" for 135 to 224 and "W" for 225 to 314. Then:

1. Apply compass to every value in its domain, collect the different results, and print them sorted alphabetically and separated by spaces, as range: <letters>. Work the letters out; do not type them into the print.
2. Turn the robot right by 90 degrees four times. After each turn, print facing <letter>, where the letter is compass applied to the robot's heading() rounded to a whole number and taken MOD 360.

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

def compass(degrees):
    return "N"

print("range:", compass(0))

Challenges

1. Give the type, domain and co-domain of a function quadrant(x, y) that returns 1, 2, 3 or 4 for a point on the mat.
2. Write compass8(degrees: int) -> str with the eight points N, NE, E, SE, S, SW, W, NW. What changes, and what stays the same?
3. battery() returns a whole percentage. Write down a sensible function type for it. Why is it not really a function in the mathematical sense?