Introduction to Racket

Racket is a popular modern dialect of Scheme, and Scheme is a popular dialct of Lisp. Lisp is a computer programming language developed in the 1950s and 1960s by John McCarthy and his students. It’s based on the lambda calculus, a mathematical formalism for defining and executing functions.

Lisp has proven to be an influential language, and has been the source of ideas found in many other languages, and it is well worth learning about.

Getting Racket

These notes will be using the Racket dialect of Lisp. Racket comes with the DrRacket IDE, which provides pretty good support for programming in Racket. If you prefer, you can use Racket with other editors, such as Sublime Text or Visual Studio Code, using their Scheme/Lisp modes.

You can also run Racket at the command line. For example, type racket to run the Racket interpreter in Linux:

$ racket
Welcome to Racket v6.11.
>

Type (exit), or ctrl-D, to quit the interpreter.

Be aware that Racket supports multiple languages, and in these notes we will always be using the base Racket language unless we say otherwise. To ensure you are using the correct language, make sure that all your Racket programs have this at the top:

#lang racket

You can find lots of documentation and support for Racket on its web page. In particular, you should bookmark the Racket Guide, which is a good overview of Racket, and also the Racket Reference, which documents all the standard functions and features. For instance, all the standard list processing functions can be found on this reference page.

Running Racket

Once it’s installed, you can run Racket by launching the DrRacket IDE. The IDE shows a text window and interaction window. The idea is that your write your program in the text window, and use the interaction window to test it.

Here are a few useful keyboard shortcuts:

• ctrl-E will open/close the interaction window
• ctrl-D will open/close the definitions window
• ctrl-S will save the current definitions
• ctrl-R will run the current definitions in the interaction window

> is the interpreter prompt, and means that it is waiting for you to type something. So try this:

> (* 2 3 5)
30

The expression (* 2 3 5) calculates the product of 2, 3, and 5, i.e. \(2 \cdot 3 \cdot 5 = 30\).

Using Racket’s Interactive Interpreter

We’ll mainly be using Racket via its interactive interpreter. This is sometimes referred to as a REPL, which stands for read-eval-print loop. It lets us evaluate expressions one at a time. For instance:

> (+ 3 2)
5

> (* 10 4)
40

> (- 5 8)
-3

> (/ 6 2)
3

> (/ 5 2)
2 1/2       ; 1/2 is written as a fraction in DrRacket

An interactive REPL is a feature of most Lisp-like language. You typically use the REPL to test small examples, or to run just part of your program.

Right away you can see that Racket looks different than most languages. All functions in Racket are called using prefix notation. This can seem strange, especially for arithmetic. Most languages use infix notation for arithmetic expressions, e.g. 3 + 2, since that’s what we learn in elementary school. However, when we evaluate functions, we normally use prefix notation, e.g. f(2, 3). Racket uses prefix notation for everything, which, once you get used to it, is simple and consistent.

Another interesting feature of Racket is that expressions are delineated by open ( and close ) brackets. As you will see, Racket programs can end up having a lot of brackets, and making sure they all match can be tricky: a good editor will help with the bracket matching.

On nice advantage of prefix notation is that you can pass multiple arguments to many operations, e.g.:

> (+ 3 2 3 5)
13

> (* 1 6 2 2)
24

> (/ 100 10 5)
2

> (- 1 2 3)
-4

Notes on “Racket Essentials”: Simple Values

Please read Racket Essentials. The following are some comments on that section.

Note that Racket has a number of simple values, some of which might unfamiliar, e.g.:

> "a"                  ; a string
"a"

> "a racket is \"an illegal scheme\""   ; \" inside strings
"a racket is \"an illegal scheme\""

> 'a                   ; a symbol
'a

> '(a b 1 (2 3) ())    ; quoted list
'(a b 1 (2 3) ())

> (+ 1/3 1/3 1/3)      ; 1/3 is a rational type
1

> (* 1+2i 1+2i)        ; complex types
-3+4i

Note that rational types may be reduced to lowest terms when they are printed, e.g.:

> 26/91
2/7

Symbols and Quoting

Symbols are a kind of value that are not found in many other mainstream languages. symbol? tests if a value is a symbol:

