High Order Functions
Contents
High Order Functions¶
In Racket, functions are considered first class citizens. This means a function can do anything any other value can do. We can make lists of functions. We can take functions as inputs. We can return functions as outputs.
When we build functions that treat other functions as inputs/outputs, we call these high order functions.
Lambda Functions¶
What is a function? It is a sequence of inputs and a sequence of instructions to complete on those inputs. It then returns the result of its computation. There is no reason we need to give functions names. We could create a list of unnamed functions and apply “the fifth function.”
There is also no reason functions need to be defined ahead of time. We could have code that creates new functions as it executes. As long as we can write code to build the function, it can be defined during execution.
An anonymous function is a function that does not have a name. To define a function without giving it a name, we use a command called lambda. A lambda function is a function created using the lambda operator. We can leave the lambda function anonymous or we can decide to give it a name later.
Note
A lambda function is anonymous when it is created, but we can give it a name at any time. Which means it might not stay anonymous. There are also ways to create an anonymous function without using lambda, although we will not see any.
In Racket, the lambda is a built in function. We can use it at any time to create a function. It takes two inputs. The first is a list containing the parameters of the function. The second input is the body of the function. The lambda command then returns a pointer to the function that was defined.
The following creates a function that squares an input x.
(lambda (x) (* x x))
This is so common, there is a shortcut for the lambda symbol in Racket. This means you don’t have to type all the letters. You can just execute ctrl-\ or option-\ depending on your OS. The same function is defined using the shortcut below.
(λ (x) (* x x))
Once we have created a function, we can apply it immediately. This is not very useful, but it shows that the lambda does create a function. The following code will return \(14\).
( (lambda (x) (+ x x)) 7)
Once we have created a function, we can give it a name using the define command.
(define f1
(lambda (x) (+ x x))
)
This is actually just the long way of doing a shortcut we learned earlier.
(define (f2 x)
(+ x x)
)
When you call the function define command, Racket creates a lambda then gives it a name. This command just does the two steps at once to save you typing.
Almost every language has some version of the lambda command. It is very useful when paired with high order functions. The following code is in Python 3.
f = lambda x : x + x
g = lambda y : 2 * y
print(f(7)) #Prints 14
print(g(8)) #Prints 16
print(g(f(10))) #Prints 40
High Order¶
Lambda functions can allow us to make high order functions. We can create functions that return other functions. We can create lists of functions. We can take functions as inputs. We can also make functions attributes of classes in object oriented programming languages.
This allows us to write more general code that can be reused in many different situations.
A high order function is defined as any function that takes at least one function as input or returns a function as output.
We can make a simple high order function. This function is called applyTwice. It will take any function given and apply it twice to the same input.
The function takes two inputs. The first, f, is the function you want to apply twice. The second x is the input you want to start with. It will then execute (f (f x)).
;Apply Twice
;input-contract: a function f that takes 1 input
; a value x
;output-contract: the result of (f (f x))
(define (applyTwice f x)
(f (f x))
)
We can apply a double-negative by applying the built in not command twice. This just returns #t against because a double-negative cancels.
(applyTwice not #t) ;not not #t = #t
We can also use a lambda to create a function and execute it twice immediately. The following code computes \(4 * 9 = 36\).
(applyTwice (lambda (x) (+ x x)) 9) ;4*9=36
We can walk though the execute of this function using Equational Reasoning. Line numbers are placed above the code so it can be executed. Each line is valid racket code and can be run.
;Line 1
(applyTwice (lambda (x) (+ x x)) 9) ;Premise
;Line 2
((lambda (x) (+ x x)) ((lambda (x) (+ x x)) 9)) ;Apply Function Def
;Line 3
((lambda (x) (+ x x)) (+ 9 9)) ;Apply Lambda
;Line 4
((lambda (x) (+ x x)) 18) ;Evaluate Addition
;Line 5
(+ 18 18) ;Apply Lambda
;Line 6
36 ;Evaluate Addition
In mathematics, it is common to use the summation pattern. We want to sum all the numbers in some range based on a function.
\( \begin{align} \sum_{x=a}^{b} f(x) \end{align} \)
We can sum all the integers from 1 to 10 by just letting \(f(x)=x\) and setting \(a=1\) and \(b=10\).
\( \begin{align} \sum_{x=1}^{10} x = 1+2+3+4+5+6+7+8+9+10 = 55 \end{align} \)
We can generate even numbers by doubling. For example, \(2*3=6\). Six is the fourth even number. The first even number is zero. We can use the same pattern, but this time \(f(x)=2x\). We sum even numbers start at \(0\) up to \(2 * 5 = 10\).
\( \begin{align} \sum_{x=0}^{5} \left(2x\right) = 0+2+4+6+8+10 = 30 \end{align} \)
We can even add together a set of odd numbers using the pattern. Every odd number is just one larger then the even number before it. So, we set \(f(x) = 2x+1\). We can add up the odd numbers from 1 to 11.
\( \begin{align} \sum_{x=0}^{5} \left(2x + 1\right) = 1+3+5+7+9+11 = 36 \end{align} \)
If we needed to compute with the summation pattern repeatedly, it would be wasteful to define a different function for each one of these. It would clutter up our code and introduce more potential bugs. Instead, we can implement the summation pattern as a high order function. Then just change how it executes.
The general pattern can be described as follows. If \(a > b\) in the summation, then there is nothing to compute. We return 0 as the base case. Otherwise, we compute one value and apply the summation recursively.
\( \begin{align} \sum_{x=a}^{b} f(x) = \begin{cases} f(a) + \sum_{x=a+1}^{b} f(x) & a \le b \\ 0 & a > b \end{cases} \end{align} \)
We can return to the even summation example, this time we look at the recursive details.
\( \begin{align} \sum_{x=0}^{5} \left(2x\right) =& (2 * 0)+\sum_{x=1}^{5} \left(2x \right)\\ =& 0 + (2 * 1) + \sum_{x=2}^{5} \left(2x \right) \\ =& 0 + 2 + (2 * 2) + \sum_{x=3}^{5} \left(2x \right) \\ =& 0 + 2 + 4 + (2 * 3) + \sum_{x=3}^{5} \left(2x \right) \\ =& 0 + 2 + 4 + 6 + (2 * 4) + \sum_{x=5}^{5} \left(2x \right) \\ =& 0 + 2 + 4 + 6 + 8 + (2 * 5) + \sum_{x=6}^{5} \left(2x \right) \\ =& 0 + 2 + 4 + 6 + 8 + 10 + 0 \\ =& 30 \end{align} \)
In Racket, we can implement summation as a high order function. It takes the function \(f(x)\) along with integers \(a\) and \(b\). Notice that we apply the function \(f\) in the code using (f a). It doesn’t matter what \(f\) is as long as it takes one input argument. This code will execute it.
;Summations
;input-contract: function f
; two integers a,b denoting a range. a <= b
;output-contact:
; sum of f(x) for x in a <= x <= b
(define (sum f a b)
(if (> a b)
0
(+ (f a) (sum f (+ a 1) b))
))
We can replicate the three summations from above by using lambda functions.
(sum (lambda (x) x) 1 10) ;55
(sum (lambda (x) ( * 2 x ) ) 0 5) ;30
(sum (lambda (x) (+ ( * 2 x ) 1) ) 0 5) ;36
We can compute summations that use more elements or complete more complex calculations.
(sum (lambda (x) (+ (* 2 x) 1)) 0 10) ;121
(sum (lambda (x) (* x x)) 0 5) ;55
(sum (lambda (x) (/ 1 (* x x))) 2 5);1669/3600
We only needed build the summation logic once. Then we could apply it repeatedly on different lambdas to create different summations.
Returning Functions¶
We can also create functions that return other functions. This can allow us to define how functions work during executing. We can use the result of a calculation, file, or user input to determine how functions are defined.
We write a function that creates a specific case of a general pattern.
Imagine that we have a program that computes the price of items. It will add sales takes to the purchase.
We can create a function that returns another function to determine the tax added to an item.
;Build Tax
;input-contract: float n (tax precent)
;output-contract: A function of one input
(define (set-tax-rate n)
(lambda (x) (+ x (* x n)))
)
The function takes an input \(n\). It puts this number into the another function. The returned function has a different input \(x\).
We can use this to create two new functions with different rates.
(define philtax (set-tax-rate .07))
(define buckstax (set-tax-rate .06))
Then we can use the function we defined throughout our code.
(philtax 100) ;107.0
(philtax 95.99) ;102.7093
(philtax 10.23) ;10.946100000000001
(buckstax 100) ;106.0
(buckstax 95.99) ;101.7494
(buckstax 10.23) ;10.8438
We can even combine this function together with our sum function.
(sum (set-tax-rate 0.04) 1 10) ;57.2
Map¶
There are two exceptionally common patterns in high order functions. The first is the map pattern. This pattern takes a function and a list of values. It applies the function to every element in the list and creates a new list of results.
This provides a quick way to map a set of values to a new set of related values. For example, we could take a list of numbers from 1 to 5 and square even value in the entire list.
(map (lambda (x) (* x x)) '(1 2 3 4 5))
;returns '(1 4 9 16 25)
This does the same thing as if we defined out own function to square the list.
(define (square_el L)
(if (null? L)
null
(cons (* (first L) (first L))
(square_el (rest L)))))
(square_el '(1 2 3 4 5))
;returns '(1 4 9 16 25)
The difference is, with map we only define the function that gets executed on each element. We don’t have to write the recursion ever time.
Map follows a basic pattern. We have a list of values \(L\) and we need to apply a function \(f\). The value at index \(i\) of the original list will be \(L[i]=f(L[i])\) after the map is complete.
To define the map function, we start with the base case. If there are no elements in the list, then it is null after the function is applied. There is nothing to apply the function to.
(define (myMap f L)
(if (null? L)
null
(... Do something? ...)
)
)
All the interesting work happens during the recursion. We could just take the first value of the list and put it back in front. The following code makes an unchanged copy of the original list.
(define (myMap f L)
(if (null? L)
null
(cons (first L) (myMap f (rest L)) )
)
)
We don’t want to just make a copy. We want to change the values. We need to apply the function to each first value before it is added back in. We add in (f (first L)) instead of (first L).
(define (myMap f L)
(if (null? L)
null
(cons (f (first L)) (myMap f (rest L)) )
)
)
This gives us a fulling functional version of the map command. It works the same as the built in one.
Fold¶
A second command pattern is the reduce or fold pattern. This is a generalization of the sum command we wrote earlier. Instead of just doing summations, it takes a list of numbers and combines them using an operator given.
The Racket language has two fold commands.
foldr- fold rightfoldl- fold left
Since not all operators will be commutative (\(3+4=4+3\)), we might need to decide which goes on the left and right.
Imagine we wanted to sum all the values in a list.
(define (sumList L)
(if (null? L)
0
(+ (first L) (sumList (rest L)))
))
If we ask (sumList '(1 2 3 4 5)) we get the result 15. Looking at the source code we can see the pattern that of the additions.
(sumList '(1 2 3 4 5))
(+ 1 (sumList '(2 3 4 5)))
(+ 1 (+ 2 (sumList '(2 3 4 5))))
(+ 1 (+ 2 (+ 3 (sumList '(2 3 4 5)))))
(+ 1 (+ 2 (+ 3 (+ 4 (sumList '(2 3 4 5))))))
(+ 1 (+ 2 (+ 3 (+ 4 (+ 5 (sumList '()))))))
(+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0)))))
We can start to think about how to generalize this pattern. We want to be able to put any function in instead of just +. A more general pattern might look more like the code given below. We replace the fixed operator + with a parameter f. Instead of sumList, the name is changed to reduce to be more general.
(f 1 (reduce f '(2 3 4 5)))
We also have to decide what the initial value is. What is returned when we call (reduce f '())? This has to be an answer, but it might not always be 0 like in the example. We also need to make that a parameter.
These changes provide us with a reduce function.
(define (reduce f init L)
(if (null? L)
init
(f (first L) (reduce f init (rest L)))))
Notice how similar it is to the sumList function. it uses the same pattern, but in a more general way. We can use this function to compute the sum, but we can just as easily compute the product of numbers.
(reduce + 0 '(1 2 3 4 5));15
(reduce * 1 '(1 2 3 4 5));120
We could even use lambda to define out own operator.
;Why does this return 1?
(reduce (lambda (x y) (if (< x y) x y)) 100 '(1 2 3 4 5 ))
We don’t need to write this command ourself. It is included.
(foldr * 1 '(1 2 3 4 5)) ;120
(foldr * 0 '(1 2 3 4 5)) ;0
(foldr + 0 '(1 2 3 4 5)) ;15
(foldr + 1 '(1 2 3 4 5)) ;16
As noted above, there are actually two commands foldr and foldl. Both addition and multiplication are commutative. That means the two functions will return the same results.
What if we did a subtraction? Subtraction is not commutative, we know that \(3-1\neq 1-3\). That means the order of application can produce different results.
(foldr - 1 '(1 2 3 4)) ;-1
(foldl - 1 '(1 2 3 4)) ;3
Both commands use the same lists and the same initial value. It is just the order of application.
To determine how the two functions differ, we can implement a special minus. This function does the standard minus, but also prints out debugging information.
(define (minus a b)
(begin
(display "(minus ")
(display a)
(display " ")
(display b)
(display ")")
(newline)
(- a b)
)
)
If we look at the output of foldr on this function, we can use the display commands to determine what it does.
(foldr minus 1 '(1 2 3 4)) ;-1
;(minus 4 1) (- [last element] [base case])
;(minus 3 3) (- [next element] [prev res])
;(minus 2 0) (- [next element] [prev res])
;(minus 1 2) (- [next element] [prev res])
(- 1 (- 2 (- 3 (- 4 1)))) ;What is executed
We can repeat the pattern on foldl to see the difference.
(foldl minus 1 '(1 2 3 4)) ;3
;(minus 1 1) (- [first element] [base case])
;(minus 2 0) (- [second element] [prev res])
;(minus 3 2) (- [next element] [prev res])
;(minus 4 1) (- [next element] [prev res])
(- 4 (- 3 (- 2 (- 1 1)))) ;What is executed
Zip¶
Another common pattern is called the zip (short for zipper). It takes two lists and combines them together. Imagine each list is one half of the zipper. We take one value from each side and merge them together just like the zipper does.
The following function takes two lists of numbers and zippers them together using addition. it adds the first number in each list together. Then it adds the second number in each list together.
(define (addpairs A B)
(if (or (null? A) (null? B))
null
(cons (+ (first A) (first B))
(addpairs (rest A) (rest B)))
))
(addpairs '(1 3 5 7) '(2 4 6 8))
;Returns '(3 7 11 15)
We could also multiply the pairs by just changing the operation.
(define (multpairs A B)
(if (or (null? A) (null? B))
null
(cons (* (first A) (first B))
(multpairs (rest A) (rest B)))
))
(multpairs '(1 3 5 7) '(2 4 6 8))
;Returns '(2 12 30 56)
If we generalize the code to take any operator instead having it hard coded, we can create our own zipper.
(define (zip f A B)
(if (or (null? A) (null? B))
null
(cons (f (first A) (first B))
(zip f (rest A) (rest B)))
))
(zip + '(1 3 5 7) '(2 4 6 8))
;'(3 7 11 15)
(zip * '(1 3 5 7) '(2 4 6 8))
;'(2 12 30 56)
We can use all our functions together to make complex tasks very simple.
We start by defining two lists.
(define A '(1 2 3 4 5 6 7))
(define B '(5 9 7 2 3 4 1))
If we zip them together using addition, we total the matching values in each column.
(zip + A B)
;'(6 11 10 6 8 10 8)
We can them map over this a function that determines if the value is even or odd. We put a 1 for even and a 0 for odd.
(map (lambda (x) (if (even? x) 1 0))
(zip + A B)
)
;'(1 0 1 1 1 1 1)
We can count the number of even totals by using foldr to add all the values up. The following single line command takes all the pairs in the two lists, adds them up, then counts how many additions resulted in even values. All in one command with no explicit recursion on the programmers part.
(foldr + 0
(map (lambda (x) (if (even? x) 1 0))
(zip + A B)
)) ;6
Recursive Music¶
Racket has a number of packages that can be installed. You can read more about installing packages here. The easiest method is to select “Package Manager” from the file menu and search for the package you want. Let DrRacket do all the work.
This example uses the rsound package. It that is not installed, this example will not work. This example has been adapted from the Rsound documentation [JohnClements20].
Once we include the rsound package, we can ask the computer to make a ding.
#lang racket
(require rsound)
;This is a good Example to test with
;It just dings
(play ding)
The ding is fun, but not very useful. It is more useful to ask the program to play a specific note. There are may kinds of sounds it can play. The following function create synthesizer notes.
(define dur 1/10)
;Create diffe
(define (note offset len) (synth-note "vgame" 49 (+ 60 offset)
(round (* (default-sample-rate) (* dur len) )))
)
This function takes offset of the midi note number and a duration to play the note. We can use map to create a sequence of notes. We map the note function over a collection of different offsets.
;Play the note with offset note number
(define (seqNotes f L) (map f L))
We may also want to repeat a second of notes over and over again. The following recursive function repeats a pattern a certain number of times.
(define (repeat pattern count)
(if (= count 0)
null
(append pattern (repeat pattern (- count 1)))
)
)
To create a song, we play two different sequences of notes together. In additional to our functions, this uses some that are part of the rsound library.
(define z
(rs-overlay
(rs-append* (repeat (seqNotes
(lambda (x) (note x 1)) '(0 2 3 7)) 20))
(rs-append* (repeat (seqNotes
(lambda (x) (note x 4)) '(0 -5 -4 -5)) 5))
)
)
Once our song is built, we just need to tell racket to play it.
(play z)
The complete code is given below if you want to test it and see what music it plays. There are some situations where music contains recursive patterns. A recursive programming languages allows us to replicate this idea.
#lang racket
(require rsound)
;This is a good Example to test with
;It just dings
;(play ding)
(define dur 1/10)
;Create diffe
(define (note offset len) (synth-note "vgame" 49 (+ 60 offset)
(round (* (default-sample-rate) (* dur len) )))
)
;Generate a list of notes
;Play the note with offset note number
(define (seqNotes f L) (map f L))
(define (repeat pattern count)
(if (= count 0)
null
(append pattern (repeat pattern (- count 1)))
)
)
(define z
(rs-overlay
(rs-append* (repeat (seqNotes
(lambda (x) (note x 1)) '(0 2 3 7)) 20))
(rs-append* (repeat (seqNotes
(lambda (x) (note x 4)) '(0 -5 -4 -5)) 5))
)
)
(play z)