This work by Anthony Zhang is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright 2013-2017 Anthony Zhang.
Designing Functional ProgramsInstructor:
Name: Sandra (Sandy) Graham
Email: sandy.graham@uwaterloo.ca
Office: MC 6423
Office hours: Tuesdays in MC 2062/2063, Thursdays in MC 4065, 1:15-2:15 PMISA = instructional support assistant
Drop by the Tutorial Center (MC 4065) during the scheduled hours for assistance, no appointments needed.
Do this before every class:
Two important branches of language design:
Member of the LISP family of languages.
Basic Scheme forms:
;; block comment
5 ; inline comment
6 ; atom number
"abc" ; atom stringStylistically, single line comments should use two semicolons; however, this is not required by the syntax.
Primary aspects of course:
In math, functions generalize similar expressions:
f(x) = x^2+4*x+2
g(x,y) = x+yFunction consist of:
Application of function:
f(3)
g(5,6)Application supplies arguments (the values) that correspond to the parameters.
In math, application is evaluated by substitution:
f(g(5,6)) = f(5+6) = f(11) = 11^2+4*11+2 = 167Evaluation can be done in any order:
g(g(1,3),f(2)) = g(1+3,f(2)) or g(1,3) + f(2)The Scheme interpreter (program that evaluates Scheme code) uses a left to right, depth-first evaluation order - inside-out, left to right.
Math is written in infix notation - the operator is placed between its operands. There are also notations known as prefix and postfix notation - operator before operands, and operator after operands, respectively.
Scheme uses prefix notation. Prefix notation needs no order of operations because there is no ambiguity.
Convert infix to prefix:
(6-4)/(5+7)
What is the last operator to be applied?
/ (6-4) (5+7)
Repeat process.
/ - 6 4 + 5 7
This is valid prefix notation, but not valid Scheme.
Since in Scheme arbitrary numbers of operands are supported, we need to add brackets to make it explicit.
(/ (- 6 4) (+ 5 7))Conversion is done by moving the last operator to be applied to the beginning of the subexpression until no infix operators remain. Operand order remains the same.
If we treat infix operators as functions, we don't need to use parentheses to specify order of operations:
3 - 2 ;infix notation
-(3, 2) ;prefix notationConvert to prefix notation:
(((3+8)-(7+9))/12) ;infix notation
/ ((3+8)-(7+9)) 12
/ - (3+8) (7+9) 12
/ - + 3 8 + 7 9 12 ;prefix expression
(/ (- (+ 3 8) (+ 7 9) 12)) ;scheme codeScheme code needs the brackets in order to support arbitrary numbers of parameters.
Racket (Scheme) development environment.
DrRacket has interactions and definitions panes. Definitions are persistent and are saved on permanent storage. Interactions are realtime and users interact with programs here, but are not saved.
The interactions pane is a REPL (read-eval-print-loop), a way to write some code, execute it, and get results immediately.
Integers in Scheme are unbounded - they can be arbitrarily large without fear of overflows.
Rational numbers in Scheme are represented and computed exactly, without any loss in precision. Scheme tries to use exact numbers whenever possible.
When an exact value is not possible, such as with irrational numbers, they are marked as inexact. Inexact values taint all computations it is used in with inexactness.
(sqrt 2) evaluates to #i1.414213562370951 ; #iX represents a literal inexact value
(expt 2 100) evaluates to 1267650600228229401496703205376 ;exact
(/ -5 12) evaluates to $-\frac{5}{12}$ ;exact
#i1.23 ;inexact
1.2e12 ;exact
1.234567 ;exact
12345 ;exactCommon errors:
(+ 1 2(1 + 2)(/ 3 (- 2 2)) (division by 0)The stepper tool is useful for tracing execution one step at a time.
Scheme is a dynamically typed language - types do not need to be declared. Contracts are not enforced by the language since they are just comments. However, we can explicitly check for types to catch errors.
This contrasts with statically typed languages such as Java, where the type is associated with identifiers and only certain values are allowed to be stored in them.
Types are associated with values, but not with identifiers such as parameters or constants.
Defining functions in math:
f(x) = x^2
This follows the general pattern of name(formal_parameters) = body
In Scheme, this is written (define (name formal_parameters) body). For example:
(define (sum x y) (+ x y)) is equivalent to sum(x,y) = x + yThis is called with something like the following:
(sum 5 6) ; 5 and 6 are the argumentsdefine is a special form. It looks like a Scheme function, but its arguments are not necessarily evaluated, and this form may do something special normal functions cannot. define binds a name to an expression.
A definition can only be defined once - define cannot be used twice on the same identifier. However, redefinition is possible in the full Scheme language.
All operators in scheme are actually just functions: +, -, sqrt are predefined in the environment when the program starts. This means that they can be redefined, too.
Evaluate (* (- 6 4) (+ 3 2)):
(* (- 6 4) (+ 3 2))
(* 2 (+ 3 2))
(* 2 5)
10On paper:
\displaystyle \text{(* (- 6 4) (+ 3 2))} \implies \text{(* 2 (+ 3 2))} \implies \text{(* 2 5)} \implies 10
Functions are applied via substitution, as in math. There is only one solution to every possible expression - there is no ambiguity. Functions can only return one value.
Constants do not accept parameters, and simply have a constant value:
(define pi 3.1415926535)
(define density (/ mass volume))Orders of definitions are not important at this point. Definitions can be done in any order.
Constants are a special case of definitions. Constants are only evaluated once, and are not evaluated again upon substitution.
Inner scopes override outer scopes:
(define x 3)
(define (f x) (* x x))
(f 4) ; in the body of f, x is 4, since the parameter is in the inner scope and overrides x=3 in the outer scopeEvery function has its own scope. Scopes are environments where bindings exist.
Constants have various advantages:
Constants are sometimes called variables, but are generally not changed.
Unevaluated code is highlighted in black. Tests try to evaluate all possible code paths and all the highlighting should disappear.
Scheme programs are sequences of definitions and expressions.
Expressions are evaluated using substitution to produce values.
Expressions may use special forms such as define, which may not necessarily behave in the same way as normal expressions.
Programs are acts of communication: between person and computer, between person and same person in the future, and between person and others.
; comments start with a semicoolon and go on until the end of the lineBlock comments are comments that generally go on for multiple lines. These are, by convention, written with two semicolons:
;; block comments
;; generally apepar at the beginning of files
;; and before functionsEvery function must follow the design recipe - a development process that leaves behind a written explanation of development.
Design recipes result in robust and reliable functions that are easy to understand.
The five parts of the design recipe are, in order of submission:
Examples are similar to tests, but tests generally only show the function works while examples show people how to use it. There are usually more tests than examples.
Recommended order of execution:
Write a function that sums the squres of two numbers:
Contract:
;; sum-of-squares: Num Num -> Num
Purpose:
;; Purpose: produces the sum of squares of arg1 and arg24
Examples:
;; Examples:
(check-expect (sum-of-squares 3 4) 25)
(check-expect (sum-of-squares 0 2.5) 6.25)
Body:
(define (sum-of-squares arg1 arg2)
(+ (sqr arg1) (sqr arg2)))
Tests:
(check-expect (sum-of-squares -1 2) 5)
(check-expect (sum-of-squares 0.01 1000) 1000000.0001)
(check-expect (sum-of-squares 50 -28) 3284)
(check-expect (sum-of-squares 1/25 65) 4225.0016)Types used in contract (case sensitive):
Tests should be written after the code body. They should be small and focused with a clear purpose.
(check-expect (+ 1 2) 3) ; checks that a value is exactly equal to another
(check-within (sqrt 2) 1.414 0.001) ; checks that a value is equal to another within a tolerance
(check-error (/ 1 0) "/: division by zero") ;checks that a certain error occursThese are special forms and are evaluated at the end. A summary of the test results are shown in the interactions window.
Write a function that rounds to a given number of decimal places:
;; round-to: Num Int -> Num
;; Purpose: produces the value given rounded to a given number of decimal places
;; Examples:
(check-expect (round-to 1.25 1) 1.2)
(check-expect (round-to 23.45 -1) 20)
(define (round-to value decimal-places)
(/ (round (* value
(expt 10 decimal-places)))
(expt 10 decimal-places)))
;; Tests
(check-expect (round-to 1.25 1) 1.2) ; round down towards even number
(check-expect (round-to 1.35 1) 1.4) ; round up towards even number
(check-expect (round-to 12.3 5) 12.3) ; fewer decimal places than requested
(check-expect (round-to 12 0) 12) ; boundary conditionWe can put ... as a placeholder for the function body before actually writing the body.
If the contract is violated, the result may be undefined. For example, (round-to 3 0.5).
Starting with the Intermediate Student teaching language, helper functions that supplement a wrapper function need only a contract and purpose if the wrapper function obeys all of the following:
Mutually recursive functions, should be directly adjacent. They only need one set of examples and tests for all of them, but each one still neesd a contract and purpose.
The tests for the wrapper function, however, must fully test the helper function as well.
Templates are useful, but are not required to unless specifically requested to, or for custom data types.
See "Generative Recursion and the Design Recipe" for more concerns when using the design recipe with generative recursion.
Scheme represents Boolean values with the literals #t and #f (true and false are also usable in the Scheme teaching languages), representing true and false respectively.
The equality function (= x y) ((= Num Num) -> Boolean) tests whether two numbers are equal and results in a boolean value. (< x y) and (>= x y) behave similarly.
Predicates are expressions that result in Boolean values. They are, by convention, given names that end with a question mark. For example, (even? x) is clearly a predicate.
The most common Boolean operators are (and x y ...), (or x y ...), and (not x). They represent x \wedge y, x \vee y, and \neg x, respectively.
Scheme has no inequality (not-equals) operator. However, it can be implemented as follows: (not (= x y)).
Scheme uses short circuit evaluation. For and and or, if the result of the expression is known before the evaluation is complete, the rest is not evaluated:
or has a true argument, it knows that the result must be true regardless of other arguments - (or #t (/ 1 0)) will not give an error, since the division is never evaluated.and has a false argument, it knows that the result must be false regardless of other arguments - (and #f (/ 1 0)) will not give an error, since the division is never evaluated.This is made possible by and and or being special forms.
Many types have an equality predicate, like symbol=? and string=?, which should be used whenever possible. However, if the types of the operands are not known befrehand, (equal? x y ...) can be used to check that they are compatible types and that they have the same value. This does not work with inexact numbers.
Strings are denoted by double quotes: "CS135", "abc", "".
The length of a string is determined with (string-length x). We determine if a value is a string with the predicate function (string? x). We concatenate strings using (string-append x y ...)
String comparisons are done based on ASCII values.
Symbols are denoted by a single quote: 'symbol. A symbol represents a particular idea. They are used to define a finite set of values, each one with a name.
Symbols can only be compared, not manipulated like with strings.
Write a predicate function that checks if the input is a valid multiple choice answer:
;; valid-choice: Any -> Boolean
;; Purpose: produces true when the answer is one of "A", "B", "C", "D", false otherwise.
;; Examples:
(check-expect (valid-choice? 123) #f)
(check-expect (valid-choice? "C") #t)
(define (valid-choice? value)
(and (string? value)
(or (string=? value "A")
(string=? value "B")
(string=? value "C")
(string=? value "D"))))
;; Tests
(check-expect (valid-choice? "A") true)
(check-expect (valid-choice? "B") true)
(check-expect (valid-choice? "C") true)
(check-expect (valid-choice? "D") true)
(check-expect (valid-choice? "potato") false)
(check-expect (valid-choice? 123) false)The special form cond is used to write conditionaal expressions in Scheme. Each argument is a question/answer pair, where the question is a boolean expression:
(cond
[(< x 0) (- x)]
[(>= x 0) x])The above results in the absolute value of x.
Square brackets are used by convention. Square brackets are equivalent to parentheses in the teaching languages.
cond evaluates the question in each pair from top to bottom. As soon as one is true, its associated answer is evaluated and returned. If no pair matches, a runtime error is generated.
The last pair can use the question else to always match:
(cond
[(= 1 2) 3]
[(= 4 5) 6]
[else 7])Write a program that converts a numeric grade to a letter grade:
(define (convert-grade percentage advanced?)
(string-append
(cond
[(>= percentage 80) "A"]
[(>= percentage 70) "B"]
[(>= percentage 60) "C"]
[(>= percentage 50) "D"]
[else "F"])
(cond
[advanced? "+"]
[else ""])))When testing cond statements, test values on boundaries, and test values for each case. A statement with 4 cases might need 7 tests.
If a question is asked, we know that all the questions before it are false.
For example, we can simplify the following:
(cond
[(< grade 50) 'fail]
[(and (< grade 60) (>= 50)) 'poor]
[(>= grade 60) 'acceptable])Into the following:
(cond
[(< grade 50) 'fail]
[(< grade 60) 'poor]
[else 'acceptable])For conditional expressions, each question and answer should have one corresponding tests. The tests should be simple and directly test a particular answer. More tests are appropriate at boundary points as well.
In the above case, good test values would be 40, 50, 55, 60, and 70.
Every way each argument could be false needs to be false, and each one needs a test.
Some tests are based on the problem description - these are black-box tests. They are not based on anything in the code, such as implementation details.
Some tests are based on the code itself - these are white-box tests. They may check things like specific conditionals or boolean expressions.
Both types of testing are important.
Helper functions generalize similar expressions, and help avoid overly complex expressions. Helper functions should use meaningful names and must follow the design recipe.
Syntax is the way we're allowed to say things.
Semantics is the meaning of what we say.
Ambiguity is the property of sentence having multiple meanings.
Scheme programs must have correct syntax, meaningful semantics, and be unambiguous.
Grammars enforce syntax and avoid ambiguity. For example, an English sentence might be described as follows:
<sentence> = <subject> <verb> <object>The grammar is the syntactic model of the Scheme language.
A semantic model provides a way to predict the result of running any program.
Ellipses (...) can represent omissions, indicate patterns, and more. Pattern ellipses often represent multiple arguments or parameters.
A semantic model for Scheme is based on substitution, where we step through the program one substitution at a time:
(f ...) => (result of evaluating f(...))(define (f ...) e) occurs to the left, (f ...) => (e with substitution of parameters for arguments)(define f (lambda (x) x)) (f 5) => ((lambda (x) x) 5)(define x ...) occurs to the left, x => ...(define (f ...) ...)(cond [true e]) => e(cond [false e] ...) => (cond ...)(cond [else e]) => e(and false ...) => false(and true ...) => (and ...)(and) => true(or true ...) => true(or false ...) => (or ...)(or) => false(make-posn ...) => (make-posn ...)(make-posn 8 1) => (make-posn 8 1)(posn-x (make-posn 4 2)) => 4(posn? (make-posn 1 2)) => true(posn? 5) => false(cons 1 (cons 2 empty)) => (cons 1 (cons 2 empty))(list 1 2 3 4 5) => (list 1 2 3 4 5) in "Beginner Student with List Abbreviations" and above.(local [(define x ...) ...] ...) => (define (new name for x) ...) (body of local with x substituted with the new name for x)(local [(define (f ...) ...) ...] ...) => (define ((new name for f) ...) ...) (body of local with f substituted with the new name for f)(local [(define x y) (define y 5)] x) => (define x_0 y_0) (define y_0 5) x, which then results in an error.((lambda (x) (* x 2)) 5) => (* 5 2)Note that constant and function definitions are already in their simplest form.
These rules may differ from those in DrRacket's stepper feature.
Evaluating a program by stepping through is called tracing. In more complex programs, condensed traces are used - traces that can skip multiple steps to show only important parts.
Trace (term (- 3 1) (+ 1 2)) given (define (term x y) (* x (sqr y))):
(term (- 3 1) (+ 1 2))
=> (term 2 (+ 1 2))
=> (term 2 3)
=> (* 2 (sqr 3))
=> (* 2 9)
=> 18
=> (simplest form)Trace (cond [( > 3 4) x]):
(cond [( > 3 4) x])
=> (cond [false x])
=> (cond)
=> (error: no questions answered)The form of a program should mirror the form of the data.
A template is a general outline of code that consumes some type of data, that we can fill in to create a program.
Templates must appear after data definitions and before function definitions.
We start by making the template of a function, and then flesh out the template to create the finished function.
For every form of data, we create a template and use it to write functions that work with that type of data.
Templates should be commented out in Scheme code due to issues with MarkUs.
For example, a template for a list of a datatype called X might appear as follows:
;; my-listof-x-fn: (listof X) -> Any
;; (define (my-listof-x-fn lox)
;; (cond
;; [(empty? lox) ...]
;; [else (... (first lox) ...
;; (my-listof-x-fn (rest lox)) ...)]))The template must always produce Any since we don't know what type of data it will give.
Templates only require the contract, but functions written using a template still require the full design recipe.
Structures are a bundling of several values into one. They are complex values.
They work only with finite sets of values, and have a fixed size and field count.
For example, a structure might represent a product in an online store. It would store, for example, the name (String), product ID (Nat), price (Num), and availability (Boolean).
The two parts of a structure definition is the code and the data definition:
;; this is the code part
(define-struct product
(name product-id price availability))
;; this is the data definition part
;; A Product = (make-product String Nat Num Boolean) ; use CamelCase in data definitionsdefine-struct is a special form that defines a structure and a set of corresponding helper functions.
Here, Racket has made a number of functions automatically:
make-product - the constructor creates an instance of the struture, and is named make-{x}, where {x} is the structure name.product-name, product-product-id, product-price, product-availability - the selector functions obtain a particular field in the structure, and are named {x}-{y}, where {x} is the structure name and {y} is a field name.product? - the type predicate checks if a particular value is an instance of the structure, and are named {x}?, where {x} is the structure name.We can now work with this structure:
(define item (make-product "Television" 412 899.99 false))
(product? item) => true
(product-name item) => "Television"Structures are immutable - they cannot be changed. Once created, they remain the same.
Structures can contain structures.
In contracts, product structures can now be referenced as Product. For example: fake-product: String Boolean -> Product.
In the Scheme teaching languages, the Posn structure is defined, and is designed to represent a 2D coordinate.
;; distance: Posn Posn -> Num
;; Purpose: productes the Euclidean distance between `p1` and `p2`
;; Examples:
(check-expect (distance (make-posn 1 1) (make-posn 4 5)) 5)
(define (distance p1 p2)
(sqrt (+ (sqr (- (posn-x p2) (posn-x p1)))
(sqr (- (posn-y p2) (posn-y p1))))))In code, the structure name is lowercase. In contracts, data definitions, and a few other places, the name is written in CamelCase - each word is capitalized, and dashes are removed.
The template is written right after the data definition.
A template for a function that consumes a structure selects every field in the structure, even if the function itself doesn't use all of them. When we want to write a function, we write it based on the template:
;; product-fn: Product -> Any
(define (product-fn prod)
(... (product-name prod) ...
... (product-id prod) ...
... (product-price prod) ...
... (product-availability prod)))We use Any since we don't know what it returns yet. This needs to be reviewed later when actually writing the function.
We then fill in the placeholders, ..., to create the finished function:
(define (change-price prod price)
(make-product (product-name prod)
(product-id prod)
price
(product-availability prod)))For each new structure type, we need:
In contracts, we can use atomic data types as well as data definition names (capitalized).
It is best to define constants for tests and examples to represent structures, in order to shorten the code.
(define-struct movieinfo (name director))
;; A MovieInfo = (make-movieinfo String String)
(define-struct mp3info (title length))
;; An Mp3Info = (make-mp3info String Num)
;; THIS IS A UNION TYPE
;; A MultimediaInfo is one of:
;; * a MovieInfo
;; * an Mp3Info
;; THIS IS THE TEMPLATE FOR A FUNCTION THAT CONSUMES THE UNION TYPE
;; my-multimediainfo-fn: MultimediaInfo -> Any
(define (my-multimediainfo-fn info)
(cond [(movieinfo? info)
(... (movieinfo-name info) ...
... (movieinfo-director info) ...)]
[(mp3info? info)
(... (mp3info-title info) ...
... (mp3info-length info) ...)]))Now when we write a function, we use the template as a basis:
;; multimediainfo-identifier: MultimediaInfo -> String
;; WE CAN ALSO WRITE THE CONTRACT AS ;; multimediainfo-identifier: (union MovieInfo Mp3Info) -> String
(define (multimediainfo-identifier info)
(cond [(movieinfo? info)
(movieinfo-name info)]
[(mp3info? info)
(mp3info-title info)]))In the above code, the union data type MultimediaInfo (also known as (union MovieInfo Mp3Info)) represents either a MovieInfo or an Mp3Info.
Data definitions do not necessarily need to correspond to any structures in the code:
;; A Nat is an integer greater than or equal to zeroAbove we defined the natural number, but there is no data type in Scheme that corresponds to this. It is intended for the human readers.
(define (safe-make-posn x y)
(cond [(and (number? x) (number? y)) (make-posn x y)]
[else (error "numerical arguments required")]))
;; Tests
(check-expect (safe-make-posn 2 3) (make-posn 2 3))
(check-error (safe-make-posn 2 'abc) "numerical arguments required")We generally assume inputs are valid unless explicitly required to do error checking.
A recursive definition defines something in terms of itself.
A list is a compound data type. It is a recursively defined. They are known as "cons" types.
A list of 5 numbers is a number followed by a list of 4 numbers.
A list of 4 numbers is a number followed by a list of 3 numbers.
A list of 3 numbers is a number followed by a list of 2 numbers.
A list of 2 numbers is a number followed by a list of 1 numbers.
A list of 1 numbers is a number followed by a list of 0 numbers.
A list of 0 numbers is the base case and handled specially.
Lists in Scheme are similar to singly linked lists.
We have access only to the first element and the rest of the list.
empty - list of 0 elements.(cons element rest) (construct) - creates a list with value followed by rest.(first list) - obtains the first element of non-empty list list.(rest list) - obtains the (possibly empty) list of all the elements of non-empty list list, excluding the first.(empty? list) - determines whether list list is empty.(cons? value) - determines whether value value is a cons type (except for empty).(member? element list) - determines whether element is contained in list.(length list) - obtains the number of elements in list.(cons 'a (cons 'b (cons 'c empty)))This is a list of 'a, 'b, and 'c, in that order.
To append lists, we cannot use (cons list1 list2). This would simply create a list with the first element being list1, and the rest being list2. For list appending, we can use the built-in function append.
A list is one of:
empty - the empty list.(cons element list) - a recursive list definition.For each new list type, we need:
The template is written right after the data definition. It is based on the data definition and so appears generally as a cond expression with one qeustion/answer pair for each possibility.
Self-referential data definition clauses lead to recursion in the template, while base cases do not.
Example of a list of strings:
;; A ListOfStrings is either
;; * empty or
;; * (cons String ListOfStrings)
;; Template for ListOfStrings
;; my-los-fn: ListOfStrings -> Any
(define (my-los-fn los)
(cond [(empty? los) ...] ; base case
[else (... (first los) ...
... (my-los-fn (rest los) ...))]))We can write ListOfStrings (or alternatively, (listof String)) in data definitions. The (listof X) notation is shorter and does not require any other definitions. Here, X represents any type, even a list or structure.
The implicit template when using (listof X) is as follows:
;; my-listof-X-fn: (listof X) -> Any
(define (my-listof-X-fn lst)
(cond [(empty? lst) ...]
[else (... (first lst)
... (my-listof-X-fn (rest lst)) ...)]))Sometimes we need non-empty lists. A data definition could be written as (ne-listof X), or using a definition like the following:
;; A NeListOfStrings is either
;; * (cons String empty) or
;; * (cons String NeListOfStrings)
;; Template for NeListOfStrings
;; my-nelos-fn: NeListOfStrings -> Any
(define (my-nelos-fn nelos)
(cond [(empty? (rest nelos)) ; base case
(... (first nelos) ...)]
[else (... (first nelos) ...
... (my-los-fn (rest nelos) ...))]))Function that makes an acronym from a list of strings:
;; make-acronym: ListOfStrings -> String
;; Purpose: produces an acronym formed by the first letter of each of the elements of `strings`.
;; Examples:
(check-expect (make-acronym (cons "Kentucky" (cons "Fried" (cons "Chicken" empty)))) "KFC")
(define (make-acronym strings)
(cond [(empty? strings) ""]
[else (string-append (substring (first strings) 0 1)
(make-acronym (rest strings)))]))Recursive definitions should have a base case. This allows the recursion to eventually terminate.
It should also always be possible to get closer to the base case upon each step. It may not have to happen for every call, but it must eventually reach the base case.
If either of these are not true, it may result in infinite recursion, when the function calls itself indefinitely.
Structural recursion, as opposed to generative recursion, is recursion guided by the data definition - the form of the code matches the form of the data definition.
In other words, our functions should follow the template closely and work with the first element of the list and recurse only with the rest of the list.
Pure structural recursion requires that at every call of the recursive function, all parameters are either unchanged or one step closer to the base case. The parameters should be driving the recursion, while everything else stays unchanged.
Mutual recursion is recursion involving two or more functions that call each other recursively. It occurs when we have data definitions that refer to each other.
Care must be taken to ensure that the base case is eventually reached. Data definitions can be mutually recursive:
A NestedThing is one of:
* empty
* (listof OtherThing)
A OtherThing is one of:
* Symbol
* (list Symbol NestedThing)A condensed trace is a way of writing traces that skips the excessive detail that would result from a full trace. Here, we skip steps to show only the most important information.
It is always important to specify whether a trace is condensed or full.
For example, we might do a condensed trace of a function as follows:
(make-acronym (cons "Kentucky" (cons "Fried" (cons "Chicken" empty))))
=> (string-append "K" (make-acronym (cons "Fried" (cons "Chicken" empty))))
=> (string-append "K" (string-append "F" (make-acronym (cons "Chicken" empty))))
=> (string-append "K" (string-append "F" (string-append "C" (make-acronym empty))))
=> (string-append "K" (string-append "F" (string-append "C" "")))
=> "KFC"This better shows the way the application of the recursive function leads to the application of that function to a smaller list, until the base case is reached.
There aren't strict rules for condensed traces, since everyone might have a different idea of what is an important step. It is possible to condense more or less depending on whether it makes the trace more clear.
Strings are used to represent text. In Scheme, strings are actually sequences of characters.
(string->list "abc ") -> (cons #\a (cons #\b (cons #\c (cons #\space empty))))
(list->string (cons #\a (cons #\b (cons #\c (cons #\space empty))))) -> "abc "Characters are denoted by #\a, where a represents the character value - in this case, a lowercase A.
;; replace-space: String -> String
;; Purpose: produces a copy of `str` where all spaces are replaced by underscores.
;; Examples:
(check-expect (replace-space "") "")
(check-expect (replace-space "CS 135") "CS_135")
;; THIS IS A WRAPPER FUNCTION; IT MAINLY CALLS ANOTHER FUNCTION TO DO THE ACTUAL WORK
(define (replace-space str)
(list->string (replace-space-list (string->list str))))
;; Tests:
;; NOT INCLUDED FOR BREVITY
;; replace-space-list: (listof Char) -> (listof Char)
;; Purpose: produces a copy of `loc` where all #\space is replaced by #\_
;; Examples:
(check-expect (replace-space-list empty) "")
(check-expect (replace-space (cons #\C (cons #\S (cons #\space (cons #\1 (cons #\3 (cons #\5 empty)))))))
(cons #\C (cons #\S (cons #\_ (cons #\1 (cons #\3 (cons #\5 empty)))))))
(define (replace-space-list loc)
(cond [(empty? loc) empty]
[else (cons (cond [(char=? (first loc) #\space) #\_]
[else (first loc)])
(replace-space-list (rest loc)))]))
;; Tests:
;; NOT INCLUDED FOR BREVITYTemplate for a Polygon:
;; A Polygon is one of:
;; * empty
;; * (cons Posn Polygon)
(define (my-polygon-fn poly)
(cond [(empty? poly) ...]
[else (... (first poly) ...
... (my-polygon-fn (rest poly)) ...)]))However, we know that (first poly) is a Posn. So we should refer to its template:
(define (my-polygon-fn poly)
(cond [(empty? poly) ...]
[else (... (my-posn-fn (first poly)) ...
... (my-polygon-fn (rest poly)) ...)]))
(define (my-posn-fn p)
(... (posn-x p) ...
... (posn-y p) ...))Alternatively, it is possible to combine the two templates:
(define (my-polygon-fn poly)
(cond [(empty? poly) ...]
[else (... (... (posn-x p) ...
... (posn-y p) ...) ...
... (my-polygon-fn (rest poly)) ...)]))A data definition for Nat:
;; A Nat is one of:
;; * 0
;; * (add1 Nat)
;; NATURAL NUMBERS START AT 0 IN COMPUTER SCIENCE AND LOGIC
;; TEMPLATE FOR NATURAL NUMBERS
(define (my-nat-fn n)
(cond [(<= n 0) ...] ; WE USE <= HERE INSTEAD OF zero? IN ORDER TO CATCH NEGATIVE OR FRACTIONAL INPUTS. THIS IS DEFENSIVE PROGRAMMING
[else (... (my-nat-fn (sub1 n)) ...)]))
;; WE USE THE INVERSE OF THE `add1` FUNCTION TO GET THE NUMBER `x` SUCH THAT `(add1 x)` IS `n`A natural number like 5 would therefore be representable as something like (add1 (add1 (add1 (add1 (add1 0))))). This is similar to the recursive formulation of a list.
Since in each call we need to get closer to the base case, we need to invert the function, so we use sub1 to get closer to the base case.
This isn't the usual way we'd think of numbers, but writing it in the form of a data definition allows us to make good templates that consume this type of data.
Countdown example:
;; countdown-to: Int Int -> (listof Int)
;; Purpose: produces a list of integers from `start` to `end`
;; Examples:
;; NOT INCLUDED FOR BREVITY
(define (countdown-to start end)
(cond [(<= start end) (cons end empty)]
[else (cons start (countdown-to (sub1 start) end))]))We can denote subsets of certain sets using subscript notation:
In data definitions, we can represent this as follows:
;; ascii->listofchar: Nat[<256] Nat[<256] -> (listof Char)Here, Nat[<256] is equivalent to \mathbb{N}_{<256}, or natural numbers less than 256. Other possible uses of the square braket notation are Int[>=20], String[<"abc"].
Primality test:
;; prime?: Nat[>0] -> Boolean
;; Purpose: produces true if `n` is prime and false otherwise
;; Examples:
(check-expect (prime? 1) false)
(check-expect (prime? 2) true)
(check-expect (prime? 4) false)
(define (prime? n)
(not (or (= n 1)
(has-factors? 2 n))))
;; Tests:
;; OMITTED FOR BREVITY
;; has-factors?: Nat[>1] Nat[>0] -> Boolean
;; Purpose: produces true if any numbers between `factor` and one less than `n` divide `n`, and false otherwise
;; Examples:
;; OMITTED FOR BREVITY
(define (has-factors? factor n)
(cond [(>= factor n) #f]
[(zero? (remainder n factor)) #t]
[else (has-factors? (add1 factor) n)]))
;; Tests:
;; OMITTED FOR BREVITYConsider a basic list sorting function template:
(define (sort list)
(cond [(empty? list) ...]
[else (... (first list) ... (sort (rest list)) ...)]))Now we need to do something with the first element of the list and the (assumed sorted) rest of the list. What we can do is use insert, a helper function that inserts an element into a list in sorted order:
(define (sort list)
(cond [(empty? list) empty]
[else (insert (first list) (sort (rest list)))]))We simply need to assume that when we call sort, we will get a sorted list, and that insert will correctly insert the element in sorted order.
We start with a template for the insertion function:
;; insert: Any (listof Any) -> (listof Any)
(define (insert element list)
(cond [(empty? list) ...]
[else (... (first list) ... (insert element (rest list)) ...)]))We can assume the list is in sorted order since it will only ever be called on the result of sort. So we just need to put it at the beginning if it's already in the proper place, or recurse to put it in the correct place in the rest of the list:
;; insert: Num (listof Num) -> (listof Num)
;; Purpose: produces a list equal to `list` except with `element` inserted in sorted order
;; Examples:
(check-expect (insert 1 (list 2 3)) (list 1 2 3))
(check-expect (insert 2 (list 1 3)) (list 1 2 3))
(define (insert element list)
(cond [(empty? list) (cons element empty)]
[(<= element (first list)) (cons element list)]
[else (cons (first list) (insert element (rest list)))]))
;; Tests:
(check-expect (insert 1 (list 2 3)) (list 1 2 3))
(check-expect (insert 2 (list 1 3)) (list 1 2 3))
(check-expect (insert 2 empty) (list 2))Together, this forms a sorting function based on the insertion sort algorithm.
Lists can be written in a few ways. All of the following are equivalent:
(cons 3 (cons (cons 'a (cons 'b empty)) (cons "test" (cons #\a empty))))(list 3 (list 'a 'b) "test" #\a)'(3 (a b) "test" #\a) - only available starting in "Beginning Student with List Abbreviations". In the quoted part, only symbols, numbers, strings, and lists are allowed. No quotes are used inside the outer brackets. '() is the same as empty.We use list for lists of fixed size, where the length of the list is known beforehand. We still need cons for constructing a list of variable length.
In data definitions, we can use notation like (list String Num) to represent a list with the first element being a string, and the second a number.
We can simulate structures with lists - each element could hold a field, and the list itself would be a collection of fields, just like a structure. This could be useful for things like type unions, where instead of writing very similar code for two different types of structures, we simply use lists for both and assume the needed fields are at the same place in both types of lists.
Beginning Student with List Abbreviations also has extra functions for working with lists:
(second list) is equivalent to (first (rest list)). It obtains the second element of a list.(third list) is equivalent to (first (rest (rest list))). It obtains the third element of a lsit.(eighth list) is equivalent to (first (rest (rest (rest (rest (rest (rest (rest list)))))))). It obtains the eighth element of a list.Dictionaries are abstract data types (not a primitive type, but a commonly used pattern). They are associations of keys with values.
A telephone directory is a dictionary - the names are the key, which we use to look up phone numbers, which are the values.
Keys must be unique in a dictionary - there can be no duplicates. However, values do not need to be unique.
The most important operations on dictionaries are:
The actual implementation of the dictionary is dependent on what we want from it. For example, some implementations might have faster lookup but slower add and remove.
This is simply a list of key/value pairs:
;; An AL is one of:
* empty
* (cons (list Num String) AL)
;; Template for AL:
;; my-al-fn: AL -> Any
(define (my-al-fn al)
(cond [(empty? al) ...]
[else (... (first (first al)) ...
... (second (first al)) ...
... (my-al-fn (rest al)) ...)]))
;; OR USE (listof (list Num String))Now we can implement a few operations on this data type:
;; al-lookup: AL Num -> (union String false)
;; Purpose: produces the value associated with `key` in `al` if it exists, and false otherwise
;; Examples:
;; OMITTED FOR BREVITY
(define (al-lookup al key)
(cond [(empty? al) false] ; false represents the element not being found
[(= key (first (first al))) (second (first al))]
[else (al-lookup (rest al) key))]))
;; Tests:
;; OMITTED FOR BREVITY
;; al-remove: AL Num -> AL
;; Purpose: produces an AL equal to `al` without the key `key`
;; Examples:
;; OMITTED FOR BREVITY
(define (al-remove al key)
(cond [(empty? al) empty]
[(= key (first (first al)))
(al-remove (rest al) key)]
[else (cons (first al) (al-remove (rest al) key))]))
;; Tests:
;; OMITTED FOR BREVITYConsider an appending function:
;; my-append: (listof Any) (listof Any) -> (listof Any)
(define (my-append list1 list2)
(cond [(empty? list1) list2]
[else (cons (first list1) (my-append (rest list1) list2))]))This uses only structural recursion - list2 does not change between calls.
Note that the run time of this function depends on the length of list1. If list1 is very large, the function may need a significant amount of time to run.
If both lists are of the same length, we can assume that the first list will be empty if and only if the second is.
Consider a dot product function:
;; dot-product: (listof Num) (listof Num) -> Num
(define (dot-product vec1 vec2)
(cond [(empty? vec1) 0]
[else (+ (* (first list1) (first list2))
(dot-product (rest vec1) (rest vec2)))]))There are four possible cases to consider if the two lists are of differing lengths.
This is reflected in the template:
;; my-double-list-fn: (listof Any) (listof Any) -> Any
(define (my-double-list-fn list1 list2)
(cond [(and (empty? list1) (empty? list2)) ...]
[(and (empty? list1) (cons? list2)) ...]
[(and (cons? list1) (empty? list2)) ...]
[else ...]))Consider an element count test function:
;; minimum-occurrences?: (listof Any) Any Nat -> Boolean
;; Purpose: produces true if `value` appears in `list` at least `count` times, and false otherwise
;; Examples:
;; OMITTED FOR BREVITY
(define (minimum-occurrences? list value count)
(cond [(<= count 0) true]
[(empty? list) false]
[(equal? value (first list))
(minimum-occurrences? (rest list) (sub1 count))]
[else (minimum-occurrences? (rest list) count)]))
;; Tests:
;; OMITTED FOR BREVITYConsider a list comparison function:
;; list=?: (listof Any) (listof Any) -> Boolean
;; Purpose: produces true if `list1` and `list2` are equal, and false otherwise
;; Examples:
;; OMITTED FOR BREVITY
(define (list=? list1 list2)
(cond [(and (empty? list1) (empty? list2)) #t]
[else (and (cons? list1) (cons? list2)
(equal? (first list1) (first list2))
(list=? (rest list1) (rest list2)))]))
;; Tests:
;; OMITTED FOR BREVITYStructural recursion is based on a recursive data definition - it is driven by and follows the form of the data definition.
On each call, all parameters must be either unchanged, or one step closer to a base case according to the data definition.
However this can have disadvantages. Consider a function finding the maximum element of a list, written in pure structural recursion style:
;; list-max: (ne-listof Num) -> Num
(define (list-max list)
(cond [(empty? (rest list)) (first list)]
[(>= (first list) (list-max (rest list))) (first list)]
[else (list-max (rest list))]))In the worst case - a strictly increasing list - the function will call itself twice for each step, which means it takes exponential time based on the length of the list.
This is similar to pure structural recursion, but it can also have parameters with partial answers.
Consider a function finding the maximum element of a list, written in accumulative recursion style:
;; list-max-helper: (listof Num) Num -> Num
(define (list-max-helper list partial-max)
(cond [(empty? list) partial-max]
[(>= (first list) partial-max)
(list-max-helper (rest list) (first list))]
[else
(list-max-helper (rest list) partial-max)]))
;; list-max: (ne-listof Num) -> Num
(define (list-max list)
(list-max-helper (rest list) (first list)))Here, we recurse at most once per call. The extra parameter allows us to move extra data downwards through the calls so we don't need to restructure it to move data upwards only.
We can use as many extra parameters as needed. The key is that we make extra data available to the callee.
Generally, the accumulatively recursive function needs a wrapper function to start it off with initial values for the extra parameters.
Consider a function that reverses a list:
;; list-reverse: (listof Any) -> (listof Any)
(define (list-reverse list current)
(cond [(empty? list) current]
[else (list-reverse (rest list) (cons (first list) current))]))Note that reverse is actually a built-in function that has the same functionality, though it doesn't require the second parameter.
We use the function as follows:
(list-reverse '(a b c) empty) -> '(c b a)Generative/general recursion allows us to get closer to a base case in any way we want - we can calculate the parameters freely.
If there is even just one generated parameter, it is generative recursion.
Consider the GCD for m > 0:
We do not have a data definition. Here, we use generative recursion to create a function to compute the GCD of two numbers:
(define (gcd n m)
(cond [(zero? m) n]
[else (gcd m (remainder n m))]))This is written in generatively recursive style because the arguments are generated by computation on n and m.
Generative recursion is easier to get wrong, harder to debug, and harder to reason about.
A tree is an abtract data type, like a dictionary. It is a recursive data structure made up of nodes:
Nodes can also store their own value. This value is known as a label.
;; A Tree is one of:
;; * (Leaf-constructor Value)
;; * (Node-constructor Tree Tree)Every node is also a tree in itself. If we look at a node and its descendents as a tree, we call it a subtree in this context.
For example, we can represent arithmetic expressions as trees. Consider (4 + 1) * (7 - (6 / 2)):
If node A refers to node B, and node B refers to node C, and so on, until node Z, then nodes B to Z are descendents of A, and nodes A to Y are ancestors of Z.
A node is its own ancestor and descendent.
If node A refers to node B, A is the parent/direct ancestor of B, and B is the child/direct descendent of A.
If two nodes have the same parent, then they are siblings.
Additional constraints for trees are:
The very top node is known as the root node.
Trees have various classifying properties:
So for the binary arithmetic expression above:
We can use the following data definition for a binary arithmetic expression tree:
(define-struct bae (operation arg1 arg2))
;; A BinExp is one of: ;; * Num ;; * (make-bae Symbol BinExp BinExp)
So the expression above would be representable as (make-bae '* (make-bae '+ 4 1) (make-bae '- 7 (make-bae '/ 6 2))).
Now we can write a template for this:
;; binexp-fn: BinExp -> Any
(define (binexp-fn tree)
(cond [(number? tree) ...]
[(bae? tree) (... (bae-operation tree) ...
(bae-arg1 tree) ...
(bae-arg2 tree) ...)]))Since we know that (bae-arg1 tree) and (bae-arg2 tree) are both of type BinExp, we can apply the BinExp processing function on it:
;; binexp-fn: BinExp -> Any
(define (binexp-fn tree)
(cond [(number? tree) ...]
[(bae? tree) (... (bae-operation tree) ...
(binexp-fn (bae-arg1 tree)) ...
(binexp-fn (bae-arg2 tree)) ...)]))Now we can make functions consuming BinExp values, such as an evaluator:
(define (eval ex)
(cond [(number? ex) ex]
[(bae? ex) (cond [(symbol=? (bae-operation ex) '*)
(* (eval (bae-arg1 ex)) (eval (bae-arg2 ex)))]
[(symbol=? (bae-operation ex) '+)
(+ (eval (bae-arg1 ex)) (eval (bae-arg2 ex)))]
[(symbol=? (bae-operation ex) '/)
(/ (eval (bae-arg1 ex)) (eval (bae-arg2 ex)))]
[(symbol=? (bae-operation ex) '-)
(- (eval (bae-arg1 ex)) (eval (bae-arg2 ex)))])))Traversal simply means going through every node of a tree.
There are two broad types of traversal:
Depth-first traversal is quite natural to implement recursively. As a result, it is used quite often in this course.
We can represent traversal as a flat list of the nodes in the tree, in the order that they were traversed.
When we do traversal, there is also a question of the order in which we deal with children of an internal node and the node itself. For example, we can process the tree (+ 1 2) in the following ways:
+, then 1 and 2 - this is called pre-order traversal. The result would be '+ 1 2.1, then +, and then 2 - this is called in-order traversal. The result would be 1 '+ 2.1, 2, and then + - this is called post-order traversal. The result would be 1 2 '+.+, and then all the nodes on the same level as 1 and 2 - this is called level-order traversal. In this case, it gives the same result as pre-order traversal.We can implement pre-order traversal pretty simply:
traverse-binexp: BinExp -> (listof (union Symbol Num))
(define (traverse-binexp tree)
(cond [(number? tree) (list tree)] ; leaf node
[(bae? tree)
(append (bae-operation tree)
(traverse-binexp (bae-arg1 tree))
(traverse-binexp (bae-arg2 tree)))]))In a similar way, in-order and post-order traversal can be done by switching the order of the arguments to append.
Dictionaries were previously implemented using an association list of two-element lists. However, this had the problem that it could potentially require us to search through thte entire list to lookup a value.
We could instead put the key-value pairs into a binary tree:
(define-struct node (key val left right))
;; A binary tree (BT) is one of:
;; * empty
;; * (make-node Num String BT BT)Here, if a node has empty as its left and right branches, it is a leaf node. Otherwise, it refers to other values and is an internal node.
Template for a binary tree:
;; my-bt-fn: BT -> Any
(define (my-bt-fn tree)
(cond [(empty? tree) ...]
[else (... (node-key tree) ...
(node-val tree) ...
(my-bt-fn (node-left tree)) ...
(my-bt-fn (node-right tree)) ...)]))Consider a function that counts the number of nodes equal to a certain value in a tree:
;; count-bt-equal: BT Any -> Any
;; Purpose: returns the number of nodes in `tree` equal to `value`
;; Examples:
;; OMITTED FOR BREVITY
(define (count-bt-equal tree value)
(cond [(empty? tree) ...]
[else (+ (cond [(equal? (node-val tree) value) 1]
[else 0])
(count-bt-equal (node-left tree))
(count-bt-equal (node-right tree)))]))
;; Tests:
;; OMITTED FOR BREVITYWe can search through this type of tree pretty easily - if not found or empty, search through the left and right subtrees recursively.
However, this is no more efficient than an association list - we could still potentially search through the whole thing in order to lookup a value.
Draw the tree (make-node 5 'a (make-node 1 'b empty empty) (make-node 6 'c empty (make-node 14 'd empty empty))):
5
/ \
1 6
\
14We do not represent the value field - only keys matter here.
We can add a constraint that makes this much more efficient:
(define-struct node (key val left right))
;; A binary search tree (BST) is one of:
;; * empty
;; * (make-node Num String BST BST)
;; And satisfies the ordering property:
;; * every key in `left` is less than `key`
;; * every key in `right` is greater than `key`The ordering property allows us to make the following assumptions:
This is very useful for operations like searching and insertion.
Searching is made more efficient because we can use these assumptions to get a faster algorithm:
Basically, we avoid doing one recursive call each time - so we would only need to make as many recursive calls as the tree is deep.
If a tree is nicely balanced (internal nodes try to have both subtrees non-empty as much as possible), we can do a search in only \log_2 n calls, where n is the number of leaf nodes.
Otherwise, degenerate trees such as one with all internal nodes having empty left or right subtrees are no more efficient than an association list.
This can be implemented as follows:
;; search-bst: Num BST -> (union Any false)
;; Purpose: produces the value associated with `key` in `tree`
;; Examples:
;; OMITTED FOR BREVITY
(define (search-bst key tree)
(cond [(empty? tree) false]
[(= key (node-key tree)) (node-val tree)]
[(< key (node-key tree)) (search-bst key (node-left tree))]
[(> key (node-key tree)) (search-bst key (node-right tree))]))
;; Tests:
;; OMITTED FOR BREVITYWe can add an element to a binary search tree in a similar fashion:
This can be implemented as follows:
;; insert-bst: Num Any BST -> BST
;; Purpose: produces `tree` with `key` associated with `value`
;; Examples:
;; OMITTED FOR BREVITY
(define (insert-bst key value tree)
(cond [(empty? tree) (make-node key value empty empty)]
[(= key (node-key tree)) (make-node key value (node-left tree) (node-right tree))]
[(< key (node-key tree)) (make-node (node-key tree) (node-val tree) (insert-bst key value (node-left tree)) (node-right tree))]
[(> key (node-key tree)) (make-node (node-key tree) (node-val tree) (node-left tree) (insert-bst key value (node-right tree)))]))
;; Tests:
;; OMITTED FOR BREVITYRemoving is a bit more complex. There are three cases to consider:
This can be implemented as follows:
;; remove-min-bst: Node -> BST
;; DESIGN RECIPE OMITTED FOR BREVITY
(define (remove-min-bst tree)
(cond [(empty? (node-left tree)) empty]
[else (make-node (node-key tree) (node-val tree)
(remove-min-bst (node-left tree))
(node-right tree))]))
;; min-bst: Node -> Node
;; DESIGN RECIPE OMITTED FOR BREVITY
(define (min-bst tree)
(cond [(empty? (node-left tree)) tree]
[else (min-bst (node-left tree))]))
;; remove-bst: Num BST -> BST
;; Purpose: produces `tree` without the node with key `key`
;; Examples:
;; OMITTED FOR BREVITY
(define (remove-bst key tree)
(cond [(empty? tree) empty]
[(= key (node-key tree))
(cond [(and (empty? (node-left tree)) ; leaf node
(empty? (node-right tree)))
empty])]
[(empty? (node-left tree)) (node-right tree)] ; right child only
[(empty? (node-right tree)) (node-left tree)] ; left child only
[else ; two children
(make-node (node-key (min-bst (node-right tree)))
(node-val (min-bst (node-right tree)))
(node-left tree)
(remove-min-bst (node-right tree))]
[(< key (node-key tree))
(make-node (node-key tree) (node-val tree)
(remove-bst key (node-left tree))
(node-right tree))]
[(> key (node-key tree))
(make-node (node-key tree) (node-val tree)
(node-left tree)
(remove-bst key (node-right tree)))]))
;; Tests:
;; OMITTED FOR BREVITYBinary trees are useful, but it is occasionally useful to allow a larger, fixed number of children. For example, a ternary tree has at most 3 elements.
Here, we would modify our implementation to use a different definition for a node structure with additional fields.
However, if there could be any number of children, we should represent a node's subtrees as a list.
Scheme expressions could be represented using one of these general trees:
(define-struct ae (operation args))
;; An arithmetic expression (AE) is one of:
;; * Num
;; * (make-ae Symbol (listof AE))
;; Template for AE:
;; my-ae-fn: AE -> Any
(define (my-ae-fn ae)
(cond [(number? ae) ...]
[else (... (ae-operation ae) ...
(my-ae-args-fn (ae-args ae)) ...)]))
;; my-ae-args-fn: (listof AE) -> Any
(define (my-ae-args-fn args)
(cond [(empty? args) ...]
[else (... (my-ae-fn (first args)) ...
(my-ae-args-fn (rest args)) ...)]))Note the mutually recursive data definition results in a mutually recursive set of functions.
Now we can write an evaluator for arithmetic expressions:
;; eval: AE -> Num
;; DESIGN RECIPE OMITTED FOR BREVITY
(define (eval ae)
(cond [(number? ae) ae]
[else (apply (ae-operation ae) (ae-args ae))]))
;; apply: (listof AE) -> Num
;; DESIGN RECIPE OMITTED FOR BREVITY
(define (apply operation args)
(cond [(empty? args) (cond [(symbol=? operation '*) 1]
[(symbol=? operation '+) 0])]
[(symbol=? operation '*)
(* (eval (first args)) (apply operation (rest args)))]
[(symbol=? operation '+)
(+ (eval (first args)) (apply operation (rest args)))]))However, we could also write the expression with just lists: '(+ 1 2 (* 4 5 6) 3). The data definition would look something like this:
;; An arithmetic expression (AE) is one of:
;; * Num
;; * (cons Symbol (listof AE))
;; Template for AE:
;; my-ae-fn: AE -> Any
;; DESIGN RECIPE OMITTED FOR BREVITY
(define (my-ae-fn ae)
(cond [(number? ae) ...]
[else (... (first ae) ...
(my-ae-args-fn (rest ae)) ...)]))
;; SEE DEFINITION OF my-ae-args-fn ABOVEThe evaluator function for this representation would look something like this:
;; eval: AE -> Num
;; DESIGN RECIPE OMITTED FOR BREVITY
(define (eval ae)
(cond [(number? ae) ae]
[else (apply (first ae) (rest ae))]))
;; SEE DEFINITION OF apply ABOVENote that apply did not change when the data definition did not change.
This is the beginnings of a full Scheme interpreter.
Nested lists can also be represented as leaf-labelled trees. Leaves correspond to list elements, and internal nodes correspond to nesting:
'(1 (2 3) 4)
*
/|\
/ * \
/ / \ \
1 2 3 4Note that the empty list is simply a single node:
'()
(nothing here)Also, a tree containing empty has an empty tree as its value:
'(1 empty 2)
*
/|\
1 2The data definition looks like this:
A NestedList is one of:
* empty
* (cons Num NestedList)
* (cons NestedList NestedList)
;; Template for NestedList
;; my-nestedlist-fn: NestedList -> Any
(define (my-nestedlist-fn list)
(cond [(empty? list) ...]
[(number? (first list))
(... (first list) ...
(my-nestedlist-fn (rest list)) ...)]
[else (... (my-nestedlist-fn (first list)) ...
(my-nestedlist-fn (rest list)) ...]))Consider a list flattening function:
;; flatten: NestedList -> Any
(define (flatten list)
(cond [(empty? list) empty]
[(number? (first list))
(cons (first list) (flatten (rest list)))]
[else (append (flatten (first list))
(flatten (rest list)))]))Consider now a representation for algebraic expressions. These are simply the expressions we saw earlier, except now with support for variables. For example, '(+ 4 #\x (* 5 3 #\x)):
An AlgExp is one of:
* Num
* Char ;WE USE CHAR HERE BECAUSE AN OPERATOR IS A SYMBOL AND IT WOULD BE CONFUSING TO HAVE SYMBOLS MEAN TWO DIFFERENT THINGS
* (cons Symbol (listof AlgExp))
;; my-listof-algexp-fn: (listof AlgExp) -> Any
(define (my-listof-algexp-fn alglist)
(cond [(empty? alglist) ...]
[else (... (my-algexp-fn (first alglist)) ...
(my-listof-algexp-fn (rest alglist)))]))
;; my-algexp-fn: AlgExp -> Any
(define (my-algexp-fn alg)
(cond [(number? alg) ...]
[(char? alg) ...]
[else (... (first alg) ...
(my-listof-algexp-fn (rest alg)) ...)]))Now we can write a substitution function:
;; substitute-list: (listof AlgExp) Char Num -> (listof AlgExp)
;; Purpose: produces `alglist` where `var` is replaced by `value`
;; Examples:
;; NOT REQUIRED DUE TO MUTUAL RECURSION
(define (substitute-list alglist var value)
(cond [(empty? alglist) empty]
[else (cons (substitute (first alglist) var value)
(substitute-list (rest alglist) var value))]))
;; Tests:
;; NOT REQUIRED DUE TO MUTUAL RECURSION
;; substitute: AlgExp Char Num -> AlgExp
;; Purpose: produces `alg` where `var` is replaced by `value`
;; Examples:
(check-expect (substitute '(+ 1 #\x 2 #\y #\x) #\x 5) '(+ 1 5 2 #\y 5))
(check-expect (substitute #\x #\x 5) 5)
(define (substitute alg var value)
(cond [(number? alg) alg]
[(char? alg) (cond [(char=? alg var) value]
[else alg])]
[else (cons (first alg)
(substitute-list (rest alg)))]))
;; Tests:
;; OMITTED FOR BREVITYGeneral trees are useful for representing any sort of nested data. For example, a book might be represented as follows:
'(chapter (section (paragraph "First sentence."
"Second sentence.")
(paragraph "Continued."))
(section ...)
...)Only available beginning with Intermediate Student. Not part of Standard Scheme, but there are similar constructs available there which are simpler, but not as general.
Definitions have to this point been made at the "top level", outside of any expressions.
However, there is also a special form local, which allows us to make definitions inside an expression and use them only inside that expression:
(local [(define a x) (define b y) (define c z) ...] ; we use square brackets by convention to improve readability
...) ; do something with those definitionsIn local definition, definitions behave like the those in the top level. We can even define functions.
Consider Heron's formula, used for calculating the area of a triangle with side lengths a, b, and c$: A = \sqrt{s(s - a)(s - b)(s - c)} where s = \frac{a + b + c}{2}.
(define (t-area a b c)
(sqrt (* (/ (+ a b c) 2)
(- (/ (+ a b c) 2) a)
(- (/ (+ a b c) 2) b)
(- (/ (+ a b c) 2) c))))The repeated calculation of (/ (+ a b c) 2) is messy. We can instead use local:
(define (t-area a b c)
(local [(define s (/ (+ a b c) 2))]
(sqrt (* s (- s a) (- s b) (- s c))))This is significantly more readable and more efficient.
Note that we can also refer to earlier definitions:
(define (t-area a b c)
(local [(define sum (+ a b c))
(define s (/ sum 2))]
(sqrt (* s (- s a) (- s b) (- s c)))))Here, we can reference sum from a definition right after it. Note that the order is significant - definitions must be defined before they are used.
A binding occurrence of a name is an occurrence of the name when it is used as a definition or a formal parameter to a function.
The bound occurrences associated with a binding occurrence and a name are the occurrences of the name that correspond to the binding occurrence.
The scope is where the binding takes effect. This is generally the area where it can be referenced, and excludes the "holes" (nested scopes) where the binding is shadowed.
Definitions are resolved from the innermost scope to the outermost scope. Definitions are said to shadow definitions in the parent scope if a name in the inner definition is the same as one in the outer one. In this case, the inner one takes precedence and the parent one is shadowed.
Lexical scoping means that binding resolution is based on where the scope is textually located in the code. So the parent scope of a given scope is the scope that is textually surrounding it. For example, the scope of variables in a local is exactly the area within the brackets surrounding local. This contrasts with dynamic scoping, where the parent scope can change depending on use.
When we define something in a local scope that has the same name as something in the parent scope (this is not recommended), references to that name in the local scope reference the local definition, while references outside are unchanged.
The global/top-level scope is the scope of top-level definitions. All programs initially statrt off in the global scope.
The stepping rules for local are the most complex we have seen so far:
local with its body expression.This all happens in one step.
Consider the following:
(define s 'blah)
(local [(define sum (+ a b c))
(define s (/ sum 2))]
(sqrt (* s (- s a) (- s b) (- s c))))
;; ONE STEP BEGINS
;; create names, bind values, and substitute the new names
(define s 'blah)
(local [(define sum_0 (+ a b c))
(define s_0 (/ sum_0 2))]
(sqrt (* s_0 (- s_0 a) (- s_0 b) (- s_0 c))))
;; move definitions outside of the local
(define s 'blah)
(define sum_0 (+ a b c))
(define s_0 (/ sum_0 2))
(local [] (sqrt (* s_0 (- s_0 a) (- s_0 b) (- s_0 c))))
;; replace local with its body
(define s 'blah)
(define sum_0 (+ a b c))
(define s_0 (/ sum_0 2))
(sqrt (* s_0 (- s_0 a) (- s_0 b) (- s_0 c)))
;; ONE STEP ENDSWe use local to make code more readable, by factoring out common subexpressions.
This is also useful for efficiency purposes. Recall the exponential-time list maximum function:
;; list-max: (ne-listof Num) -> Num
(define (list-max list)
(cond [(empty? (rest list)) (first list)]
[(>= (first list) (list-max (rest list))) (first list)]
[else (list-max (rest list))]))We can now use local to make it much more efficient:
;; list-max: (ne-listof Num) -> Num
(define (list-max list)
(cond [(empty? (rest list)) (first list)]
[else (local [(define m (list-max (rest list)))]
(cond [(>= (first list) m) (first list)]
[else m]))]))Now it calls the function ony once per call, and runs in linear time.
Encapsulation is the process of grouping things together into a capsule or a black box. We choose the hide the irrelevant details to make things simpler.
Behavior encapsulation is the encapsulation of functions.
Since we can define functions locally, we use this to encapsulate related functions.
For example, helper functions that are only used by one function can and should be moved inside that function as a local definition. This makes them invisible outside the function and avoids cluttering the top-level namespace.
;; sum-list: (listof Num) -> Num
;; Purpose: produces the sum of every element in `lon`
;; Examples:
;; OMITTED FOR BREVITY
(define (sum-list lon)
(local [;; sum-acc: (listof Num) -> Num
;; Purpose: produces the sum of every element in `lst` plus `acc`
(define (sum-acc lst acc)
(cond [(empty? lst) acc]
[else (sum-acc (rest lst)
(+ (first lst) acc))]))]
(sum-acc lon 0)))
;; Tests:
;; OMITTED FOR BREVITYNote that the locally defined function does not require examples or tests. However, the function it is located in must fully test the locally defined function.
It's useful that sum-acc can access any of the bindings available in the scope of sum-list. For example, this can remove the need for parameters that "go along for the ride":
(define (count-to upper)
(local [(define (count-from lower)
(cond [(> lower upper) empty]
[else (cons lower (count-from (add1 lower)))]))]
(count-from 0)))Each time we evaluate a local, we are lifting out another set of definitions - defining a different function.
If we evaluate (count-to 1), a function gets created with a body equal to count-from, except with upper replaced by 1.
If we evaluate (count-to 2), another function gets created with a body equal to count-from, except with upper replaced by 2.
This allows us to create different functions as needed.
Now we can fully encapsulate the sort function defined earlier:
;; sort: (listof Num) -> (listof Num)
;; Purpose: produces `list` sorted in ascending order
;; Examples:
;; OMITTED FOR BREVITY
(define (sort list)
(local [;; insert: Num (listof Num) -> (listof Num)
;; Purpose: produces `list` with `element` inserted in sorted order
(define (insert element list)
(cond [(empty? list) (cons element empty)]
[(<= element (first list)) (cons element list)]
[else (cons (first list) (insert element (rest list)))]))]
(cond [(empty? list) empty]
[else (insert (first list) (sort (rest list)))])))
;; Tests:
;; OMITTED FOR BREVITYFunctions are first-class values. This means functions can be passed as arguments to other functions, returned as values, and otherwise treated just like other values like numbers or strings.
Consider the sorting funtion example shown previously. What would we need to change to make it work with strings rather than numbers?
(define (sort list)
(local [;; insert: Num (listof Num) -> (listof Num)
;; Purpose: produces `list` with `element` inserted in sorted order
(define (insert element list)
(cond [(empty? list) (cons element empty)]
[(string<=? element (first list)) (cons element list)]
[else (cons (first list) (insert element (rest list)))]))]
(cond [(empty? list) empty]
[else (insert (first list) (sort (rest list)))])))This is not very elegant - for every type, we need to define a new function.
Instead, we can pass a comparison function as an argument to the sort, which will abstract away the details of comparison:
;;sort: (X X -> Boolean) (listof X) -> (listof X)
(define (sort list less-equal?)
(local [;; insert: Num (listof Num) -> (listof Num)
;; Purpose: produces `list` with `element` inserted in sorted order
(define (insert element list)
(cond [(empty? list) (cons element empty)]
[(less-equal? element (first list)) (cons element list)]
[else (cons (first list) (insert element (rest list)))]))]
(cond [(empty? list) empty]
[else (insert (first list) (sort (rest list) less-equal))])))Note the use of X to represent a particular type (that is possibly a union), in order to show that the input types and output types are the same.
This is known as a type variable. We can also use ones like W, Y, or Z, as long as the meaning is clear. We use type variables whenever two or more places within a contract need to have the same type.
The function works with many different types of data. THis makes it generic or polymorphic, a positive quality.
We also used (X X -> Boolean) to represent a function type. The type of a function is its contract.
Now we can call the function thus
(sort ("b" "d" "a" "c") string<=?)
(sort (5 2 9 1 3) <=)We can also define custom comparators:
(define (posn-less-equal? p1 p2)
(<= (+ (sqr (posn-x p1)) (sqr (posn-y p1)))
(+ (sqr (posn-x p2)) (sqr (posn-y p2)))))
(sort (list (make-posn 1 2) (make-posn 4 3) (make-posn 0 0))) -> (list (make-posn 0 0) (make-posn 1 2) (make-posn 4 3))The built-in function (quicksort list less-equal?) does the same thing. These are abstract list functions - they work on a whole class of lists.
Using this technique, we find that there are a lot of different abstract list operations that we often do. For example, applying a function to every element in a list:
;; map: (X -> Y) (listof X) -> (listof Y)
(define (map f list)
(cond [(empty? list) empty]
[else (cons (f (first list)) (map f (rest list)))]))Note that map is also a built-in function that does the same thing.
How do we use this?
(map sqr '(1 2 3 4 5)) -> '(1 4 9 16 25)
(map even? '(1 2 3 4 5)) -> '(#f #t #f #t #f)Another example is removing elements that do not fit a certain criteria:
;; filter: (X -> Boolean) (listof X) -> (listof X)
(define (filter keep? list)
(cond [(empty? list) empty]
[(keep? (first list)) (cons (f (first list)) (map f (rest list)))]
[else (filter keep? (rest list))]))Note that filter is also a built-in function that does the same thing.
How do we use this?
(filter negative? '(1 -5 -7 3 0)) -> '(-5 -7) (filter #t '(1 2 3 4 5)) -> '(1 2 3 4 5) (list->string (filter char-alphabetic? (string->list "a89erha ae 23*%$%44 yusdh"))) -> "aerhaaeyusdh"
Consider the original elements-more-than in assignment 4, question 2a. Now we can write it much more simply using the abstract list functions:
;; elements-more-than: (listof Num) -> (listof Num)
;; Purpose: produces the elements of `lon` strictly greater than `n`
(define (elements-more-than lon n)
(local [;; keep?: Num -> Boolean
;; Purpose: produces `true` if `number` is greater than `n`
(define (keep? number)
(> number n))]
(filter keep? lon)))How do we add up a list of numbers?
;; total: (listof Num) -> Num
(define (total lon)
(cond [(empty? lon) 0]
[else (+ (first lon) (total (rest lon)))]))This basic form is also used in make-acronym, as well as many other places. How do we abstract this?
An abstract list function could apply a function to the first element of a list and the result of applying it to the rest of the list:
foldr: (X Y -> Y) Y (listof X) -> Y
(define (foldr f base-case list)
(cond [(empty? list) base-case]
[else (f (first list) (foldr f base-case (rest list)))]))Note that foldr is also a built-in function that does the same thing.
The function f should accept an element and the "folded" rest of the list.
How do we use this?
(foldr + 0 '(5 2 3 7)) -> 17
(define (glue-first word acronym)
(string-append (substring word 0 1) acronym))
(foldr glue-first "" '("Kentucky" "Fried" "Chicken")) -> "KFC"foldr abstracts the list template using pure structural recursion.
Intuitively, (foldr f base '(a b c ...)) is equivalent to (f a (f b (f c ...)))
This is less commonly used.
It does the same thing as foldr, but in the opposite order.
We can implement it as follows:
foldl: (Y X -> Y) Y (listof X) -> Y
(define (foldl f base-case list)
(local [;; fold-from-left: (Y X -> Y) Y (listof X) -> Y
(define (fold-from-left f previous list)
(cond [(empty? list) previous]
[else (fold-from-left f (f previous (first list)) (rest list))]))]
(fold-from-left f base-case list)))Note that foldr is also a built-in function that does the same thing.
foldl abstracts the list template using structural recursion with one accumulator.
Intuitively, (foldl f base '(... x y z)) is equivalent to (f z (f y (f x ...)))
How do we apply a function to numbers from 1 to n?
;; even-numbers: Nat -> (listof Nat)
;; Purpose: produces a list of even numbers including 0 up to but not including `n`
(define (even-numbers n)
(local [(define (even-numbers-from start)
(cond [(>= start n) empty]
[else (cons (* start 2) (even-numbers-from (add1 start)))]))]
(even-numbers-from 0)))How can we abstract this?
An abstract list function could apply a function to every number from 0 to the target value:
;; build-list: Nat (Nat -> X) -> (listof X)
(define (build-list n f)
(local [(define (build-list-from start)
(cond [(>= start n) empty]
[else (cons (f start) (build-list (add1 start)))]))]
(build-list-from 0)))Note that build-list is also a built-in function that does the same thing.
The function f should accept a natural number and produce an element of the resulting list.
build-list abstracts the count-up pattern.
(string-ref String Nat) -> Char obtains the character at a given index in a given string. The first character is at index 0.
We can use this to implement string->list ourselves using build-list:
;; string->list: String -> (listof Char)
;; Purpose: produces a list of characters for each character in `s`
(define (string->list s)
(build-list (string-length s) (lambda (i) (string-ref s i))))From now on, we should use the abstract list function whenever possible, rather than dealing with first and rest. The opposite of abstract list functions is explicit recursion.
Create a function that when given a list of numbers, produces the list of those numbers greater than the average:
(define (above-average lon)
(local [(define average (/ (foldr + 0 lon) (length lon)))
(define (higher? n)
(> n average))]
(filter higher? lon)))Create a funciton that checks if a given list of strings is a word chain - where the last letter of each word is the first letter of the next word:
(define (word-chain? los)
(local [(define (check-letter word1 word2-or-bool)
(local [(define word1-length (string-length word1))]
(cond [(boolean? word2-or-bool)
(cond [word2-or-bool word1] ; ignore the starting case
[else false])] ; already failed test
[(string=? (substring word1 (sub1 word1-length) word1-length)
(substring word2-or-bool 0 1))
word1]
[else false])))]
(string? (foldr check-letter true los))))We can have lists and structures that produce functions. We can also have functions that produce functions:
;; generate-line: Posn Posn -> (Num -> Num)
;; Purpose: produces a function that represents a line passing through `p1` and `p2`
;; Examples:
;; OMITTED FOR BREVITY
(define (generate-line p1 p2)
(local [(define slope (/ (- (posn-y p2) (- (posn-y p1)))
(- (posn-y p2) (- (posn-y p1)))))
(define intercept (- (posn-y p1) (* slope (posn-x p1))))]
(lambda (x) (+ (* slope x) b))))
;; Tests:
;; OMITTED FOR BREVITYNote that due to the halting problem, we cannot compare two functions for equality. Therefore, we can't directly test the function that generate-line produces. However, we can just test the function that it produces instead of generate-line itself.
We can use it like this:
((generate-line (make-posn 0 0) (make-posn 1 2)) 5) -> 10We can test it like this:
(check-expect ((generate-line (make-posn 0 0) (make-posn 1 2)) 5) 10)
(check-expect ((generate-line (make-posn 0 0) (make-posn 1 2)) 0) 0)
(check-expect ((generate-line (make-posn 0 0) (make-posn 1 2)) 1) 2)(lambda (arg1 arg2 ...) body)lambda creates an anonymous/unnamed function - a function that is not bound to a name. This is roughly equivalent to the following:
(local [(define (temporary-function arg1 arg2 ...)
body)]
temporary-function)This is simply a function like any other, except there are no names that refer to them.
A lambda is an anonymous function.
This is very useful for the abstract list functions. Where we previously made small helper functions in local definitions, now we can simply use lambda.
Anonymous functions do not need any parts of the design recipe.
(define (f ...) ...) is actually a short form for (define f (lambda (...) ...)).
Lambdas by themselves are values and are in their simplest form.
When applied, lambdas are substituted for their bodies, with arguments inserted in the place of parameters, just like with normal functions.
In Intermediate Student, function applications and definitions with zero arguments are allowed. Note that (+) is 0 and (*) is 1.
Functional abstraction is the process of creating abstract functions like filter. When we abstract the details into an abstract function, we reduce code size and make it easier to fix bugs.
Consider the following function:
(define (make-adder n)
(lambda (x) (+ x n)))We use it as follows:
(define add5 (make-adder 5))
(add5 6) => 11The binding occurrence of n is outside of the lambda. (make-adder 5) creates a new function that is equivalent to (lambda (x) (+ x 5)).
Note that add5 still has access to n inside make-adder, even though we are no longer inside of make-adder when we are calling add5. This is because the function body itself is still inside make-adder, and so still follows the rules of lexical scoping.
Functions that consume or produce functions are sometimes known as higher-order functions.
We are actually not as behind as we thought. So today we will go through module 10 again, but slower this time.
We can actually implement map and filter all using foldr:
(define (my-map f l)
(foldr (lambda (x y) (cons (f x) y)) empty l))
(define (my-filter f l)
(foldr (lambda (x y) (cond [(f x) (cons x y)] [else y])) empty l))Everything that can be done with the list template can be done via foldr, unless it terminates the recursion before the base case, like insert.
Abstract list functions should be used in addition to the list template, when it makes for more understandable code.
Structural recursion is a way of writing code that results in the code following the form of the data definition.
In contrast, generative recursion has the recursive cases and base cases generated based on the problem to be solved.
Consider the GCD function using the Euclidean algorithm:
(define (gcd n m)
(cond [(zero? m) n]
[else (gcd m (remainder n m))]))We know this is correct because we have proven it in MATH135 - see the proof of GCD-WR. In other words, we know that it will give the correct result.
We want to know if the function terminates - if an application of the function results in a simplest form in finite time.
For structurally recursive functions, this is easy because we know that each recursive case recurses on a value closer to the base case, and so it must eventually terminate.
Therefore, we can always bound the depth of recursion based on certain characteristics of the input.
For generatively recursive functions, we must be able to make a similar proof of termination. This will depend on the function itself.
For gcd, we know that (remainder n m) < m and that both are positive or 0. So m is decreasing on every call. Since it can never shoot past 0 into the negatives, it must eventually reach 0, the base case.
Therefore, for any input, the depth of recursion is bounded by the argument m.
It is not possible to analyze an arbitrary function to see if it will terminate due to the halting problem.
Consider the Collatz conjecture, which states that the hailstone sequence, x_n = \begin{cases} \frac{x_{n - 1}}{2} &\text{ if } x_{n - 1} \text{ is even} 3x_{n - 1} + 1 &\text{ if } x_{n - 1} \text{ is odd} \end{cases}, must eventually result in the sequence 1, 4, 2, 1, 4, 2, \ldots.
This is, as of 2013, an unsolved problem in mathematics. We do not know if an arbitrary starting value will eventually result in 1.
As a result, whether the following function terminates is also an unsolved problem in mathematics:
(define (collatz n)
(cond [(= n 1) 1]
[(even? n) (/ n 2)]
[else (add1 (* n 3))]))Consider a more practical example of generative recursion. Quicksort is a sorting algorithm used very widely due to its performance in real-world situations.
This is generative recursion because we are not following the data definition for a list.
It is a divide and conquer algorithm - we divide the problem into smaller subproblems, then recursively solve each one. Afterwards, we combine the results together to obtain the final result.
Quicksort works by picking a pivot, then recursively sorting all the elements lower than the pivot, and all the elements higher than the pivot. Afterwards, the two sorted sublists and the pivots are simply put back together again.
Now we will implement it.
We can simply select the first element of the list as a pivot. This is done with (first list).
Now we need to obtain those elements less than the pivot, excluding the pivot itself: (filter (lambda (x) (< x (first list))) (rest list)).
Now we need to obtain those elements greater than the pivot, excluding the pivot itself: (filter (lambda (x) (>= x (first list))) (rest list)).
We can combine the results as follows: (append sorted-less pivot sorted-greater).
We can now implement the function as follows:
(define (quicksort l)
(cond [(empty? l) empty]
[else (local [(define pivot (first l))
(define less (filter (lambda (x) (< x pivot)) (rest l)))
(define greater (filter (lambda (x) (>= x pivot)) (rest l)))]
(append less (list l) greater)))We know that this function terminates because each recursive call is given a smaller list, which is closer to the base case. Therefore, the function is bounded by the size of the list.
Note that if the list is already sorted, our choice of pivot causes the less list to be empty and the greater list to have every elemetn except the pivot. This would cause it to have the worst-case behavior - quadratic time based on the size of the list. Likewise with lists sorted in descending order.
This is caused by our choice of pivot. Choosing a better pivot in this case would probably help, but it wouldn't work in every case. Consider a list where all elements are equal. This would exhibit worst-case behavior regardless of the pivot choice.
Quicksort has similarities to constructing a binary search search tree out of the elements in the list, and then flattening the tree into a list using in-order traversal. Quicksort can be seen as doing all of this, except without explicitly using trees.
To continue the metaphor, we would simply choose the first element in the list as the root node of the current tree, and then add the rest of the elements of the tree recursively according to their value.
The tree sorting technique would use structural recursion, with accumulators. Quicksort uses generative recursion to do the same task but more efficiently.
When doing generative recursion, the following must also be taken into consideration when writing the design recipe:
Mergesort recursively merges sorted sublists together, and eventually merges two lists into one sorted ist.
We want to implement mergesort. This function is generatively recursive because we need to split the list into two halves.
;; mergesort: (listof Num) -> (listof Num)
(define (mergesort values)
(local [;; merge: (listof Num) (listof Num) -> (listof Num)
(define (merge list1 list2)
(cond [(empty? list1) list2]
[(empty? list2) list1]
[(<= (first list1) (first list2))
(cons (first list1) (merge (rest list1) list2))]
[else
(cons (first list2) (merge list1 (rest list2)))]))]
(cond [(empty? values) empty]
(merge (mergesort (left-half-of values)
(right-half-of values))))))However, it is difficult and computationally expensive to split a list in two - we can't implement left-half-of and right-half-of in a simple way.
Instead, we take a different approach - we work from the bottom, and convert a list of lists into a smaller list of lists. Eventually, we merge two lists into one sorted list.
(define (mergesort values)
(cond [(empty? values) empty]
[(empty? (rest values)) (first values)] ; one element
[else (mergesort (merge-pairs (map list values)))]))
(define (merge-pairs values)
(cond [(empty? values) empty] ; no elements
[(empty? (rest values)) (first values)] ; one element
[else (cons (merge (first values) (second values)) ; merge two adjacent elements together
(rest (rest values)))]))
;; (listof Num) (listof Num) -> (listof Num)
(define (merge list1 list2)
(cond [(empty? list1) list2]
[(empty? list2) list1]
[(<= (first list1) (first list2))
(cons (first list1) (merge (rest list1) list2))]
[else
(cons (first list2) (merge list1 (rest list2)))]));wip: we are probably not supposed to use the same merge here in the second version
We can also simplify mergesort by using a local definition:
(define (mergesort values)
(local [(define (mergesort-ne values)
(cond [(empty? (rest values)) (first values)] ; one element
[else (mergesort-ne (merge-pairs (map list values)))]))]
(cond [(empty? values) empty]
[else (mergesort-ne values)]))We know this terminates because merge-pairs always produces a list that is around half the given list. As a result, if we call it enough times, we will get a list of length 1, the base case.
A graph is simply a collection of nodes where each node can refer to zero or more nodes, including themselves.
A directed graph is a collection of nodes together with a collection of edges.
In a directed graph, edges have direction - the edges (A, B) is different from (B, A). The first points from A to B, while the second points from B to A.
There are also undirected graphs where edges have no direction.
Trees are always graphs, but graphs are not always trees. Trees are graphs that obey some additional constraints.
We can draw graphs graphically. Nodes can be represented as dots with or without labels, and edges can be represented as arrows leading from one node to another.
A graph is useful for solving a lot of different types of problems. For example, internet routing, solving sliding puzzles, and finding road directions.
In a graph, a vertex is a node.
An edge connects two nodes together.
An edge is an ordered pair of nodes like (A, B), where A and B are nodes.
(A, B) is an edge connecting A and B. A is an in-neighbor of B (A points inward to B), and B is an out-neighbor of A (A points outward towards B).
A sequence of nodes v_1, \ldots, v_k is a path or route with length k - 1 if (v_1, v_2), (v_2, v_3), \ldots, (v_{k - 1}, v_k) are edges in the graph.
The length of a path is the number of edges that make it up.
A cycle is a path where v_1 = v_k - the path starts and ends at the same node.
A directed acyclic graph (DAG) is a graph with no possible cycles.
We can represent a graph as a list of nodes, each of which has a list of the nodes it points to. This is called the adjecency list representation.
We will be using the adjacency list representation unless otherwise specified.
This is basically an association list with nodes as keys and a list of their out-neighbors as values.
In Scheme, we can represent a graph with (listof (list Symbol (listof Symbol))):
;; A Node is a Symbol. It is a vertex in a graph.
;; A NodeEntry is a (list Node (listof Node)). It stores a vertex and a list of vertices that the vertex points to.
;; A Graph is a (listof NodeEntry). It is a collection of vertices and their out-neighbors.An example graph in this representation would be:
'((P (Q))
(Q (Z))
(W (X Y))
(X (Q Z))
(Y ())
(Z ()))Note that the order of the nodes in each list is completely arbitrary and does not matter.
Since in this representation, a graph is a list, we can use a list template:
;; my-graph-fn: Graph -> Any
(define (my-graph-fn graph)
(cond [(empty? graph) ...]
[else (... (first (first graph)) ... ; node
(second (first graph)) ... ; node out-neighbors
(my-graph-fn (rest graph)) ...)]))Backtracking algorithms try to find a route from an origin to a destination. They try a possibility, and if it doesn't work out, goes back and tries another, until either there are no possibilities or a route is found.
Suppose we wanted to write find-route, a function that finds a path from one node to another in a DAG. First we write a neighbor function:
;; neighbors: Node Graph -> (listof Node)
;; Purpose: looks up the list of out-neighbors of `node` in `graph`
(define (neighbors node graph)
(cond [(symbol=? node (first (first graph))) ; we do not use a base case because the node is known to be in the graph
(second (first graph))]
[else (neighbors node (rest graph))]))If there is a path, either the starting location is equal to the target location (base case), or the path exists in one of the node's out-neighbors.
;; find-route: Node Graph -> (listof Node)
;; Purpose: produces a path leading from `start` to `end` in `graph`
(define (find-route start end graph)
(cond [(symbol=? start end) (list end)]
[else
(local [(define found-paths
(filter cons?
(map (lambda (node) (find-route node end graph))
(neighbors start))))]
(cond [(empty? found-paths) false]
[else (first found-paths)]))]))This works, but it isn't very efficient since we only really care about one possible path, and it would be more efficient to stop searching when we've found a path already:
;; find-route: Node Node Graph -> (union (listof Node) false)
;; Purpose: produces a path leading from `start` to `end` in `graph` or false if not possible
(define (find-route start end graph)
(cond [(symbol=? start end) (list end)]
[else (local [(define route (find-route-list (neighbors start graph) end))]
(cond [(false? route) false]
[else (cons start route)]))]))
;; find-route-list: (listof Node) Node Graph -> (union (listof Node) false)
;; Purpose: produces a path leading from one of `nodes` to `end` or false if not possible
(define (find-route-list nodes end graph)
(cond [(empty? nodes) false]
[else (local [(define route (find-route (first nodes) end graph))]
(cond [(cons? route) route]
[else (find-route-list (rest nodes) end graph)]))]))We could trace this, but in this case it is more useful to do a trace tree. This is a tree drawn with the recursive call as each node.
find-route is designed to work with acyclic graphs. If there is a cycle, it could potentially loop through the cycle infinitely.
For example, the graph '((A (B)) (B (C)) (C (A)) (D ())) would result in infinite recursion if we tried to find a route from A to D.
For directed acyclic graphs, any route must have no more nodes in it than the number of nodes in the graph. So find-route has an upper bound on the number of times it recurses - the number of routes to any destination in the graph. So the function always terminates if there are no cycles.
What if there are cycles?
Some possible solution is to pass down a list of visited nodes to avoid visiting them again, since the visited nodes are still being processed:
;; find-route: Node Node Graph (listof Node) -> (union (listof Node) false)
;; Purpose: produces a path leading from `start` to `end` in `graph` having visited `visited` or false if not possible
(define (find-route start end graph visited)
(cond [(symbol=? start end) (list end)]
[else (local [(define route (find-route-list (neighbors start graph) end
graph (cons start visited)))]
(cond [(false? route) false]
[else (cons start route)]))]))
;; find-route-list: (listof Node) Graph Node -> (union (listof Node) false)
;; Purpose: produces a path leading from one of `nodes` having visited `visited` or false if not possible
(define (find-route-list nodes end graph visited)
(cond [(empty? nodes) false]
[(member? (first nodes) visited)
(find-route-list (rest nodes) visited)]
[else (local [(define route (find-route (first nodes) end graph visited))]
(cond [(cons? route) route]
[else (find-route-list (rest nodes) end graph visited)]))]))Note that the value of visited is always the reverse of the route, if there is one.
In practice, we would usually write a wrapper function to avoid having to pass the extra visited parameter.
The accumulator makes sure we never recurse deeper than there are nodes in the graph, so the function always terminates, even if there are cycles.
However, this is still not very efficient. Consider the following graph:
'((A (B1 B2)) ; diamond 1
(B1 (C))
(B2 (C))
(C (D1 D2)) ; diamond 2
(D1 (E))
(D2 (E))
(E (F1 F2)) ; diamond 3
(F1 (G))
(F2 (G))
(G (H1 H2)) ; diamond 4
(H1 (I))
(H2 (I))
(I ()) ;end of diamond 4
(Z ()))If we tried to search for a path from A to Z, the backtracking search would check every possible path variation. For example, there are 2 ways to get from A to C, but C doesn't lead to Z in the first place, so searching to C is a waste of time the second time we try to get to it.
In fact, with this diamond-shaped pattern of graph, the number of paths checked is an exponential function of the number of diamonds - 2^n, in our case.
We can make this more efficient by having a failed route finding in find-route-list return the list of nodes that were visited so that we can avoid visiting them again in the remaining candidates in the list of neighbors:
;; find-route: Node Node Graph -> (union (listof Node) false)
;; Purpose: produces a path leading from `start` to `end` in `graph` or false if not possible
(define (find-route start end graph)
(local [(define route (find-route-fast start end graph empty))]
(cond [(empty? (first route)) false] ; no route found
[else route])))
;; find-route-fast: Node Node Graph (listof Node) -> (union (listof Node) (listof (union empty Node)))
;; Purpose: produces a path leading from `start` to `end` in `graph` having visited `visited` or the list of visited nodes with empty prepended if not possible
(define (find-route-fast start end graph visited)
(cond [(symbol=? start end) (list end)]
[else (local [(define route (find-route-list (neighbors start graph) end
graph (cons start visited)))]
(cond [(empty? (first route)) route]
[else (cons start route)]))]))
;; find-route-list: (listof Node) Graph (listof Node) -> (union (listof Node) (listof (union empty Node)))
;; Purpose: produces a path leading from one of `nodes` having visited `visited` or the list of visited nodes with empty prepended if not possible
(define (find-route-list nodes end graph visited)
(cond [(empty? nodes) (cons empty visited)]
[(member? (first nodes) visited)
(find-route-list (rest nodes) end graph visited)]
[else (local [(define route (find-route-fast (first nodes) end graph visited))]
(cond [(empty? (first route)) ; route not found
(find-route-list (rest nodes) end graph (rest route))]
[else route]))]))Now each node is visited at most once, since once a node has been visited, it stays in visited for the rest of the search. Therefore, the number of nodes we check is a linear function of the number of nodes in the graph.
Since each node check calls neighbors, which takes linear time proportional to the number of nodes in the graph, the runtime of find-route is a quadratic function of the number of nodes in the graph.
Sometimes it is impractical or inefficient to build the entire graph explicitly. An implicit graph is one that isn't explicitly represented as a graph.
For example, the possible legal moves in a chess game could be an implicit graph, with nodes representing possible game states and edges representing legal moves between these states. It is not practical to represent all the possible moves explicitly, so we do not.
What if we wanted to use find-route to search for a path through an implicit graph?
Note that the only part of the function that actually does anything with the graph is neighbors. In fact, all we have to do is implement a different neighbors function. A neighbor function that returned the list of legal moves in chess given the current game state would allow us to use a backtracking search to implement a simple chess solver, though its performance is impractically poor.
In artificial intelligence applications, implementations usually add heuristics to determine which neighbors to explore first or which to skip entirely, in order to save time.
Computer Science is not a well defined field, having only existed for about 75 years.
Early computations were done by humans, who were called "computers".
Charles Babbage (1791-1871) was a mathematician who invented but never built the difference engine and analytical engine - mechanical computing machines where the specification of the operations to be executed were separated from actually execution. This is the first autonomous computing machine.
Ada "Lovelace" Augusta Byron (1815-1852) assisted Babbage in the design of the machines and could be considered the first computer scientist or programmer. Wrote about the actual operation and use of the engines rather than just the design.
David Hilbert (1862-1943) was a mathemtician who formalized the axiomatic treatment of Euclidean geometry. He is famous for posing 23 unsolved problems, some of which have since been solved.
Most famously, Hilbert posed the question of whether mathematics is consistent (a statement cannot be proven true and false), or complete (all true statements are provable).
Kurt Godel (1906-1978) finally proved that any non-trivial system of axioms (a system of axioms capable of describing integer arithmetic) is not complete. If it is consistent, it cannot be proved within the system.
The proof is based on "this statement cannot be proved" written in mathematical notation. It would be inconsistent if the statement was false, since it would be a proof of a false statement, so it must be true but not provable.
Another one of Hilbert's questions asked if there was a procedure that, given a formula, proves it true, shows it false, or shows that it is unprovable. This requires a precise definition of a procedure - a formal model of computation.
Alonzo Church (1903-1995) showed that such a procedure is not possible. He invented lambda calculus with his student Kleene.
The notation is as simple as possible: \lambda x . E is a single-argument function with body E, while ;wip
Alan Turing (1912 1954) defined a different model of computation and resulted in a simpler and more influential proof.
His Turing machine was a theoretical device with unlimited memory and a finite number of states. It could be thought of as a machine with an infinite tape and a finite state machine.
One could represent a Turing machine using characters stored in the memory of another machine. Suppose there was a machine that could process one of these descriptions and result in whether it would eventually halt or not. Then there exists another machine that would halt if and only if the first machine said it wouldn't. This is a contradiction, so it is impossible for such a machine to exist.
This is called the halting/undecidability problem and was a very significant result. This was later adapted into lambda calculus, and an equivalence was established between the two models.
Turing is also known for his contributions to code breaking in World War 2, and to the first electronic computer, Colossus.
John von Neumann (1903-1957) is known for his von Neumann computer architecture, with programs stored in the same memory as data. This is still the standard model for computation today, along with the Harvard architecture. However, it doesn't take advantage of parallel processing.
;wip: von neumann bottleneck
Grace Murray Hopper (1906-1992) was the author of the first compiler defining an english-like data processing language, which later became COBOL.
John Backus designed FORTRAN, which became the dominant language of numerical and scientific computation. The Backus-Naur notation is also attributable to him.
He also proposed a functional programming language, and led to the development of LISP.
John McCarthy (1927-2011) was an AI researcher at MIT known for designing and implementing LISP, based on ideas from lambda calculus and recursive function theory.
It was described with only the functions atom ((lambda (x) (not (cons? x)))), eq (equal?), car (first), cdr (rest), and cons. It also had the special forms lambda, quote, cond, and label (define). Many other functions could be implemented using just these functions.
LISP (LISt Processing) eventually evolved into a general purpose programming language with many other useful functions. It became the dominant language in artificial intelligence due to its encouragement of modifying the language itself. It became two main standards after the 1980s - Common Lisp and Scheme.
Gerald Sussman invented Scheme after an idea for a Lisp-like programming language had actors and lexical scoping added (as opposed to Common Lisp's dynamic scoping). It became popular in the study of programming languages. He also wrote the textbook "Structure and Interpretation of Computer Programs", based on Scheme.
The textbook "How to Design Programs" was written to remedy some issues with that book, such as a steep learning curve and a lack of methodology.
APPLAUSE
This work by Anthony Zhang is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright 2013-2017 Anthony Zhang.