Higher-order Functions
Table of Contents
1 Introduction
We illustrate programming with higher-order functions. This is one of the main features of a functional programming language.
2 Compose
The compose function o in mathematics takes two
functions \(f:A\rightarrow B\) assumed to be of type and
\(g:B\rightarrow C\) and returns a function of type
\(A\rightarrow C\) that takes an argument \(x\) and returns \(g\)
applied to the result $f to \(x\).
;;; Signature
;;; o: [A -> B], [B -> C] -> [A -> C]
;;; usage
;;; ((o add1 *2) 3) => 8
(define o
(lambda (f g) ; f: [A -> B]
; g: [B -> C]
(lambda (x) ; x: A
(g (f x)))))
In Racket, we could also have written this definition as follows:
(define ((o f g) x) (g (f x)))
Note that this corresponds to the definition \((f\circ g)(x) = g(f(x))\).
To test this, consider the function *2:
(define *2
(lambda (n)
(* n 2)))
The expression (o add1 *2) returns a function, which may
be applied to a number. Thus, ((o add1 *2) 3).
2.1 Tracing the execution of ((o add1 *2) 3)
;; ((o add1 *2) 3) =>
;; ((lambda (x) (g (f x))) {f: add1, g: *2} 3)
;; ((lambda (x) (*2 (add1 x))) 3) =>
;; (*2 (add1 x)) {x: 3} =>
;; (*2 (add1 3)) =>
;; (*2 4) =>
;; ((lambda (n) (* n 2)) 4) =>
;; (* n 2) {n: 4} =>
;; (* 4 2) =>
;; 8
3 Iteration
3.1 Definition
;;; (iter f n) returns the nth iterate of the function f.
;;; iter : [A -> A], nat? -> [A -> A]
;;; (iter f n) = identity, if n=0
;;; (iter f n) = (o f (iter f (sub1 n))), if n>0
;;; (iter f 0) = identity
;;; (iter f 1) = f
;;; (iter f 2) = (o f f)
(define identity
(lambda (x)
x))
(define iter
(lambda (f n) ; f: A -> A
; n: nat?
(if (= n 0)
identity
(o f (iter f (sub1 n))))))
3.2 Theorem relating (iter f 2) and (o f f)
;;; Theorem: (iter f 2) === (o f f)
;;; Proof:
(iter f 2) => beta
(if (= n 0)
identity
(o f (iter f (sub1 n)))) {f: f, n: 2} => subst
(o f (iter f 1)) => beta
(o f (if (= n 0)
identity
(o f (iter f (sub1 n)))){f: f, n:1}) => subst
(o f (o f (iter f 0))) => beta
(o f (o f (if (= n 0)
identity
(o f (iter f (sub1 n)))){f:f, n:0})) => subst
(o f (o f identity)) => ...
(o f (lambda (x) (identity (f x)))) =>
(o f (lambda (x) ((lambda (x) x) (f x)))) =>
(o f (lambda (x) (f x))) => eta
(o f f)
4 Derivative
;;; The Derivative operator
;;;
;;; ((D f) x) = (/ (- (f (+ x dx)) (f x)) dx)
(define dx 0.01)
;;; D : [num? -> num?] -> [num? -> num?]
(define D
(lambda (f) ; f: num? -> num?
(lambda (x) ; x: num?
(/ (- (f (+ x dx)) (f x))
dx))))
;;; D2 : [num? -> num?, num?] -> num?
(define D2
(lambda (f x) ; f: num? -> num?
(/ (- (f (+ x dx)) (f x))
dx)))
5 Lists
5.1 Map
;;; map: [A -> B, (list-of A)] -> (list-of B)
;;; usage:
;;; (map add1 '(2 5 9)) => '(3 6 10)
;;; (map add1 '()) => '()
;;; (map f '()) => '()
;;; (map f (cons x ls)) => (cons (f x) (map f ls))
(define map
(lambda (f ls) ; f: A -> B
(if (null? ls) ; ls: (list-of A)
'()
(let ([x (first ls)]
[ls2 (rest ls)])
(cons (f x)
(map f ls2))))))
5.2 Digression into let
(let ((x 3) (y 4)) (+ x y))
is syntactic shorthand for
((lambda (x y) (+ x y)) 3 4)
5.3 Filter
;;; filter
;;; (filter f ls) takes a predicate f and a list ls and returns a list
;;; all of whose elements satisfy f.
;;; Examples
;;; -------
;;; (filter number? '(a 3 8 "hello")) => '(3 8)
;;; (filter even? '( 2 4 9)) => '(2 4)
;;; (filter f? '()) => '()
;;; (filter f? (cons x ls)) =
;;; = (filter f? ls), if (f? x) is false
;;; = (cons x (filter f? ls)), if (f? x) is true
(define filter
(lambda (f? ls)
(if (null? ls)
'()
(let ([x (first ls)]
[lsr (rest ls)])
(if (f? x)
(cons x (filter f? lsr))
(filter f? lsr))))))