> (symbol? 'a)
#t

> (symbol? 'apple)
#t

> (symbol? 'first-ever-airplane)
#t

> (symbol? 4)      ; 4 is a number
#f

> (symbol? odd?)   ; odd? is a function
#f

> (symbol? x)      ; missing '
. . x: undefined;
 cannot reference an identifier before its definition

Symbols are just values with names, and we can’t access the individual characters they’re made from.

Strings and symbols are similar. In Racket, strings are wrapped in ""-quotes, e.g.:

"apple"    ; a string
'apple     ; a symbol
apple      ; an unbound variable (error)

You can access the individual characters of strings, calculate their length, and so on. But you can’t normally do such things with symbols. Given two symbols you can check if they are the same or different, but that’s about it.

Note the quote, ', in front of all the valid symbols. Quoting is an important part concept in Racket, and it is used to distinguish symbols from variables. For example, x is a variable, while 'x is a symbol:

> (symbol? 'x)
#t

> (symbol? x)
. . x: undefined;
 cannot reference an identifier before its definition

The expression (symbol? x) can’t be evaluated because Racket applies symbol? to the value bound to x. But in this case, x is not bound to anything, so there’s an error.

Like numbers, symbols evaluate to themselves:

> 'a
'a

> 'cat
'cat

This contrasts with variables, which evaluate to the value they’re bound to.

You can also quote lists in Racket, e.g.:

> (+ 2 3)
5
> '(+ 2 3)
'(+ 2 3)

'(+ 2 3) is not a symbol. Instead, it’s a list:

> (symbol? '(+ 2 3))
#f
> (list? '(+ 2 3))
#t

If you don’t put a ' in front of the list, then it evaluates to 5:

> (list? (+ 2 3))   ; same as (list? 5)
#f

In general, a quoted expression evaluates to itself: the thing being quoted is not evaluated.

There is another, less common, way of quoting things in Racket. You can use the quote form like this:

> (quote (+ 2 3))
'(+ 2 3)

(+ 2 3) does not get evaluated inside of a quote form. Thus, quote is an example of a special form: it does not evaluate its argument.

In general, (quote x) is the same as 'x. The single-quote form is usually preferred because it has fewer brackets and is easier to read, e.g.:

> (symbol? (quote (+ 2 3)))
#f
> (list? (quote (+ 2 3)))
#t

> (symbol? '(+ 2 3))
#f
> (list? '(+ 2 3))
#t

Notes on “Racket Essentials”: Simple Definitions and Expressions

The define form is used to define identifiers and functions.

Here’s how we can use define to give identifiers a value:

(define scale 4.5)
(define title "Dr. Racket")

After clicking “Run” (or type ctrl-R) in DrRacket, you can use scale and title:

> (* scale 5)
22.5

> (string-append title "!!!")
"Dr. Racket!!!"

Function definitions usually have a different form:

(define (add1 n) (+ 1 n))

This defines a function named add1 that takes one input, here called n, and returns one more than n. It is up to the programmer to make sure that only numbers are passed to add1, otherwise you get an error:

> (add1 5)
6

> (add1 "five")
. . +: contract violation
  expected: number?
  given: "five"
  argument position: 2nd
  other arguments...:

Here’s another example of a function, this time one with side-effects:

(define (greet name)
  (printf "Welcome to Racket ~a!" name)
  (newline)
  (printf "I hope you learn a lot.")
)

It is called like this:

> (greet "Alan")
Welcome to Racket Alan!
I hope you learn a lot.

This function is named greet, and it doesn’t return a value. The only reason we call it is for its side-effects, i.e. for what it prints to the screen. Anything that happens outside of a function — such as printing to the screen, reading from a file, setting a global variable, etc. — is a side-effect. In general, we will try to avoid side-effects in Racket whenever possible. Unnecessary side-effects tend to make programs more complicated and error-prone.

Source Code Comments in Racket

There are a couple of ways of writing source comments in Racket:

• ; is a single-line comment: characters after ; and to the end of the line are ignore. Multiple ; characters are often used for emphasis, e.g. the beginning of an important section of code might begin with ;;;.

  ; single-line comments start with “;” in Racket

• #| and |# can mark multi-line comments: #| is the start of the comment and |# is the end of the comment, e.g.:

  #|
  
     This is an example of a multi-line comment.
  
  |#
  

• #; comments out an entire expression. For example, this entire expression is commented out by the #; at the start:

  #;(define (nlist? n lst)
    (and (list? lst)
         (= n (length lst))))
  

Notes on “Racket Essentials”: Conditionals with if, and, or, and cond

Conditionals are used to make decisions in programs. The if form is like an if-then-else statement in other languages, and it always has this format:

(if <test> <true-result> <false-result>)

<test> is an expression that evaluates to #t (true) or #f (false). If <test> is #t, then <true-result> is evaluated; otherwise, <false-result> is evaluated.

Importantly, if — and all the other Racket conditionals — returns its result. This is like the ?: operator in languages such as C/C++ and Java. So we can use if forms inside other calculations, e.g.:

(define x 2)
(define y 3)

> (if (< x y) y x)
3

> (- (if (< x y) y x) (if (> x y) y x))
1

The last expression calculates the max of x and y minus the min of x and y. So we could have written these function definitions:

(define (mymax x y) (if (> x y) x y))  ; max and min are already defined in
(define (mymin x y) (if (< x y) x y))  ; Racket, so we call these mymax and mymin

> (- (mymax x y) (mymin x y))
1

Or we could define one function to do the entire calculation:

(define (abs-diff x y)
  (if (< x y)
      (- y x)
      (- x y)))

> (abs-diff x y)
1

The and form calculates the logical “and” of 0 or more boolean expressions: (and <test1> <test2> ...) returns #t just when all of the tests evaluate to true, and #f otherwise. For example:

> (and)
#t
> (and (= 2 3))
#f
> (and (= 2 2) (< 4 5))
#t
> (and (= 2 2) (< 4 5) (> 4 10))
#f

Importantly, and uses short-circuiting: the inputs to and are evaluated in the order they’re given (left to right), and after the first one evaluates to #f, the expression returns #f and none of the rest are evaluated.

For example, the following function relies on the fact that and is short-circuited:

(define (good-password x)
  (and (string? x)                   ; must be a string
       (<= 8 (length x))             ; at least 8 characters
       (not (string-contains? x " ") ; has no spaces
)))

(good-password s) is #t if s is a “good” password, and #f otherwise. The first thing it checks is that s is indeed a string. If s is not a string, then the later calls to length and string-contains? would fail with an error. Since and is short-circuited, if (string? x) is #f, the entire expression returns #f and the last two expressions are never evaluated.

The or form is similar to and, except it evaluates logical “or”: (or <test1> <test2> ...) returns #t if 1, or more, of the tests evaluate to true, and #f otherwise. For example:

> (or)
#f
> (or (= 2 3))
#f
> (or (= 2 3) (< 4 5))
#t
> (or (= 2 3) (> 4 5) (> 6 10))
#f

Like and, or is short-circuited: the tests are evaluated in order (from left to right), and soon as one evaluates to #t no further tests are evaluates and the entire expression evaluates to #t. For instance, this expression returns #t thanks to short-circuiting:

> (or (= 2 2) (error "oops"))
#t

Finally, the most general conditional form we will look at is cond. A cond form is similar to if-else-if structures in other languages. For example:

(define (sign n)
  (cond [(not (number? n)) "not a number"]
        [(< n 0) "negative"]
        [(> n 0) "positive"]
        [else "zero"]
))

> (sign -5)
"negative"
> (sign 3)
"positive"
> (sign 0)
"zero"
> (sign "three")
"not a number"

In general, a cond form looks like this:

(cond [test1 result1]
      [test2 result2]
      ...
      [else result_else]
)

When cond is evaluated, first test1 is evaluated. If it’s #t, then result1 is evaluated and the entire cond expression returns result1 (and no more tests are evaluated). If instead test1 is #f, then test2 is evaluated. If test2 is #t, then the entire cond returns result2. Otherwise, if test2 is #f, the rest of the cond is evaluated in a similar fashion.

The final test in this general cond form is else, which is a synonym for #t. Since else is always true, if the program ever gets to it then result_else will be returned as the value of the cond.

A cond doesn’t need to have an else: it depends upon what you want the cond to do. Also, you could replace else with #t and get the same result.

It’s important to understand that as soon as one test in the cond evaluates to true, all later tests (and results) are not evaluated. This means that cond is not a function (because all arguments to a function are evaluated), and is instead another example of a special form.

Finally, we note that the use of []-brackets in cond expressions is just a convention, and you could instead use regular round brackets. For instance, the sign function from above could be written without []-brackets like this:

(define (sign n)
  (cond ((not (number? n)) "not a number")
        ((< n 0) "negative")
        ((> n 0) "positive")
        (else "zero")
))

[]-brackets are used just for readability: all those parentheses can get hard to read, and so this is one of the places that most Racket programmers use []-brackets. The []-brackets mean the same thing as ()-brackets, and so you can use them anywhere you like. In general, you should only use []-brackets in cases, as in cond, where they improve the readability of code.

Conditionals are Not Functions

Suppose x is a variable that already been defined, but we don’t know what it’s value is. The expression (and (number? x) (= x 0)) is true if x is a number equal to 0, and false otherwise. If x happens to be a list, then the expression evaluates to false thanks to the fact that and uses short-circuit evaluation.

You might wonder if it’s possible to write your own version of and as a function, e.g. maybe something like this:

(define (bad-and e1 e2)
    (if e1
        (if e2 #t #f)
        #f
    )
)

Logically, this is correct: it returns #t if both e1 and e2 are true, and #f otherwise. Also, if e1 is false, then it knows the entire expression must be #f, and it doesn’t even look at the value of e2.

But it doesn’t work in Racket. The problem is that Racket evaluates the arguments to a function before calling the function. Suppose x is defined to be the list '(a b c), and consider what would happen if you were to evaluate (bad-and (number? x) (= x 0)):

• First (number? x) is evaluated, and this evaluates to #f because x is the list '(a b c).

• Second, (= x 0) is evaluated, and this causes an error because you cannot use a list with =:

  > (= 0 '(a b c))
  . . =: contract violation
    expected: number?
    given: '(a b c)
    argument position: 2nd
    other arguments...:
  

So the expression fails with an error before my-and can even be called.

The problem is that conditionals like if, and, or, and cond don’t evaluate all their arguments. Instead, their arguments are passed to them unevaluated so that the conditional can decide which arguments to evaluate.

There is no way around this problem using functions: conditional forms like if, and, or, and cond cannot be written as functions. But, they can be written as macros. Macros are function-like definitions that don’t evaluate their arguments, and so can be used to implement conditionals and other special forms (like variations of define). Macros are a more advanced topic that will be discussed later.

Notes on “Racket Essentials”: Lambda Function

A lambda function, also know as an anonymous function, is essentially an expression that evaluates directly to a function. You can think of it as a function without a name.

For example, this lambda function doubles its input:

(lambda (n) (* 2 n))   ; a lambda function

The entire expression evaluates to a function that takes a single input, n, and returns two times n. You could use it directly like this:

> ((lambda (n) (* 2 n)) 31)
62

You can also define a variable to be a function like this:

(define double (lambda (n) (* 2 n)))

> (double 31)
62

The definition of double using lambda is equivalent to this one:

(define (double n) (* 2 n))

This form is shorter and easier to read, and so this is what most programmers tend to write. But you could certainly write function definitions in the lambda style if you prefer.

In general, a lambda function has the format (lambda (arg1 arg2 ... argn) body-expr).

In Racket, lambda functions are often used when you want to pass a small function to another function. For example, consider the twice function:

(define (twice f x)  ; call f twice on input x
    (f (f x)))

You can use twice like this:

> (twice sqr 3)
81
> (twice sqrt 3)
1.3160740129524924
> (twice (lambda (x) (+ 6 x)) 3)
15

The last example could instead have been written like this:

(define (add6 x) (+ 6 x))

> (twice add6 3)
15

But it seems a bit much to use define to create a named function in this case. In practice, a function like add6 might only be used a single time, and it might be hard to come up with a good name. And so many Racket programmers prefer to use lambda functions for small functions like this.

Notes on “Racket Essentials”: Local Bindings with Let and Let*

Sometimes it is convenient to create a local variable, or local binding in an expression. For example, we can use a let form like this:

(define (dist1 x1 y1 x2 y2)
  (let ([dx (- x1 x2)]
        [dy (- y1 y2)])
    (sqrt (+ (* dx dx) (* dy dy)))))

Here, dx and dy are local variables that only exist within the scope of the let form. In general, let has this format:

(let ([v1 val1]
      [v2 val2]
      ...
      [vn valn]
  body ; v1, v2, ..., vn can be used here
)

The entire let form evaluates to whatever body evaluates to.

As with cond, it is conventional (but not required) that []-brackets are used to enclose the bindings. You could write let like this if you prefer:

(let ((v1 val1)   ;; ()-brackets can be used intead of []-brackets
      (v2 val2)
      ...
      (vn valn)
  body
)

Most Racket programmers find the version with []-brackets to be more readable, and so it is the preferred style.

Consider this example of let:

> (let ([a 1] [b 1] [c 2]) (+ a b c))
4

There is a subtlety here that is worth exploring a bit. It could be re-written like this:

> ((lambda (a b c) (+ a b c)) 1 1 2)
4

This shows that we can simulate a let using a function call: calling a function binds its input arguments to its formal parameters. The let is much easier to read, of course, because it puts the variables right beside their assigned values; here, the variables are quite far away from their values, making it much harder to read. But nonetheless, it shows that let can be simulated using simpler concepts.

Indentation makes the scope clearer:

(
  (lambda (a b c)
     (+ a b c)
  )
  1 1 2  ; a, b, c are not in scope here
)

Notice that the scope of a, b, and c is limited to the lambda function they’re defined in. You can’t use a, b, or c outside of it.

So, for example, this expression causes an error:

(
  (lambda (a b c)
     (+ a b c)
  )
  1 a 2  ; error: a is not in scope
)

If you re-write this as an equivalent let expression, you get this:

(let ([a 1]
      [b a]  ; error: a is out of scope here!
      [c 2]
     )
     (+ a b c)
)

This is an also an error, presumably because let is converted into something like the lambda version we wrote above.

While this limitation makes sense given what let is re-written to, it is inconvenient in practice. And so Racket provides the let* form which remove this restriction. This works as expected:

(let* ([a 1]
       [b a]  ; okay: this is a let* environment
       [c 2]
      )
  (+ a b c)
)

You can imagine that let* re-writes the expression using embedded let forms, perhaps like this:

(let ([a 1])
    (let ([b a])     ; ok: a is in scope
        (let ([c 2])
            (+ a b c)
        )
    )
)

Or even as plain lambdas:

(
  (lambda (a)
      (
        (lambda (b)
            (
              (lambda (c)
                  (+ a b c)
              )
              2 ; bound to c
            )
        )
        a ; bound to b
      )
  )
  1 ; bound to a
)

In practice, many programmers always use let* since it is more flexible.

Notes on “Racket Essentials”: Lists and Recursion

Racket has good built-in support for singly-linked lists. In this course, it’s the data structure we’ll use most frequently. Racket supports things like vectors, strings, and hash tables as well, but we will not use those too often.

You can create a list using the list function, or with quoting, e.g:

> (list 1 2 3)
'(1 2 3)
> '(1 2 3)
'(1 2 3)

> (list 'a 'b 'c)
'(a b c)
> '(a b c)
'(a b c)

> (list 'my 'dog 'has 'fleas)
'(my dog has fleas)
> '(my dog has fleas)
'(my dog has fleas)

> (list 'my 'dog (list 'and 'hamster) 'have 10 'fleas 'each)
'(my dog (and hamster) have 10 fleas each)
> '(my dog (and hamster) have 10 fleas each)
'(my dog (and hamster) have 10 fleas each)

As the last example shows, a Racket list can contain any type of value, even other lists.

Since list is a function, it can be useful in cases where you want to evaluate expressions before putting them into a list, e.g.:

> (list (+ 1 2) (* 3 4) (- 5 6))
'(3 12 -1)

If you don’t start a list with a ', Racket tries to evaluate the list as if it were a function call, e.g.:

> (1 2 3)
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 1
  arguments...:

Here, Racket is treating 1 as if it were a function, and tries to “apply” it to the arguments 2 and 3. Since 1 is not a function, it cannot be applied, and so an error results.

The empty list is a list with 0 values, and is written as '(). Use null? or empty? to test if a list is empty:

> (null? '(1 2))
#f
> (null? '())
#t

> (empty? '(1 2))
#f
> (empty? '())
#t

List Processing

Racket has many useful built-in list processing functions. When thinking about the performance characteristics of these functions, keep in mind that Racket lists are singly-linked lists, and so a function that traverses an entire list runs in, at least, linear time.

The first function returns the first element of a list:

> (first '(1 2 3))
1
> (first '((1 2) 3 4))
'(1 2)
> (first '(my dog has fleas))
'my
> (first '())
. . first: contract violation
  expected: (and/c list? (not/c empty?))
  given: '()

The empty list has no first element, so (first '()) is an error.

The rest function returns everything on a list except for the first element:

> (rest '(1 2 3))
'(2 3)

> (rest '((1 2) 3 4))
'(3 4)

> (rest '(my dog has fleas))
'(dog has fleas)

> (rest '())
. . rest: contract violation
  expected: (and/c list? (not/c empty?))
  given: '()

Note

first and rest were not the function names used in the original version of Lisp. Instead, car was the name for first, and cdr was the name for rest. These unusual names refer to the underlying hardware of the original computer on which Lisp was first implemented.

Some Lisp programmers still like to use car and cdr: they are short and simple. These functions are predefined in Racket, and do have some uses. But, for readability, we will stick to first and rest whenever possible.

The cons function “constructs” a new list by adding an element to the start of a given list:

> (cons 1 '(2 3))
'(1 2 3)
> (cons '(2 3) '(3 4))
'((2 3) 3 4)
> (cons 'my '(dog has fleas))
'(my dog has fleas)
> (cons 'x '())
'(x)

first, rest, and cons work well together, e.g.:

> (cons (first '(1 2 3)) (rest '(1 2 3)))
'(1 2 3)

It can be useful to think of a list as a nested series of calls to cons. For example, the list '(a b c d) could be written like this:

> (cons 'a (cons 'b (cons 'c (cons 'd '()))))
'(a b c d)

Since Racket implements lists as singly-linked lists, then first, rest, and cons all run in worst-case \(O(1)\) time.

These functions can be combined to do many different useful things. For example, the first of a lists rest is its second element:

> (first (rest '(a b c d)))
'b

Racket has a predefined function called second that does the same thing.

Racket even lets you do things like this:

> ((first (list min max)) 41 2 3)
2

To evaluate this entire expression, (first (list min max)) is evaluated. First, the sub-expression (list min max) evaluates to (list <min-fn> <max-fn>), i.e. the variables min and max are replaced by the functions they’re bound to. Then (list <min-fn> <max-fn>) evaluates to the list (<min-fn> <max-fn>). So (first (list min max)) becomes (first (<min-fn> <max-fn)), which is just <min-fn>.

Notice that we used list in the above example. Using a ' does not give the same result:

> ((first '(min max)) 41 2 3)
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 'min
  arguments...:

The difference here is that the min inside the quoted list is not evaluated, and so the result of (first '(min max)) is the symbol 'min. In contrast, when (list min max) is called, both min` and ``max are evaluated, and replaced with their corresponding functions. So (first (list min max)) is the min function, while (first '(min max)) is the 'min symbol.

Recursive Functions

If you want to determine the length of a list, Racket provides a built-in length function:

> (length '(1 (2 3) 4))
3

We could also write our own function using recursion like this:

(define (len lst)
  (cond [(null? lst) 0]                 ; base case
        [else (+ 1 (len (rest lst)))])) ; recursive case

len has two cases:

• base case: when the list lst is empty
• recursive case: calculate the length of the rest of lst, then add 1

As you can see, you must take care to get all the parentheses to match!

Here’s another example where we implement linear search to determine if a given value is on a list:

;; Returns true if x is in lst, and false otherwise.
(define member
  (lambda (x lst)
    (cond [(null? lst) #f]
          [(equal? x (first lst)) #t]
          [else (member x (rest lst))]
)))

Notice there are two base cases here: one for the empty list, and one for when x is the first element of the list. In general, a recursive function could have multiple base cases and multiple recursive cases.

Recall that the symbol? function tests if an object is a symbol (such as 'cat). The following function returns the number of symbols in a list:

(define (count-sym1 lst)
  (cond
    [(null? lst) 0]
    [(symbol? (first lst))
     (+ 1 (count-sym1 (rest lst)))]
    [else (count-sym1 (rest lst))]))

We could have written it more compactly like this:

(define (count-sym2 lst)
  (if (null? lst)
      0
      (+ (if (symbol? (first lst)) 1 0)
         (count-sym2 (rest lst)))))

Since an if form returns a value, we can are able to use it inside the + in the above function. It makes it clear that that the only thing that differs in the two cases is whether we add a 1 or a 0.

Suppose now we want to count how many numbers are in a list. We can make a small modification to count-sym1 to get this:

(define (count-num lst)
  (cond [(null? lst) 0]
        [(number? (first lst))
         (+ 1 (count-num (rest lst)))]
        [else (count-num (rest lst))]))

Compared to count-sym1, count-num is the same except for two differences: number? is used instead of symbol?, and each occurrence of count-sym1 has been changed to count-num.

Lets generalize this even further, and write a general-purpose counting function that takes a list and a predicate function (i.e. a function that takes one value as input and returns a boolean value) as input:

(define (count-fn1 pred? lst)
  (cond [(null? lst) 0]
        [(pred? (first lst))
         (+ 1 (count-fn1 pred? (rest lst)))]
        [else (count-fn1 pred? (rest lst))]))

To use it we pass in any function that takes a single input value and returns either true or false:

> (count-fn1 even? '(1 2 3 4 5 6 7))
3
> (count-fn1 odd? '(1 2 3 4 5 6 7))
4
> (count-fn1 number? '(1 2 3 4 5 6 7))
7
> (count-fn1 symbol? '(1 2 3 4 5 6 7))
0

Using count-fn1, it is easy to re-write the previous functions like this:

(define count-symbol (lambda (lst) (count-fn symbol? lst)))

(define count-number (lambda (lst) (count-fn number? lst)))

Notice that we could also have written count-fn1 is this equivalent but more compact way:

(define (count-fn2 pred? lst)
  (if (null? lst) 0
      (+ (if (pred? (first lst)) 1 0)
         (count-fn2 pred? (rest lst)))))

Here’s another example of the same sort of generalization. This is a more flexible version of the member function from above:

(define (member-fn pred? lst)
  (cond [(null? lst) #f]
        [(pred? (first lst)) #t]
        [else (member-fn pred? (rest lst))]
))

(member-fn pred? lst) returns true if there is one, or more, elements x on lst such that (pred? x) is true.

For example, to test if a list contains an even number, you can do this:

> (member-fn even? '(1 3 5 6 9 9))
#t
> (member-fn even? '(1 3 5 61 9 9))
#f

We can also re-write the first member function like this:

(define (member x lst)
  (member-fn (lambda (b) (equal? b x))
             lst))

(lambda (b) (equal? b x)) is a lambda function, i.e. a function with no name. Note that the x is not in the scope of the lambda function itself, but x is in the scope of the enclosing member function. Thus, strictly speaking, (lambda (b) (equal? b x)) is a closure, i.e. a function plus an environment that stores the value of x. For most purposes, closures and functions work just the same, i.e. you can call a closure in the same way you would call a regular function.

More Examples of Recursive Functions

It takes a bit of time to get used to writing recursive functions in Racket, so here are a few more examples to study.

;;
;; Remove all top-level occurrences of x from lst.
;;
(define (remove-all x lst)
  (cond [(null? lst) '()]
        [(equal? x (first lst))
         (remove-all x (rest lst))]
        [else
         (cons (first lst) (remove-all x (rest lst)))]))

;;
;; Replace all top-level occurrences of 'clinton with 'trump.
;;
(define (trumpify lst)
  (cond [(null? lst) '()]
        [(equal? 'clinton (first lst))
         (cons 'trump (trumpify (rest lst)))]
        [else
         (cons (first lst) (trumpify (rest lst)))]))

;;
;; Replace all top-level occurrences of old with new.
;;
(define (replace old new lst)
  (cond [(null? lst) '()]
        [(equal? old (first lst))
         (cons new (replace old new (rest lst)))]
        [else
         (cons (first lst) (replace old new (rest lst)))]))

;;
;; Returns a function that, when called, replaces all occurrences of old
;; with new on a given list. You can use it like this:
;;
;; > (define clean (make-replacer 'dirt 'soap))
;;
;; > (clean '(ice dirt dirt (1 dirt) cow dirt))
;; (ice soap soap (1 dirt) cow soap)
;;
(define (make-replacer old new)
  (lambda (lst) (replace old new lst)))

;;
;; Returns the number of numbers on lst, even numbers inside of lists.
;;
(define (deep-count-num lst)
  (cond [(null? lst) 0]
        [(list? (first lst))
         (+ (deep-count-num (first lst)) (deep-count-num (rest lst)))]
        [(number? (first lst))
         (+ 1 (deep-count-num (rest lst)))]
        [else
         (deep-count-num (rest lst))]))

Flattening a List

The deep-count-num function from the previous section can be re-written in an interesting way. Consider the problem of flattening a list, i.e. removing all the lists, and sub-lists, and leaving just the non-list elements in their original order. For example, Racket provides the flatten function for doing this:

> (flatten '(1 (a b) (c (d) ((e) g))))
(1 a b c d e g)

You could then write deep-count-num like this:

(define (deep-count-num lst)
    (count-num (flatten lst)))

The nice thing about this version of deep-count-num is that it is built from simpler functions.

Here’s an implementation of flatten:

(define (my-flatten x)
  (cond [(null? x) x]
        [(not (list? x)) x]
        [(list? (first x))
         (append (my-flatten (first x))
                 (my-flatten (rest x)))]
        [else (cons (first x)
                    (my-flatten (rest x)))]
))

append is an important Racket function. It takes 0 or more lists as input, and concatenates them, i.e. it returns a new list consisting of all the given lists combined into a single list, one after the other. For example:

> (append '(1 2) '(3 4 5))
'(1 2 3 4 5)
> (append '(once) '(upon a) '(time))
'(once upon a time)

Mapping, Filtering, and Folding

Next, we introduce some very useful functions that can be used to process lists in different ways. Many functions can be written entirely in terms of these functions (or functions like them), without using explicit recursion. Such functions are often shorter, easier to read, and more likely to be bug-free than their recursive equivalent.

Mapping

The map function applies a given function to every element of a list. For example:

> (map sqr '(1 2 3 4))
'(1 4 9 16)

> (map list '(this is a test))
'((this) (is) (a) (test))

In general, (map f '(x1 x2 ... xn)) returns the value of ((f x1) (f x2) ... (f xn)).

map is built-in, but it’s instructive to write our own version:

(define (my-map f lst)
  (if (empty? lst) '()
      (cons (f (first lst))
            (my-map f (rest lst)))))

Two useful variations of map are andmap and ormap. The andmap function returns #t when f evaluates to #t for every element of the list, and #f otherwise. For example:

> (andmap even? '(1 2 3 4))
#f
> (andmap even? '(12 2 30 4))
#t

Here’s an implementation:

(define (my-andmap pred? lst)
  (if (empty? lst) #t
      (and (pred? (first lst))
           (my-andmap pred? (rest lst)))))

We name the function pred? because it is a predicate, i.e. a function that takes one input and returns either #t or #f. Also, recall that and is short-circuited, so if (pred? (first lst)) evaluates to #f, then the recursive call to my-andmap is not made.

ormap return #t if 1, or more, elements on the list evaluates to #t, and #f otherwise, e.g.:

> (ormap even? '(1 2 3 4))
#t
> (ormap even? '(1 25 3 41))
#f

Here’s an implementation:

(define (my-ormap pred? lst)
  (if (empty? lst) #f         ;; base case different than my-andmap!
      (or (pred? (first lst))
          (my-ormap pred? (rest lst)))))

The built-in implementations of map, andmap, and ormap are actually a little more general than what we’ve shown, as they allow for multiple lists. For example:

> (map + '(1 2 3) '(4 5 6))
'(5 7 9)
> (andmap (lambda (a b) (> a b)) '(11 6 6) '(4 5 6))
#f
> (andmap (lambda (a b) (> a b)) '(11 6 7) '(4 5 6))
#t

Filtering

The filter function removes items from a list that don’t match a given predicate. For example:

> (filter odd? '(1 2 3 4 5 6))
'(1 3 5)
> (filter even? '(1 2 3 4 5 6))
'(2 4 6)
> (filter (lambda (lst) (>= (length lst) 2)) '((a b) (5) () (one two three)))
'((a b) (one two three))

Intuitively, you can think of filter as meaning “keep if” the predicate is true on a list element.

Here’s an implementation:

(define (my-filter pred? lst)
  (cond [(empty? lst) '()]
        [(pred? (first lst))
         (cons (first lst) (my-filter pred? (rest lst)))]
        [else
         (my-filter pred? (rest lst))]))

As an example of how you might use filter, suppose you want to count the number of symbols in the top-level of a list. You could do it like this:

> (length (filter symbol? '(we have 4 kinds 2 wheelers)))
4

Folding

Folding is a general-purpose operation that applies a function to a list in a way that combines all the elements into a final value. To understand how it works, first consider these examples of concrete folding functions:

(define (sum lst)
  (if (empty? lst) 0
      (+ (first lst) (sum (rest lst)))))

(define (prod lst)
  (if (empty? lst) 1
      (* (first lst) (prod (rest lst)))))

(define (my-length lst)
  (if (empty? lst) 0
      (+ 1 (my-length (rest lst)))))

These functions share a common a pattern that is captured by the following function:

;; > '(f a (f b (f c init)))
(define (fold-right f init lst)
  (if (empty? lst) init
      (f (first lst) (fold-right f init (rest lst)))))

We can simulate the three functions (and many others!) above like this:

> (fold-right + 0 '(1 2 3 4))
10
> (fold-right * 1 '(1 2 3 4))
24
> (fold-right (lambda (next accum) (+ accum 1)) 0 '(1 2 3 4))
4

The function f passed to fold-right takes two inputs, and it is helpful to call the first input next and the second input accum (as shown in the third example). The idea is that f is that next is assigned all the values of the list, one at a time, and accum is the accumulation of the results of f.

fold-right is quite a flexible function. For instance, it can be used to implement map:

(define (my-map2 f lst)
  (fold-right (lambda (next accum) (cons (f next) accum))
              '()
              lst))

> (my-map2 list '(one two (three)))
'((one) (two) ((three)))

> (my-map2 sqr '(2 3 5))
'(4 9 25)

Many programmers find folds tricky to think about at first. For example, what does (fold-right cons '() '(a b c d)) evaluate to?

Here is a perspective that can help with right folds. Any list such as '(a b c d) can be written as nested calls to cons like this:

> (cons 'a (cons 'b (cons 'c (cons 'd '()))))
'(a b c d)

You can think of (fold-right f init '(a b c d)) as replacing cons with f and '() with init:

(fold-right f init '(a b c d))

is the same as

(f 'a (f 'b (f 'c (f 'd init))))

For example, (fold-right + 0 '(1 2 3)) evaluates this expression:

(+ 1 (+ 2 (+ 3 0)))

So that means (fold-right cons '() '(a b c d)) evaluates to '(a b c d).

fold-right is called a right fold because it processes the items in the list in reverse order, from the right end to the left end. For example, (fold-right + 0 '(1 2 3)) evaluates to this: (+ 1 (+ 2 (+ 3 0)). In this expression, first (+ 3 0) is calculated, and the (+ 2 3) is calculated, and finally (+ 1 5) is calculated. The numbers are processed in the order 3, 2, and then 1.

For some functions, that might not be the order you want, and so there is also a fold-left function that applies f from left to right. It is usually defined like this:

;; > (f (f (f init a) b) c)
(define (fold-left f init lst)
  (if (empty? lst) init
      (fold-left f (f init (first lst)) (rest lst))))

A good feature of fold-left is that it is tail-recursive, i.e. the last thing fold-left does is call itself. Racket can automatically optimize this recursive call into a loop, which saves both time and memory. So in practice, left folds are usually preferable to right folds.

Both left and right folds are standard functions in Racket: foldr is right fold, and foldl is left fold. However, foldl is not defined quite the same as fold-left, e.g.:

> (foldl cons '() '(a b c))
'(c b a)
> (fold-left cons '() '(a b c))
'(((() . a) . b) . c)

Folding Example: The Structure of Folds

To help better understand how folds work, we can make folds that show the expression they evaluated. First, we define this function:

(define (show next acc)
  (cons 'f (cons next (list acc))))

By passing show to the various fold functions, the result will be a list that shows how it is evaluated. For example:

> (fold-right show '() '(a b c))
'(f a (f b (f c ())))

> (foldr show '() '(a b c))
'(f a (f b (f c ())))

This shows that both our fold-right, and the built-in Racket foldr evaluate to the same thing. However, as mentioned above, fold-left and foldl are different:

> (fold-left show '() '(a b c))
'(f (f (f () a) b) c)

> (foldl show '() '(a b c))
'(f c (f b (f a ())))

This last expression suggests that foldl could be implemented like this:

(define (my-foldl f init lst)
  (fold-right f init (reverse lst)))

However, this is not how Racket implements foldl. According to the documentation for foldl and foldr, foldl uses a constant amount of space to process the list, while foldr uses an amount of space proportional to the size of the list. But this implementation of my-foldl calls fold-right, meaning it uses space proportional to the size of the lst.

Notes on “Racket Essentials”: Pairs, Lists, and Racket Syntax

So far we’ve only used cons to construct a new list. For lists, (cons a b) only makes sense when b is a list (and a is any value). But it turns out that (cons a b) will work with any two values, e.g.:

> (cons 2 3)
'(2 . 3)
> (cons 'a 'b)
'(a . b)
> (cons (list 1 2 3) 'a)
'((1 2 3) . a)

All the results contain a ., and such values are sometimes called dotted pairs, or just pairs for short. The pair? predicate tests if a value is a pair, e.g.:

> (pair? '(1 . 2))
#t
> (pair? '(a . b))
#t
> (pair? '(one two))
#t
> (pair? '(3 4 5))
#t
> (pair? 'two)
#f

Notice that the list '(3 4 5) is a pair. That because lists are constructed from pairs, and '(3 4 5) is a short form for this expression:

> '(3 . (4 . (5 . ())))
'(3 4 5)

The list has the structure '(3 . otherstuff), and so it’s a pair. The list? predicate checks if something is a list, e.g.:

> (list? '(1 . 2))
#f
> (list? '(1 2))
#t

Both '(1 . 2) and (1 2) are pairs, but only '(1 2) is a list because it is has the proper structure: '(1 . (2 . ())).

The car and cdr functions are used to access the two elements in a pair. If p is a pair, then (car p) returns the first element, and (cdr p) returns the second element, e.g.:

> (car '(a . b))
'a
> (cdr '(a . b))
'b
> (car '(a . (b . (c . ()))))
'a
> (cdr '(a . (b . (c . ()))))
'(b c)

If p happens to be a proper list, then (car p) returns the first element of the list, and (cdr p) returns the rest of the list.

See cons cell box diagrams for examples of how to draw diagrams of pairs and lists.

Other Data Types

While we will focus almost exclusively on Racket lists in this course, it is worth noting that Racket also has built-in support for vectors and maps. For example, a vector has the form #(v0 v1 ... vn-1):

> #(blue red green)
'#(blue red green)

> (list? #(blue red green))
#f

> (vector-ref #(blue red green) 2)
'green

(vector-ref vec i) returns the element at index location i of vec (the first index location is 0).

See Hash Tables for how to use hash tables in Racket.

Quasiquoting

A quasiquote is usually written as a backwards quote mark in Racket. It is a more general form of regular quoting. For example:

> (define lst '(a b c))

> `(letters ,lst and chars ,@lst)
'(letters (a b c) and chars a b c)

Inside a quasiquoted list, a , means that next value is unquoted. A ,@ before a list means to splice the values of the list directly into the quoted expression, as shown.

In practice, quasiquoting can be very useful in certain situations. It can make certain Racket expressions much more compact and easier to write. For instance, it is often used with match, or when constructing complex lists.

Matching

Please read Matching from the Racket notes.

The match form is a powerful Racket construct that lets you check for patterns in almost any Racket expression. To see how it works, consider the problem of recognizing simple infix expressions, like these:

• numbers, e.g. -2, 4.6, 0, …
• unary expressions of the form (op x), e.g. (- 7), (- x), (+ a), ….
• binary expressions of the form (x op y), e.g. (1 + a), (41 / 2), …

Importantly, these are not recursive expressions: x and y are always numbers or symbols.

One way to solve the problem is as follows:

;; returns true iff x is a list of length n
(define (nlist? x n)
  (and (list? x)
       (= n (length x))))

(define all-bin-ops '(+ - * /))
(define all-unary-ops '(- +))

(define (is-basic-expr? x)
  (cond [(number? x) #t]
        [(and (nlist? x 2) (member (first x) all-unary-ops)) #t]
        [(and (nlist? x 3) (member (second x) all-bin-ops)) #t]
        [else #f]))

The helper function nlist? is quite useful here, and is how we distinguish between unary and binary expressions.

Now lets use match to write the same function:

(define (is-basic-expr2? x)
  (if (number? x) #t
      (match x
        [(list op a) (member op all-unary-ops)]
        [(list a op b) (member op all-biary-ops)]
        [_ #f])))

> (is-basic-expr2? '(s * r))
#f

> (is-basic-expr2? '(+ 5))
'(+)

> (is-basic-expr2? '(c ++))
#f

The idea is to use match to recognize patterns in lists, or other Racket data structures (like vectors). After (match x ...) you write [pattern expr] lists where pattern describes a possible pattern for x, and expr is the expression to evaluate if the pattern matches. This is similar to cond, but more powerful.

Notice that _ (not else!) is used to match anything. Here it is used as a catch-all in case none of the earlier patterns match.

Quasiquoting often works nicely with match, e.g.:

(define (is-basic-expr3? x)
  (if (number? x) #t
      (match x
        [`(,op ,a) (member op all-unary-ops)]
        [`(,a ,op ,b) (member op all-unary-ops)]
        [_ #f])))

For example, `(,op ,a) is the same as (list op a).

Another way to write this match is to explicitly list every case:

(define (is-basic-expr4? x)
  (if (number? x) #t
      (match x
        [`(- ,a) #t]
        [`(+ ,a) #t]
        [`(,a + ,b) #t]
        [`(,a - ,b) #t]
        [`(,a * ,b) #t]
        [`(,a / ,b) #t]
        [_ #f])))

This version is longer than the others, but it has the virtue of explicitly showing all the patterns. Notice that in the pattern `(,a + ,b), the + does not have comma in front of it. That means that there must be an actual + symbol in x to be matched.

Now suppose want to evaluate basic expressions, i.e. (3 + 6) evaluates to 9. A few small changes to is-basic-expr4 are all that’s needed:

(define (basic-eval x)
  (if (number? x) x
      (match x
        [`(- ,a) (- a)]
        [`(+ ,a) (+ a)]
        [`(,a + ,b) (+ a b)]
        [`(,a - ,b) (- a b)]
        [`(,a * ,b) (* a b)]
        [`(,a / ,b) (/ a b)]
        [_ (error "basic-eval: bad expression")])))

> (basic-eval '(4 + 3))
7
> (basic-eval '(4 / 3))
1 1/3
> (basic-eval '(4 ^ 2))
'error

If x is not a valid expression, then basic-eval causes an error using the error function.

Division by 0 causes this error:

> (basic-eval '(2 / 0))
. . /: division by zero

Lets suppose we want our own custom error message. We can easily do that by adding another pattern to basic-eval:

(define (basic-eval x)
  (if (number? x) x
      (match x
        [`(- ,a) (- a)]
        [`(+ ,a) (+ a)]
        [`(,a + ,b) (+ a b)]
        [`(,a - ,b) (- a b)]
        [`(,a * ,b) (* a b)]
        [`(,a / 0) (error "basic-eval: div by 0")]
        [`(,a / ,b) (/ a b)]
        [_ (error "basic-eval: bad expression")])))

> (basic-eval '(2 / 0))
. . basic-eval: div by 0

Note that the order of the patterns matters: we must check for division by 0 before regular division.

Now lets generalize basic-eval to allow for sub-expressions, i.e. we want evaluate expressions like ((4 / 2) - (2 * 3)). We could do it like this:

(define (arith-eval x)
  (if (number? x) x
      (match x
        [`(- ,a) (- (arith-eval a))]
        [`(+ ,a) (+ (arith-eval a))]
        [`(,a + ,b) (+ (arith-eval a) (arith-eval b))]
        [`(,a - ,b) (- (arith-eval a) (arith-eval b))]
        [`(,a * ,b) (* (arith-eval a) (arith-eval b))]
        [`(,a / ,b) (/ (arith-eval a) (arith-eval b))]
        [_ (error "arith-eval: bad expression")])))

Notice that the code, while not as short as it could be, is clear and simple: each possible pattern for x is explicitly given beside its associated evaluation.