Functional Programming with Natural numbers and Lists
Table of Contents
- 1. Introduction
- 2. Function Composition
- 3. Sequential Application of Functions
- 4. Identity Function
- 5. Variable arity composition and sequentialisation:
compandseq - 6. Reduce
- 7. Linear Reduction
- 8. List Reduction as a Special Case of Linear Reduction
- 9. Iteration as a Special Case of Linear Reduction
- 10. Higher Order Reduction
- 11. Curried version of basic functions
- 12. Non-determinism
1 Introduction
In this section, we look at functional programming, or programming with functions as values on their own right. A functional is a function that takes or returns functions. In mathematics, functionals are very common, although they are better known as operators. Examples: the compose operator, denoted \(f\circ g\), which takes two functions \(f\) and \(g\) and returns their composition \(\lambda x.\ f(g(x))\). Another example is the iterate operator denoted by superscripts: \(f^{i}\) is the function obtained by iterating \(f\) \(i\) times.
Functional Programming is a style of programming where one can write functions that take or return functions. Racket/Scheme is eminently suited for functional programming.
Functional Programming is useful because it lets one write programs (functions) that generate other functions. This allows one to write very general programs at a high level of abstraction and then specialise these high level programs to generate more specific programs. Several examples of this type of abstraction followed by specialisation are presented in this section.
2 Function Composition
Given two functions \(f:A\rightarrow B\) and \(g:B\rightarrow C\), the composition of \(g\) with \(f\), written \(g\circ f:\) is the function from \(A\) to \(C\) defined as \((g\circ f)(x)= g(f(x))\).
(define comp2
(lambda (g f)
(lambda (x)
(g (f x)))))
(check-equal? ((comp2 (lambda (x) (* x 2)) (lambda (x) (+ 1 x))) 3) 8 "comp-1-test")
(check-equal? ((comp2 even? first) '(8 3 4)) #t "comp-2-test")
Notice the generation of the new composite function by
comp2. Thus comp2 denotes a higher-order
function that takes two functions as arguments and returns
a function as the result.
Thus we can write the conversion from Centigrade to Fahrenheit as a composition of two smaller functions:
(define add32 (lambda (x) (+ 32 x))) (define mul-with-9/5 (lambda (x) (* 9/5 x))) (define c->f1 ;; using comp2 (comp2 add32 mul-with-9/5)) (check-equal? (c->f1 0) 32 "c->f1-1") (check-equal? (c->f1 100) 212 "c->f1-2") (check-equal? (c->f1 -40) -40 "c->f1-3")
Note that although c->f1 is a function from (a number
denoting) temperature to temperature, there is no reference
to the temperature a formal parameter in the definition of
c->f1. It has been abstracted away. Abstractions such as
these result in programs that are compact, but which,
without some practice, also seem inscrutable. The advantage
of the compactness is, however, compelling.
3 Sequential Application of Functions
Another way to think about composition (and this is less confusing for some) is the operator $;$ often used in programming languages like C to express sequential operation.
\(f;g\) takes an \(x:A\) and returns \(g(f(x))\). Note that \(f;g = g\circ f\), but the notation \(f;g\) aligns better with the left to right reading: apply \(f\); then apply \(g\).
(define seq2
(lambda (f g)
(comp2 g f)))
(define c->f2 ;; using seq2
(seq2 mul-with-9/5 add32))
(check-equal? (c->f2 0) 32 "c->f2-1")
(check-equal? (c->f2 100) 212 "c->f2-2")
(check-equal? (c->f2 -40) -40 "c->f2-3")
4 Identity Function
The identity function \(\mathit{Id}\) is useful function to have around. Notice that \(f;\mathit{Id} = \mathit{Id};f = f\) for any function \(f\).
(define id (lambda (x) x))
5 Variable arity composition and sequentialisation: comp and seq
The composition and sequentilisation operators may be generalized to arbitrary arity:
;;; comp: [A_{n-1} -> A_n, A_{n-2} -> A_{n-1} ... A_{0} -> A_{1}] -> A_0 -> A_n
(define comp
(lambda fs
(cond
[(null? fs) id]
[else (comp2 (first fs) (apply comp (rest fs)))])))
(define sqr
(lambda (x) (* x x)))
(check-equal? ((comp) 5) 5 "comp-1")
(check-equal? ((comp add1) 5) 6 "comp-2")
(check-equal? ((comp add1 sqr) 5) 26 "comp-3")
(check-equal? ((comp add1 sqr mul-with-9/5) 5) 82 "comp-4")
;;; seq: [A_0 -> A_1, A_1 -> A_2 ... A_{n-1} -> A_n] -> A_0 -> A_n
(define seq
(lambda fs
(cond
[(null? fs) id]
[else (seq2 (first fs) (apply seq (rest fs)))])))
(check-equal? ((seq) 5) 5 "seq-1")
(check-equal? ((seq add1) 5) 6 "seq-2")
(check-equal? ((seq add1 sqr) 5) 36 "seq-3")
(check-equal? ((seq add1 sqr mul-with-9/5) 4) 45 "seq-4")
6 Reduce
Recall the notion of a deterministic, non-blocking state machine.
\[ S = \pair{X, U, Y, f:X,U\rightarrow X, h:X\rightarrow Y} \]
Deterministic and non-blocking means that there is exactly one next state for each state \(x\) and each input \(u\) and that state is \(f(x,u)\).
Given a state \(x\in X\) and a sequence \(\overline{u}\) of inputs, we are interested in knowing what is the output of the machine after it consumes the input \(\overline{u}\). Such a function is easy to write in functional programming.
(define list-reduce1
(lambda (f h)
(lambda (x us)
(letrec ([loop
(lambda (us a)
(cond
[(null? us) (h a)]
[else (loop (rest us) (f a (first us)))]))])
(loop us x)))))
;;; computes the length of a list
(define list-length1
(list-reduce1 (lambda (a u) (add1 a)) id))
(check-equal? (list-length1 0 '(a b c))
3 "reduce1-1")
;;; reverses a list
(define list-reverse1
(list-reduce1 (lambda (a u) (cons u a)) id))
(check-equal? (list-reverse1 '() '(a b c))
'(c b a) "reduce1-2")
;;; sums the numbers in a list of numbers
(define list-sum1
(list-reduce1 + id))
(check-equal? (list-sum1 0 '(1 5 2)) 8 "reduce1-3")
The function list-reduce1 takes the functions \(f\) and \(h\)
above and returns a function that takes a state \(x\) and a
sequence of inputs \(us\) and returns the output of the state
reached after consuming the entire input us.
7 Linear Reduction
By abstracting the sequencing operators of the input sequence, we get the following generalized reduce operator that works on finite linear structures that includes lists and also natural numbers.
;;; [first: (seq U) -> U, rest: (seq U) -> (seq U), base?: (seq U) -> boolean?]
;;; -> [init: X, f: [X,U]->X, h: X->Y] -> (seq U) -> Y
(define linear-reduce
(lambda (first rest base?)
(lambda (f h)
(lambda: (x us)
(letrec ([loop (lambda (us x)
(cond
[(base? us) (h x)]
[else (loop (rest us) (f x (first us)))]))])
(loop us x))))))
8 List Reduction as a Special Case of Linear Reduction
From this we may easily define reduction on lists as
(define list-reduce
(linear-reduce first rest null?))
;;; computes the length of a list
(define list-length
(: (list-reduce (lambda (a u) (add1 a)) id) 0))
(check-equal? (list-length '(a b c))
3 "list-length-1")
;;; sums the numbers in a list of numbers
(define list-sum
(: (list-reduce + identity) 0))
(check-equal? (list-sum '(1 5 2)) 8 "list-sum-1")
;;; reverses a list
(define list-reverse
(: (list-reduce (lambda (a u) (cons u a)) id) '()))
(check-equal? (list-reverse '(a b c))
'(c b a) "list-reverse-1")
;;; list-map: A->B -> list[A] -> list[B]
(define list-map
(lambda (g)
(: (list-reduce (lambda (ls u) (cons (g u) ls)) reverse) '())))
(check-equal? (: list-map add1 '(2 7 3)) '(3 8 4) "list-map-1")
9 Iteration as a Special Case of Linear Reduction
Natural numbers are also linear structures. A natural number \(n\) is isomorphic to a list of n objects.
(define nat-reduce
(linear-reduce identity sub1 zero?))
;;; nat? -> nat?
(define nat-sum
(: (nat-reduce + identity)
0))
(check-equal? (nat-sum 0) 0 "nat-sum-1")
(check-equal? (nat-sum 4) 10 "nat-sum-2")
;;; nat? -> nat?
(define nat-prod ;; factorial
(: (nat-reduce * identity)
1))
(check-equal? (nat-prod 0) 1 "nat-prod-1")
(check-equal? (nat-prod 4) 24 "nat-prod-2")
;;; f:A->A -> n:nat? -> A->A
(define nat-iterate
(lambda (f)
(: (nat-reduce (lambda (g n) (comp2 f g)) identity)
identity)))
(check-equal? (: nat-iterate add1 4 3) 7 "nat-iterate-1")
(check-equal? (: nat-iterate add1 0 3) 3 "nat-iterate-2")
10 Higher Order Reduction
Can the above programs be made more compact? The answer is yes! In the programs that follow, we will aggressively use currying, and will define functions in a curried way wherever possible and useful.
We curry the arguments f and h. Further, we also switch
the arguments of f, so the signature of \(f\) is now
\(f:U\rightarrow X\rightarrow X\). We also switch the order
of arguments to loop.
;;; [first: (seq U) -> U, rest: (seq U) -> (seq U), base?: (seq U) -> boolean?]
;;; -> [f: U->X->X, h: X->Y] -> (seq U) -> X -> Y
(define linear-reduce-t1: ;; take 1
(lambda (first rest base?)
(lambda: (f h)
(letrec ([loop (lambda: (us x)
(cond
[(base? us) (h x)]
[else (: loop (rest us)
(: f (first us) x))]))])
loop))))
Notice that the clause in the else part of loop's
definition may be written using seq, and as a result, the
x may be factored out of the definition:
;;; [first: (seq U) -> U, rest: (seq U) -> (seq U), base?: (seq U) -> boolean?]
;;; -> [f: U->X->X, h: X->Y] -> (seq U) -> X -> Y
(define linear-reduce: ;;; take2
(lambda (first rest base?)
(lambda: (f h)
(letrec ([loop (lambda (us)
(cond
[(base? us) h]
[else (seq (: (seq first f) us)
(: (seq rest loop) us))]))])
loop))))
Exercise: derive the equivalence of linear-reduce and
linear-reduce-t1 using the rules of eta reduction i.e.,
(lambda (x) (e x)) = e (provided x is not a free
variable in e) and the definition of seq.
11 Curried version of basic functions
First, we defined curried versions of binary functions +
and cons:
(define +: (lambda: (x y) (+ x y))) (define cons: (lambda: (x ls) (cons x ls)))
The curried list-reduce: and various functions generated
from it may now be defined as follows
(define list-reduce:
(linear-reduce: first rest null?))
;;; computes the length of a list
(define list-length:
(lambda (ls)
(: list-reduce: (lambda (u) add1) id ls 0)))
(check-equal? (list-length: '(a b c))
3 "list-length:-1")
;;; sums the numbers in a list of numbers
(define list-sum:
(lambda (ls)
(: list-reduce: +: id ls 0)))
(check-equal? (list-sum: '(1 5 2)) 8 "list-sum:-1")
;;; reverses a list
(define list-reverse:
(lambda (ls)
(: list-reduce: cons: id ls '())))
(check-equal? (list-reverse: '(a b c))
'(c b a) "list-reverse-1")
(define list-map:
(lambda: (g ls)
(: list-reduce: (seq g cons:) reverse ls '())))
(check-equal? (: list-map: add1 '(2 7 3)) '(3 8 4) "list-map:-1")
12 Non-determinism
Consider a non-deterministic state machine
\[S = \pair{X, U, f:U\rightarrow X\rightarrow 2^{X}, X, h:X\rightarrow X}\]
The transition relation in \(S\) is specified by the function
\(f:U\rightarrow X\rightarrow 2^{X}\) and output function \(h\)
is assumed identity. The corresponding reduce function
nd-reduce: takes a list of inputs us and a set of states
xs and returns the set of states reachable from xs via
us.
(define set-mapf
(lambda (f sets)
(set-map sets f)))
;;; nd:reduce:-t1 : [f: U->X->set[X]] -> list[U] -> set[X] -> set[X]
(define nd-reduce:-t1
(lambda (f)
(: list-reduce:
(lambda: (u xs)
(apply set-union (set-mapf (f u) xs)))
id)))
The next few programs illustrate an exercise in code
refactoring. Our goal is to write a version of nd-reduce
that abstracts away the parameters xs and u (in that
order).
We start by currying set-mapf and apply:
(define set-mapf:
(lambda: (f sets)
(set-map sets f)))
(define apply:
(lambda: (fn args)
(apply fn args)))
(define nd-reduce:-t2 ;; take 2
(lambda (f)
(: list-reduce:
(lambda: (u xs)
(: apply: set-union (: set-mapf: (f u) xs)))
id)))
Expanding the definition of :, we have
(define nd-reduce:-t3
(lambda (f)
(: list-reduce:
(lambda: (u xs)
((apply: set-union) ((set-mapf: (f u)) xs)))
id)))
Expanding the definition of lambda:, we have
(define nd-reduce:-t4
(lambda (f)
(: list-reduce:
(lambda (u)
(lambda (xs)
((apply: set-union) ((set-mapf: (f u)) xs))))
id)))
Introducing comp, we get
(define nd-reduce:-t5
(lambda (f)
(: list-reduce:
(lambda (u)
(lambda (xs)
((comp (apply: set-union) ((comp set-mapf: f) u)) xs)))
id)))
Inverse eta reduction abstracts the xs parameter away:
(define nd-reduce:-t6
(lambda (f)
(: list-reduce:
(lambda (u)
(comp (apply: set-union) ((comp set-mapf: f) u)))
id)))
By currying comp, we get
(define comp2:
(lambda: (f g)
(comp2 f g)))
(define nd-reduce:-t7
(lambda (f)
(: list-reduce:
(lambda (u)
((comp2: (apply: set-union)) ((comp set-mapf: f) u)))
id)))
This allows us to abstract away the u
(define nd-reduce:-t8
(lambda (f)
(: list-reduce:
(comp (comp2: (apply: set-union)) (comp set-mapf: f))
id)))
Exploiting the associativity of comp, i.e., (comp A (comp
B C)) to (comp A B C) we get
(define nd-reduce:-t9
(lambda (f)
(: list-reduce:
(comp (comp2: (apply: set-union)) set-mapf: f)
id)))
The code below tests nd-reduce: with a non-deterministic
state machine:
(define nd-reduce: nd-reduce:-t9)
(define nd-reduce-f:
(let ([f (lambda: (u x)
(case u
[(0) (case x
[(q0) (set 'q0 'q1)]
[(q1) (set 'q1 'q2)]
[(q2) (set 'q0)])]
[else (error 'nd-reduce: "invalid arg ~a" u)]))])
(nd-reduce: f)))
(check-equal? (: nd-reduce-f: '(0) (set 'q0)) (set 'q0 'q1) "nd-reduce-f:-1")
(check-equal? (: nd-reduce-f: '(0 0) (set 'q0)) (set 'q0 'q1 'q2) "nd-reduce-f:-2")
(check-equal? (: nd-reduce-f: '(0 0 0) (set 'q0)) (set 'q0 'q1 'q2) "nd-reduce-f:-3")
(check-equal? (: nd-reduce-f: '(0) (set 'q0 'q2)) (set 'q0 'q1) "nd-reduce-f:-4")