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))))))