Racket Explained

(cons a b)

Main Overview

cons is a very simple function, but it's often misunderstood by first-timers because of a lack of the prerequisite knowledge of how pairs work in Racket. All that cons does is cons-truct a new pair with a as its first value and b as its second. Where the confusion arises is that we are often wanting to deal with lists, rather than pairs, and so cons behaves slightly differently than we might expect. Check out the FAQ on pairs for a more in-depth explanation.

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

(lambda (args) body ...)

Main Overview

The lambda function is often people's first experience with procedures, that is, functions as data values. The name, lambda, comes from the Lambda Calculus, which is the formal mathematical system which originated the concept of doing operations on functions, and inspired the whole Lisp family of programming languages. So, that should give you an idea for how central this function is to everything we do in Racket.

The lambda function is used to create a new procedure. The first parameter, args holds the names of the parameters that the procedure should accept. The second parameter, body holds the expression that the procedure should evaluate.

; Procedure which adds 5 to a value
(lambda (x) (+ x 5)) -> #<procedure>

; Procedure which takes the average of 2 numbers
(lambda (a b) (/ (+ a b) 2)) -> #<procedure>

; Applying a procedure immediately after creation with lambda
((lambda (x) (+ x 5)) 8) -> 13

; Passing a procedure made with lambda as a parameter to another procedure
(map (lambda (x) (+ x 5)) '(1 2 3 4)) -> '(6 7 8 9)

Optional Parameters

You can assign default values to parameters, which gives the user the option to skip passing in a value for that parameter. The parameter will then be filled in with whatever the default value is. The syntax looks like this:

; Procedure with one required parameter and one optional parameter
(lambda (x [y 5]) (+ x y))

; Applying that procedure without specifying a value for y
((lambda (x [y 5]) (+ x y)) 11) -> 16

Note that you must put all optional parameters at the end of your parameter list, after all required parameters, so that the order that parameters are passed in is always clear.

; Optional parameter before required parameter
(lambda (x [y 5] z) (+ x (+ y z))) -> SYNTAX ERROR

Trailing Bodies

If you have keen eyes you may have noticed the ... in the definition of lambda and been wondering what that's all about. Well, as with most places that accept a code body, lambda will accept as many body expressions as you give it. These bodies will be executed one after another, and as is standard for Racket, the last body expression to be evaluated (also called tail position) will be the one that supplies the return value for the whole procedure.

((lambda (x y) (println x) (println y) (+ x y)) 4 5)
> 4
> 5
-> 9

(define id expr)
(define (head args) body ...)

Main Overview

You can think of the define function as Racket's version of a global variable/function definition. Define is one of the few functions which does not have a return value. Instead, it is used to bind an identifier id to a value expr. Once bound, you'll be able to refer to that value later in your program using the name that it was bound to, just like when you define a variable in Java or C. However, these definitions cannot be changed, so they're closer to constants in other languages than variables.

(define myconstant 8)

(println myconstant)
> 8

Of course, with the help of lambda or any other function that returns a procedure, you can also define functions this way! However, define also has an alternate syntax that is specifically for defining functions, which is kind of like a define and lambda combined. Instead of id, you specify the form that is to be used when calling the function, including its name and parameters. Then, as the second parameter you supply the body of the function. Below are examples of the same function being defined in Java syntax as well as both Racket syntaxes, for clarity:

// in Java
public static var computeAverage(var x, var y)
{
    return (x + y) / 2.0;
}

; in Racket, with lambda
(define compute-average (lambda (x y) (/ (+ x y) 2)))

; in Racket, with alternate define syntax
(define (compute-average x y) (/ (+ x y) 2))

Nested Function Definition

The alternate syntax of define has a bonus feature that may occasionally be useful if you can wrap your head around it. That is the ability to define nested functions.

(define ((increase-by x) y) (+ y x))

((increase-by 5) 4) -> 9

To better understand what's going on, let's take another look at the define alternate syntax:

(define (head args) body ...)

What I neglected to point out before is that the head part of this definition is actually recursive. That is, you can replace head with another (head args) as many times as you want and the syntax will still be valid.

(define ((head args) args) body ...)
(define (((head args) args) args) body ...)
(define ((((head args) args) args) args) body ...)
...
in general:
head -> (head args) or id

What does this do though? Well, what's happening is it's defining a function which returns another function, which finally returns a value. It's as if the function (increase-by x) itself is the name of the main function ((increase-by x) y).

This is all still just shorthand; it's nothing you couldn't achieve with the basic define syntax and some lambdas, as you can see demonstrated below:

; Function from the earlier example
(define ((increase-by x) y) (+ y x))

; The same function defined with basic syntax
(define increase-by (lambda (x) (lambda (y) (+ y x))))

Why would we want this? Well, the first syntax up above is much shorter and also clearer about the usage of the function that we're defining. As for why we'd want a nested function like that, there are times when we'd like to define a whole set of related functions, such as increase-by-1, increase-by-10, increase-by-100 and this can be a neat and scalable way of doing so.

(define ((increase-by x) y) (+ y x))

(define (increase-by-1 y) (increase-by 1))
(define (increase-by-10 y) (increase-by 10))
(define (increase-by-100 y) (increase-by 100))

(println (increase-by-100 (increase-by-10 4)))
> 114

(cond [test body ...] ... [else body ...])

Main Overview

The name cond stands for conditional, and you can think of cond as Racket's version of an if/else chain. There is also the if function, but cond is usually preferred as it is more flexible. cond can be confusing at first because of its syntax, but once you get used to it, it's quite straightforward. It accepts any number of clauses, by convention indicated with square brackets, and each clause contains a test expression followed by any number of body expressions. Starting with the first and working its way down, cond evaluates the test expression of each clause. If the test returns true, the body for that clause is evaluated and its result is returned for the whole cond expression. If the test returns false, the body for that clause is ignored and cond continues to the next clause.

The final clause in a cond expression can optionally use the word "else" in place of a test expression, in which case the body is always evaluated as long as cond reaches that clause. There are actually 2 other types of clause which are accepted by cond, but they are seldom used. You can read about them in the official docs page.

I figure the easiest way to get a feel for the syntax of cond is to compare it to an identical control flow in a more familiar language. Here is an example of the same piece of code written in both Java and Racket:

// Java
public static String aiChatBot(String prompt)
{
    if(prompt.equals("quit"))
    {
        return "Goodbye!";
    }
    else if(prompt.startsWith("how do i"))
    {
        return "I am programmed not to answer questions like \""
            .concat(prompt).concat("\" for ethical reasons.");
    }
    else
    {
        return "I'm not sure I understand. Please rephrase your question.";
    }
}

; Racket
(define (ai-chat-bot prompt)
  (cond
    [(equal? prompt "quit") "Goodbye!"]
    [(string-prefix? prompt "how do i")
     (string-append "I am programmed not to answer questions like \""
                    prompt "\" for ethical reasons.")]
    [else "I'm not sure I understand. Please rephrase your question."]))

(map proc lst ...)

Main Overview

Map is one of the most fundamental operations that can be done with procedures. Its name comes from the terminology of set theory, where a map refers to a type of relation between two sets where every member of the input set is associated with exactly one member of the output set, much like how we associate points on the Earth's surface with points on a flat page when we draw geographical maps. The map function takes a procedure, and applies it in sequence to every member of a list, and then returns a list of the results in the same order.

Map is a really useful tool to have at your disposal because in many cases it can greatly simplify things when you would otherwise need to write a loop to iterate through a list. Below are some examples of how you might use the map function:

; Generating the first 10 perfect square numbers
(map sqr (range 10)) -> '(0 1 4 9 16 25 36 49 64 81)

; Running a logical test on each element of a list
(map odd? '(8 2 9 10 13 5 28)) -> '(#f #f #t #f #t #t #f)

; Appending a string to each element of a list of strings
(map (lambda (s) (string-append "P" s))
     '("ython" "erl" "HP" "ascal" "rolog"))
-> '("Python" "Perl" "PHP" "Pascal" "Prolog")

Multiple Input Lists

Map doesn't just work with procedures that have one input and one output. Notice the ... in the function signature up above. Map can accept more than one input list, and if you supply additional ones, map will use them to fill in additional parameters in proc.

; a function that takes two parameters 
(* 4 3) -> 12

; calling map with two input lists
(map *
     '(2 5 7 3)
     '(8 4 3 9)) -> '(16 20 21 27)

; map will throw an error if the input lists
; don't all have the same number of elements
(map *
     '(2 5 7)
     '(8 4 3 9))
-> error: map: all lists must have the same size

(andmap proc lst ...)
(ormap proc lst ...)
(foldl proc init lst ...)

Main Overview

These three functions are variants of the map function. Like map, they too run a given procedure on every element of a given list (or set of lists). However, rather than a list, these functions combine the results of each call to proc to return a single value.

andmap will return true if and only if proc returns true for every element of the list, and false otherwise.

ormap will return true unless proc returns false for every element of the list, and false otherwise.

foldl is a more general form of this operation and we'll discuss it further down.

; verify that every element of a list is an integer
(andmap integer? '(1 3 8 5 2)) -> #t
(andmap integer? '(1 3 8 4.1 2)) -> #f

; test if there exists an element of a list that is an integer
(ormap integer? '(3.8 7.4 "x" #f 200.9)) -> #f
(ormap integer? '(3.8 8 "x" #f 200.9)) -> #t

; test if the elements of two lists sum to 15 in each place
(andmap (lambda (a b) (eq? (+ a b) 15))
        '(1 2 3 4)
        '(14 13 12 11)) -> #t

; andmap and ormap are useful in evaluating the "for all"
; and "there exists" predicates of first order logic

; Test a given list, lst, for the condition:
; for all x in lst, there exists a, b in x for which a + b = 15

(andmap
 (lambda (x)
   (ormap
    (lambda (a)
      (ormap
       (lambda (b)
         (eq? (+ a b) 15))
       x))
    x))
 lst)

foldl

foldl is a more versatile form of map, andmap and ormap, giving you the freedom to specify how the values of the list(s) are combined. It takes an additional parameter called init. foldl starts from the left of the list (hence the "l") and calls proc, passing in the first element of the list along with init as parameters. It then passes the second element of the list along with the result of the first call to proc into the next call to proc, and then it passes the third element along with the result of that call into the next call, and on and on until it progresses through the whole list.

I find it easiest to imagine the flow of foldl as if I was literally folding a brochure:

foldl is a little less intuitive than the other functions in the map family, but it is incredibly powerful. Here are just a few examples of how it can be used:

; implementing a sum function using foldl
(define (my-sum lst) (foldl + 0 lst))

; implementing a reverse function using foldl
(define (my-reverse lst) (foldl cons '() lst))

; implementing a map function using foldl
(define (my-map proc lst) (foldl
                           (lambda (a b)
                             (append b (list (proc a))))
                           '()
                           lst))

; implementing an andmap function using foldl
(define (my-andmap proc lst) (foldl
                              (lambda (a b) (and (proc a) b))
                              #t
                              lst))

; implementing an ormap function using foldl
(define (my-ormap proc lst) (foldl
                             (lambda (a b) (or (proc a) b))
                             #f
                             lst))

; in the English card game of Cribbage, part of scoring
; a hand of cards involves counting the number of subsets of
; cards in the hand whose values add up to 15.

; Here is a Cribbage hand 15 counter using foldl:
(define (count-15s card-values)
  (foldl
   (lambda (sublist tally)
     (if (eq? (foldl + 0 sublist) 15)
         (add1 tally)
         tally))
   0
   ; the combinations function returns all sublists of a list
   ; AKA it takes the powerset
   (combinations card-values)))

; a pretty average Cribbage hand
(count-15s '(2 7 8 7 1 3 10)) -> 4

; the theoretical perfect hand
(count-15s '(4 4 5 5 5 6 6)) -> 13

(curry proc)
(curry proc v ...)

Main Overview

Currying is one of the more advanced standard operations in functional programming and it's named after mathematician Haskell Curry (who also has 3 different programming languages named after him). It describes the process of breaking down a procedure so that parameters can be fed to it one by one rather than all at once.

When you call curry on a procedure, it returns a curried version of that procedure, which will behave exactly like the original procedure if it is called with the required number of parameters.

cons -> #<procedure:cons>

(curry cons) -> #<procedure:curried:cons>

(cons 2 '(6)) -> '(2 6)

((curry cons) 2 '(6)) -> '(2 6)

However, if you feed a curried procedure fewer parameters than it requires, it will wait, returning itself (to be precise, a version of itself that remembers the parameters you passed) until it recieves enough parameters, at which point it will finally execute.

(define (add-5-numbers a b c d e) (+ a b c d e))

((curry add-5-numbers) 1) -> #<procedure:curried:add-5-numbers>
(((curry add-5-numbers) 1) 2 3) -> #<procedure:curried:add-5-numbers>
((((curry add-5-numbers) 1) 2 3) 4) -> #<procedure:curried:add-5-numbers>
(((((curry add-5-numbers) 1) 2 3) 4) 5) -> 15

; You can also pass in parameters with the initial call to curry
((curry add-5-numbers 1 2 3 4) 5) -> 15

Example

So why is this useful? Well, there are often times in a program where you'd like to specify some parameters to a procedure before you specify others. Without curry, you would have to wait until you know every parameter you need to pass to the procedure, and this might mean jumping through a lot of hoops to make sure that all these values are accessible in the same scope. Let's take a look at an example.

; This function searches through a list of numbers and returns
; true if there exists a set of 3 numbers in the list that form
; a pythagorean triple (a^2 + b^2 = c^2).
(define (contains-pythagorean-triple? A)
  (contains-pythagorean-triple?-helper A '()))

; We accomplish this by creating a helper function which does all
; the real work and takes an additional parameter: "test-vals"

; test-vals will be used to store a list of the elements that
; are currently being tested for pythagorean triples. This is a
; pretty standard algorithm for finding particular subsets of a
; list of elements.
(define (contains-pythagorean-triple?-helper A test-vals)
  (cond
    ; Once test-vals has amassed 3 elements, run them through
    ; is-pythagorean-triple? and return the result.
    [(= (length test-vals) 3)
     (is-pythagorean-triple?
      (first test-vals)
      (second test-vals)
      (third test-vals))]
    ; If we've reached the end of list A, return false.
    [(empty? A) #f]
    ; Otherwise, we branch into two recursive calls:
    ; One where we include (car A) in test-vals, and one
    ; where we do not include (car A) in test-vals.
    [else (or
           ; Case where we don't add (car A) to test-vals
           (contains-pythagorean-triple?-helper
            (cdr A) test-vals)
           ; Case where we do add (car A) to test-vals
           (contains-pythagorean-triple?-helper
            (cdr A) (cons (car A) test-vals))
           )]
    ))

; Function to test if 3 numbers form a pythagorean triple
(define (is-pythagorean-triple? a b c)
  (let ([a-squared (* a a)]
        [b-squared (* b b)]
        [c-squared (* c c)])
    (cond
      [(or
        (= (+ a-squared b-squared) c-squared)
        (= (+ c-squared a-squared) b-squared)
        (= (+ b-squared c-squared) a-squared)
        ) #t]
      [else #f]
      )))

; Some example calls
(contains-pythagorean-triple? '(3 4 5)) -> #t
(contains-pythagorean-triple? '(5 12 13)) -> #t
(contains-pythagorean-triple? '(3 4 6 8)) -> #f
(contains-pythagorean-triple? '(9 7 4 1 3 11 5)) -> #t

Now, this code works just fine. It solves the problem at hand and pretty efficiently as well. However, it is a bit cumbersome having to keep track of this list of elements that we're testing. The following example shows the same function but utilizing curry. Notice how test-vals is nowhere to be seen; instead of having to manually keep track of the elements we're testing, we just immediately pass them into the curried version of is-pythagorean-triple?, which feels a lot cleaner.

; The same function but utilizing curry
(define (contains-pythagorean-triple? A)
  (contains-pythagorean-triple?-helper
   ; We pass A to the helper function as before, but this time,
   ; instead of passing an empty list for test-vals, we pass a
   ; freshly curried version of is-pythagorean-triple?
   A (curry is-pythagorean-triple?)
   ))

(define (contains-pythagorean-triple?-helper A curried-test)
  (cond
    ; Instead of that bulky expression from the previous example,
    ; we just check whether curried-test has returned yet and pass
    ; on the result if it has.
    [(boolean? curried-test) curried-test]
    [(empty? A) #f]
    [else (or
           ; Case where we don't pass (car A) to curried-test
           (contains-pythagorean-triple?-helper
            (cdr A) curried-test)
           ; Case where we do pass (car A) to curried-test
           (contains-pythagorean-triple?-helper
            (cdr A) (curried-test (car A)))
           )]
    ))