Functions are first-class values

Typed Racket supports functions as first-class values, by which we mean that we can treat functions just the way that we treat other values, such as numbers, strings, lists, etc. Specifically, we can pass functions as arguments to function calls, return function values as results from function calls, and embed function values in data structures.

Function types

Just as function values are first-class in Typed Racket, function types are also first-class. We have been using -> when specifying the type signature of functions, but this symbol is a type operator, which can be used to construct new types just the way that we use the union type operator (U). For example,

(Integer -> Integer) -> Boolean

is the type function that takes an integer to integer function as an argument and returns a boolean result. Alternatively,

Integer -> (Integer -> Boolean)

is the type of a function that takes an integer argument and returns an integer to boolean function as a result. When written in infix style, the -> operator associates to the right, so we could rewrite the previous type without the extra parentheses.

Integer -> Integer -> Boolean

We could also write these types using Racket’s prefix type syntax

(-> (-> Integer Integer) Boolean)
(-> Integer (-> Integer Boolean))

We can also use function types as arguments to other type constructors. For example, the type of a list of real to real functions would be written as

(Listof (Real -> Real))

Functions as arguments

The simplest, and the most common, use of higher-order functions is as arguments to functions. For example, we might wish to convert lists of values to strings where the values are separated by commas. We could write a specific function for numbers

(: numbers->string : (Listof Number) -> String)
(define (numbers->string nums)
  (match nums
    ['() ""]
    [(list x) (number->string x)]
    [(cons x xs) (string-append (number->string x) "," (numbers->string xs))]))

(check-expect (numbers->string '()) "")
(check-expect (numbers->string '(1)) "1")
(check-expect (numbers->string '(1 2 3)) "1,2,3")

and we could write a version for symbols

(: symbols->string : (Listof Symbol) -> String)
(define (symbols->string nums)
  (match nums
    ['() ""]
    [(list x) (symbol->string x)]
    [(cons x xs) (string-append (symbol->string x) "," (symbols->string xs))]))

(check-expect (symbols->string '()) "")
(check-expect (symbols->string '(a)) "a")
(check-expect (symbols->string '(a b c)) "a,b,c")

But these two functions only differ in the operation used to convert list elements to strings. We can abstract over this operation by using a function-valued parameter:

(: values->string : (All (A) (A -> String) (Listof A) -> String))
(define (values->string ->string values)
  (match values
    ['() ""]
    [(list x) (->string x)]
    [(cons x xs) (string-append (->string x) "," (values->string ->string xs))]))

(check-expect (values->string number->string '()) "")
(check-expect (values->string symbol->string '(a)) "a")
(check-expect (values->string number->string '(1 2 3)) "1,2,3")

In practice, the most common use of functions as arguments is when working with aggregate types, such as lists and vectors. We discuss the various higher-order list functions below.

Functions as results

We can also write functions that return functions. For example, we can define an addition function that takes one argument x and returns a function that add’s the value of x to its argument:

(: add : Number -> Number -> Number)
(define (add x)
  (local
    {(: add-x : Number -> Number)
     (define (add-x y) (+ x y))}
    add-x))

We can then use add to define some other functions

(define incr : Number -> Number (add 1))
(define decr : Number -> Number (add -1))

A key aspect of understanding higher-order functions is understanding how lexical scoping works. In the above example, the variable x is a free variable in the function add-x (i.e., it is bound as a parameter to the function add). To represent the function value that results from applying add to an argument \(n\), Typed Racket uses a representation that combines the code that implements the function (i.e., add-x) with the bindings of its free variables (i.e., \(\{\mathtt{x} \mapsto n\}\)). We use the term closure to refer to the pair of the code and environment (i.e., the free-variable bindings) that represent a function value.

In the above example, the variable incr is bound to a closure that binds x to 1, whereas the variable decr is bound to a closure that binds x to -1.

Functions embedded in data structures

A simple example is a list of functions:

(define trig-fns : (Listof (Real -> Real)) (list sin cos tan))

Higher-order functions on lists

Typed Racket provides a number of higher-order functions that operate on lists:

(: map : (All (X Y) (X -> Y) (Listof X) -> (Listof Y)))
;; maps a function across a list to produce a new list

(: foldl : (All (X Y) (X Y -> Y) Y (Listof X) -> Y))
;; fold a reduction function across a list left-to-right

(: foldr : (All (X Y) (X Y -> Y) Y (Listof X) -> Y))
;; fold a reduction function across a list right-to-left

(: build-list : (All (X) Integer (Natural -> X) -> (Listof X)))
;; build a list of the specified length by applying the function
;; to 0, 1, ..., length-1

(: filter : (All (X) (X -> Boolean) (Listof X) -> (Listof X)))
;; filter a list using the given predicate

(: andmap : (All (X) (X -> Boolean) (Listof X) -> Boolean))
;; return true if the predicate is true for all members of the list

(: ormap : (All (X) (X -> Boolean) (Listof X) -> Boolean))
;; return true if the predicate is true for any member of the list

Anonymous lambdas

When programming with higher-order functions, it is annoying to have to define new named functions whenever we need a function value. In these cases, we can use the lambda expression, which provides a way to define a non-recursive function without giving it a name. The basic syntax is

(lambda ([param-1 : ty-1] ... [param-n : ty-n]) expr)

where the param-i are the function parameters with the corresponding declared types. Anonymous functions are particularly useful in combination with higher-order functions, such as map and foldl. For example, we can compute the sum of the squares of a list of numbers as follows

(: sum-of-sqrs : (Listof Real) -> Real)
(define (sum-of-sqrs xs)
  (foldl
   (lambda ([x : Real] [acc : Real]) (+ acc (* x x)))
   0
   xs))

(check-expect (sum-of-sqrs '()) 0)
(check-expect (sum-of-sqrs '(1 2 3)) 14)

Lambda expressions are also quite useful for writing curried functions. For example, a curried form of addition can be written as

(: curried-add : Integer -> (Integer -> Integer))
(define (curried-add a)
  (lambda ([b : Integer]) (+ a b)))

Curried functions are useful when combined with other higher-order functions. For example, using curried-add, we can use map to increment the elements of a list by some amount:

(: list-inc : Integer (Listof Integer) -> (Listof Integer))
(define (list-inc delta xs) (map (curried-add delta) xs))
Last updated 2020-03-04 09:35:23 -0600
Table of Contents | Back to CS151 Home