Introduction to Scheme¶
Scheme is a popular dialect of Lisp, a language developed in the 1950s and 1960s by John McCarthy and his students. Lisp is based on the lambda calculus, a mathematical formalism for defining and executing functions.
Despite being so simple and not quite having achieved mainstream success on its own, Lisp has proven to be an influential language, and has been the source of ideas found in many other languages.
Getting Scheme¶
These notes will be using MIT Scheme, a popular version of Scheme that is easy to use.
To install MIT Scheme on Ubuntu Linux, run this command in a shell:
$ sudo apt-get install mit-scheme
For other systems, see the MIT Scheme home page.
Running Scheme¶
Once it’s installed, you can run it at the command-line like this:
$ mit-scheme
MIT/GNU Scheme running under GNU/Linux
Type `^C' (control-C) followed by `H' to obtain information about interrupts.
Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Image saved on Tuesday October 22, 2013 at 12:31:09 PM
Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/i386 4.118
Edwin 3.116
1 ]=>
]=> is the interpreter prompt, and means that it is waiting for you to
type something. So try this:
1 ]=> (* 2 3 5)
;Value: 30
1 ]=>
The Scheme expression (* 2 3 5) calculates the product of 2, 3, and 5,
i.e. \(2 \cdot 3 \cdot 5 = 30\).
While it is possible to compile Scheme, we will stick to just the interpreter for this course.
Quitting Scheme¶
To exit the interpreter, type ctrl-d:
1 ]=>
Kill Scheme (y or n)? Yes
Moriturus te saluto.
Or by typing (exit) and return:
1 ]=> (exit)
Kill Scheme (y or n)? Yes
Moriturus te saluto.
Note
“Moriturus te saluto” is Latin for “I who am about to die salute you”.
Loading Files¶
We’ll usually be putting Scheme functions in text files that are loaded into
the interpreter. For example, suppose the file circle.scm contains this:
;;; calculates perimeter of a circle of radius r
(define circle-perim
(lambda (radius)
(* 2 3.14 radius)
)
)
Then in Scheme we can load and run it like this:
1 ]=> (load "circle.scm")
1 ]=> (circle-perim 2)
;Value: 12.56
1 ]=>
Using Scheme in an Editor¶
While you can use MIT-Scheme directly at the command-line as above, it lacks many basic editing features and so is a very unpleasant experience. Most programmers prefer to run it directly in their text editor.
For example, if you are using Sublime Text as your editor, then you can install the SublimeREPL package, which lets you run an interpreter in a Sublime window.
Another popular editor for Lisp-like languages is Emacs, which comes ready to run Scheme in an editor window.
Using Scheme’s Interactive Interpreter¶
We’ll be using Scheme via its interpreter, or REPL. REPL stands for read-eval-print loop, and it lets us evaluate Scheme expressions one at a time. For instance:
1 ]=> (+ 3 2)
;Value: 5
1 ]=> (* 10 4)
;Value: 40
1 ]=> (- 5 8)
;Value: -3
1 ]=> (/ 6 2)
;Value: 3
1 ]=> (/ 5 2)
;Value: 5/2 ;; 5/2 is a rational value
Right away you can see that Scheme looks different than most languages. All
functions in Scheme 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). Scheme uses prefix notation for everything,
which, once you get used to it, is simple and consistent.
Another other interesting feature of Scheme notation is that expressions are
always delineated by open ( and close ) brackets. As you will see,
Scheme programs can end up having a lot of brackets, and making sure they
all match can be tricky.
You can pass multiple arguments to arithmetic operations:
=> (+ 1 2 3)
6
=> (* 1 6 2 2)
24
=> (/ 100 10 5)
2
=> (- 1 2 3)
-4
Or combine numbers and expressions:
=> (+ (- 1 2 3) (* 4 5))
16
Notice that Scheme supports a built-in rational numeric type, which is not common in mainstream languages:
1 ]=> (+ 1/2 1/2)
;Value: 1
1 ]=> (+ 1/2 1/2 1/2)
;Value: 3/2
Number Basics¶
Lets look at the basic types of values in Scheme.
The standard Scheme functions integer?, rational?, real?,
complex?, and number? test for various kinds of numbers. For example:
;;
;; integers
;;
1 ]=> (integer? 5)
;Value: #t
1 ]=> (integer? 6.0)
;Value: #t
1 ]=> (integer? 6.1)
;Value: #f
;;
;; rationals
;;
1 ]=> (rational? 6/3)
;Value: #t
1 ]=> (rational? 6)
;Value: #t
1 ]=> (rational? 6.1)
;Value: #t
;;
;; reals
;;
1 ]=> (real? 2)
;Value: #t
1 ]=> (real? 2.1)
;Value: #t
1 ]=> (real? 6/17)
;Value: #t
;;
;; complex
;;
1 ]=> (complex? 3.1+4i)
;Value: #t
1 ]=> (complex? 3.1+0i)
;Value: #t
1 ]=> (complex? 6)
;Value: #t
The value #t means true, and #f means false. The number? function
can be used to test if a value is any kind of number at all.
Here are a few handy built-in numerical functions: zero?, positive?,
negative?, odd?, even?. For example:
1 ]=> (zero? (- 5 5))
;Value: #t
1 ]=> (positive? (- 5 5))
;Value: #f
1 ]=> (positive? 22)
;Value: #t
1 ]=> (negative? 0)
;Value: #f
1 ]=> (negative? -3)
;Value: #t
1 ]=> (odd? 101)
;Value: #t
1 ]=> (even? 2038)
;Value: #t
There’s also min and max:
1 ]=> (min 8 3 -2 9 1 0)
;Value: -2
1 ]=> (max 8 3 -2 9 1 0)
;Value: 9
See the MIT Scheme documentation for a list of the other mathematical functions.
Symbol Basics¶
Symbols are a kind of value that are not found in many other mainstream
languages. Use symbol? to test if a value is a symbol:
1 ]=> (symbol? 'a)
;Value: #t
1 ]=> (symbol? 'apple)
;Value: #t
1 ]=> (symbol? 'first-ever-airplane)
;Value: #t
1 ]=> (symbol? 4)
;Value: #f
1 ]=> (symbol? odd?)
;Value: #f
1 ]=> (symbol? x)
;Unbound variable: x
Symbols are just values with names, and we don’t usually care about the individual characters they’re made from. While they may look like strings, they are not. Like other Scheme names, symbol names cannot contain certain characters (such as spaces).
Note the ' in front of all the valid symbols. Quoting is an important part
of Scheme, and it is necessary to distinguish a symbol from a variable. For
example, x is a variable, while 'x is a symbol:
1 ]=> (symbol? 'x)
;Value: #t
1 ]=> (symbol? x)
;Unbound variable: x
The expression (symbol? x) can’t be evaluated because Scheme 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:
1 ]=> 'a
;Value: a
1 ]=> 'cat
;Value: cat
This contrasts with variables, which evaluate to the value they’re bound to.
define is one way to create new variables:
1 ]=> (define pi 3.14)
;Value: pi
1 ]=> pi
;Value: 3.14
1 ]=> (* 2 pi)
;Value: 6.28
Here, pi is a variable bound to the value 3.14. Thus, pi evaluates to
3.14, and can be used anywhere a number is needed.
Notice also that the variable pi does not have a type. This is a key
feature of Scheme: it is a weakly typed language, meaning that the type of
most expressions is not known until the expression is evaluated (in contrast
to more strongly typed languages where types are known at compile-time).
pi is not a symbol, it’s a variable:
1 ]=> (symbol? pi) ;; pi is a variable
;Value: #f
1 ]=> (symbol? 'pi) ;; 'pi is a symbol
;Value: #t
You can also quote lists in Scheme, e.g.:
1 ]=> (+ 2 3)
; Value: 5
1 ]=> '(+ 2 3)
; Value: (+ 2 3)
Note that '(+ 2 3) is not a symbol. Instead, it’s a list:
1 ]=> (symbol? '(+ 2 3))
; Value: #f
1 ]=> (list? '(+ 2 3))
; Value: #t
If you don’t put a ' in front of the list, then it gets evaluated (to 5):
1 ]=> (list? (+ 2 3))
; Value: #f
In general, a quoted expression evaluates to itself. It causes the thing being quoted to not be evaluated. This is one of the most useful features of Scheme.
There is another, less common, way of quoting things in Scheme. You can use
quote like this:
1 ]=> (symbol? (quote (+ 2 3)))
; Value: #f
1 ]=> (list? (quote (+ 2 3)))
; Value: #t
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.
Note that quote has unusual behaviour:
1 ]=> (quote (+ 2 3))
; Value: (+ 2 3)
The (+ 2 3) does not get evaluated inside of quote. Thus, quote
is a special form: it does not evaluate its argument (if it did, then it
wouldn’t work!).
Basics of Lists¶
A list is a sequence of 0, or more, values. The values in a list can be any Scheme value: numbers, symbols, other lists, etc.
As with symbols, literal lists usually begin with a ':
1 ]=> '(1 2 3)
;Value 13: (1 2 3)
1 ]=> '(my dog has fleas)
;Value 14: (my dog has fleas)
1 ]=> '(my dog (and hamster) have 10 fleas each)
;Value 15: (my dog (and hamster) have 10 fleas each)
If you don’t start the list with a ', Scheme tries to evaluate the list
as if it were a function call, e.g.:
=> (1 2 3)
;The object 1 is not applicable.
Here, Scheme 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 in it, and is written as either ()
or '(). Use null? to test if a list is empty:
1 ]=> (null? '(1 2))
;Value: #f
1 ]=> (null? '())
;Value: #t
The difference between quoted and unquoted lists is important in Scheme, and in more complex programs it can start to get tricky. Consider this expression:
1 ]=> (min 3 1)
;Value: 1
(min 3 1) is an unquoted list, so Scheme evaluates it as a function call.
It passes 3 and 1 to the function min is bound to.
If, instead, you put a ' in front of this list, then it evaluates to
itself:
1 ]=> '(min 3 1)
;Value 16: (min 3 1)
Note
Quoted lists are similar in spirit to strings in other languages. For example, in Go, this statement prints 3:
fmt.Println(1 + 2)
But this statement prints "1 + 2":
fmt.Println("1 + 2")
The difference is that, on its own, 1 + 2 is an expression that
evaluates to 3. But put it inside quotes, then it’s just a string of 5
characters that are not evaluated.
Quoted lists are the same idea: the unquoted expression (+ 1 2)
evaluates to 3, while the quoted expression '(+ 1 2) evaluates to the
list (+ 1 2).
List Processing¶
Scheme has a number of useful built-in list processing functions. When thinking about the performance characteristics of these functions, keep in mind that Scheme lists are singly-linked lists, and so a function that traverses an entire list usually runs in linear time.
The car function returns the first element of a list:
1 ]=> (car '(1 2 3))
;Value: 1
1 ]=> (car '((1 2) 3 4))
;Value 18: (1 2)
1 ]=> (car '(my dog has fleas))
;Value: my
1 ]=> (car '())
;The object (), passed as the first argument to car, is not the correct type.
The empty list has no first element, so (car '()) is an error.
The cdr function returns everything on a list except for the first
element:
1 ]=> (cdr '(1 2 3))
;Value 19: (2 3)
1 ]=> (cdr '((1 2) 3 4))
;Value 20: (3 4)
1 ]=> (cdr '(my dog has fleas))
;Value 21: (dog has fleas)
1 ]=> (cdr '())
;The object (), passed as the first argument to cdr, is not the correct type.
Note
The names car and cdr are traditional, and refer to the
underlying hardware of the original computer on which Lisp was first
implemented.
Some languages use first instead of car, and rest instead of
cdr.
The cons function “constructs” a new list by adding a new element to the
start of a given list:
1 ]=> (cons 1 '(2 3))
;Value 22: (1 2 3)
1 ]=> (cons '(2 3) '(3 4))
;Value 23: ((2 3) 3 4)
1 ]=> (cons 'my '(dog has fleas))
;Value 24: (my dog has fleas)
1 ]=> (cons 'x '())
;Value 25: (x)
car, cdr, and cons work well together, e.g.:
1 ]=> (cons (car '(1 2 3)) (cdr '(1 2 3)))
;Value 26: (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:
1 ]=> (cons 'a (cons 'b (cons 'c (cons 'd '()))))
;Value 27: (a b c d)
Since Scheme implements lists as singly-linked lists, then car, cdr,
and cons all run in worst-case \(O(1)\) time.
Another way to create a list is to use the list function:
1 ]=> (list 1 2 3)
;Value 28: (1 2 3)
1 ]=> (list '(1 2) 3 4)
;Value 29: ((1 2) 3 4)
1 ]=> (list 'my 'dog 'has 'fleas)
;Value 30: (my dog has fleas)
1 ]=> (list)
;Value: ()
These functions can be combined to do many different useful things. For
example, the car of a lists cdr is its second element:
1 ]=> (car (cdr '(a b c d)))
;Value: b
Scheme actually as a predefined function called cadr that does the same
thing.
Scheme even lets you do things like this:
1 ]=> ((car (list min max)) 41 2 3)
;Value: 2
To evaluate this entire expression, (car (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 (car (list min max)) then becomes (car
(<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:
1 ]=> ((car '(min max)) 41 2 3)
;The object min is not applicable.
The difference here is that the min inside the quoted list is not
evaluated, and so the result of (car '(min max)) is just the symbol
min. In contrast, when (list min max) is called, both min` and
``max are evaluated, and replaced with their corresponding functions. So
(car (list min max)) is the min function.
Functions¶
Functions are at the heart of Scheme, and there are a number of ways to
create them. One way is to use define:
(define add1
(lambda (n)
(+ n 1)
)
)
Or equivalently:
(define (add1 n)
(+ n 1)
)
This defines a function named add1 that takes a single value, n, as
input. It returns the value of (+ 1 n):
1 ]=> (add1 5)
;Value: 6
1 ]=> (add1 (add1 (add1 3)))
;Value: 6
Notice the type of n is not specified. Scheme is dynamically typed:
it doesn’t check the type of a value until run-time.
Here’s another function:
(define circle-area
(lambda (radius)
(* 3.14 radius radius)
)
)
1 ]=> (circle-area 3)
;Value: 28.259999999999998
1 ]=> (circle-area (add1 4))
;Value: 78.5
In the following function, p1 and p2 are assumed to both be of the
form (x y):
(define add-points
(lambda (p1 p2)
(list (+ (first p1) (first p2))
(+ (second p1) (second p2))
)
)
)
1 ]=> (add-points '(2 1) '(5 9))
;Value 11: (7 10)
Logical Expressions¶
You can use and, or, and not to evaluate logical expressions in
Scheme. For example:
(define all-diff?
(lambda (x y z)
(and (not (equal? x y))
(not (equal? x z))
(not (equal? y z))
)
)
)
1 ]=> (all-diff? 1 2 1)
;Value: #f
1 ]=> (all-diff? 1 2 -5)
;Value: #t
and is what is known in Scheme as a special form. It is different
than an ordinary function because it does not immediately evaluate the
expressions passed to it. Instead, and evaluates its arguments one at a
time from left to right, and stops immediately after the first expression that
evaluates to false; none of the expressions after that are evaluated.
or is also a special form, e.g.:
(define any-same?
(lambda (x y z)
(or (equal? x y)
(equal? x z)
(equal? y z)
)
)
)
1 ]=> (any-same? 3 5 3)
;Value: #t
1 ]=> (any-same? 3 5 13)
;Value: #f
Similar to and, the or special form evaluates its inputs one at a
time, from left to right, stopping after finding the first true expression
(and not evaluating anything after that).
not works as expected, i.e. it flips true to false and false to true:
(define any-same2?
(lambda (x y z)
(not (all-diff? x y z))
)
)
Decisions with cond¶
cond is a special form in Scheme that is similar to if-else structures in
other languages. Consider this function:
(define sign
(lambda (n)
(cond ((< n 0) 'negative)
((= n 0) 'zero)
(#t 'positive)
)
)
)
1 ]=> (sign -4)
;Value: negative
1 ]=> (sign 0)
;Value: zero
1 ]=> (sign 5)
;Value: positive
A cond expression consists of 2-element (test value) lists. For
example, (< n 0) is a test, and 'negative is it’s corresponding value.
cond evaluates its pairs one at a time in the order they occur. If a test
evaluates to true, its corresponding value is returned. The final test is
#t, which is always true, and so it serves the same purpose as else in
other programming languages.
Instead of #t, you can also use else:
(define sign
(lambda (n)
(cond ((< n 0) 'negative)
((= n 0) 'zero)
(else 'positive)
)
)
)
This is a little more readable, and so we’ll usually write else instead of
#t.
Recursive Functions¶
If you want to determine the length of a list, Scheme provides a built-in
length function:
1 ]=> (length '(1 (2 3) 4))
;Value: 3
We could also write our own function using recursion like this:
(define len
(lambda (lst)
(cond
((null? lst) 0) ;; base case
(else (+ 1 (len (cdr lst)))) ;; recursive case
)
)
)
len has two cases:
- base case: when the list
lstis empty - recursive case: calculate the length of the
cdroflst, then add 1
As you can see, you must take care to get all the parentheses to match!
Here’s another example of recursion:
;; Returns true if x is in lst, and false otherwise.
(define member
(lambda (x lst)
(cond
((null? lst)
#f)
((equal? x (car lst))
#t)
(else
(member x (cdr lst)))
)
)
)
Recall that the symbol? functions tests if an object is a symbol (such as
'cat). The following function returns the number of symbols in a list:
(define count-sym
(lambda (lst)
(cond
((null? lst)
0)
((symbol? (car lst))
(+ 1 (count-sym (cdr lst))))
(else
(count-sym (cdr lst)))
)
)
)
We could have written count-sym more compactly like this:
(define count-sym
(lambda (lst)
(if (null? lst)
0
(+ (if (symbol? (car lst)) 1 0)
(count-sym (cdr lst)))
)
)
)
Instead of cond, this uses if, which allows only one test and one
value, i.e. (if test true-val false-val). In some cases, it can be more
readable than ``cond.
Suppose now we want to count how many numbers are in a list. We can make a
small modification to count-sym to get this:
(define count-num
(lambda (lst)
(cond
((null? lst)
0)
((number? (car lst))
(+ 1 (count-num (cdr lst))))
(else
(count-num (cdr lst)))
)
)
)
Compared to count-sym, count-num is the same except for two
differences: number? is used instead of symbol?, and each occurrence
of count-sym 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-fn
(lambda (fn? lst)
(cond
((null? lst)
0)
((fn? (car lst))
(+ 1 (count-fn fn? (cdr lst))))
(else
(count-fn fn? (cdr lst)))
)
)
)
To use it we pass in any function that takes a single input value and returns
either true or false:
1 ]=> (count-fn even? '(1 2 3 4 5 6 7))
;Value: 3
1 ]=> (count-fn odd? '(1 2 3 4 5 6 7))
;Value: 4
1 ]=> (count-fn number? '(1 2 3 4 5 6 7))
;Value: 7
1 ]=> (count-fn symbol? '(1 2 3 4 5 6 7))
;Value: 0
Using count-fn, 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)))
Here’s another example of the same sort of thing. This is a generalized
version of the member function from above:
(define member-fn
(lambda (fn? lst)
(cond
((null? lst)
#f)
((fn? (car lst))
#t)
(else
(member-fn fn? (cdr lst)))
)
)
)
(member-fn fn? lst) returns true if there is one, or more, elements x
on lst such that (fn? x) is true.
For example, to test if a lst 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
(lambda (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 in it 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¶
;;
;; Remove all top-level occurrences of x from lst.
;;
(define remove-all
(lambda (x lst)
(cond
((null? lst)
'())
((equal? x (car lst))
(remove-all x (cdr lst)))
(else
(cons (car lst) (remove-all x (cdr lst))))
)
)
)
;;
;; Replace all top-level occurrences of 'clinton with 'trump.
;;
(define trumpify
(lambda (lst)
(cond
((null? lst)
'())
((equal? 'clinton (car lst))
(cons 'trump (trumpify (cdr lst))))
(else
(cons (car lst) (trumpify (cdr lst))))
)
)
)
;;
;; Replace all top-level occurrences of old with new.
;;
(define replace
(lambda (old new lst)
(cond
((null? lst)
'())
((equal? old (car lst))
(cons new (replace old new (cdr lst))))
(else
(cons (car lst) (replace old new (cdr 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
(lambda (old new)
(lambda (lst) (replace old new lst))
)
)
;;
;; Returns the number of numbers on lst, even numbers inside of lists.
;;
(define deep-count-num
(lambda (lst)
(cond
((null? lst)
0)
((list? (car lst))
(+ (deep-count-num (car lst)) (deep-count-num (cdr lst))))
((number? (car lst))
(+ 1 (deep-count-num (cdr lst))))
(else
(deep-count-num (cdr lst)))
)
)
)
Flattening a List¶
The deep-count-num function from the previous section is can be re-written
in an interesting way. Consider the problem of flattening a list, i.e.
removing all the lists, and sub-lists, from a list and leaving just the
non-list elements in their original order. For example:
> (flatten '(1 (a b) (c (d) ((e) g))))
(1 a b c d e g)
With flatten, you could then write deep-count-num like this:
(define deep-count-num
(lambda (lst)
(count-num (flatten lst))
)
)
The nice thing about this version of deep-count-num is that it is built
from simpler functions. However, it is probably not as efficient as earlier
version of deep-count-num.
Here’s an implementation of flatten:
(define flatten
(lambda (x)
(cond
((null? x)
x)
((not (list? x))
x)
((list? (car x))
(append (flatten (car x))
(flatten (cdr x))))
(else
(cons (car x)
(flatten (cdr x)))
)
)
)
)
append is an an important Scheme function. It takes 1 or more lists as
inputs, and returns a new list consisting of all its input lists combined in
order. For example:
1 ]=> (append '(1 2) '(3 4 5))
;Value 15: (1 2 3 4 5)
1 ]=> (append '(once) '(upon a) '(time))
;Value 16: (once upon a time)
Lambda Functions¶
A lambda function is essentially a function without a name. We’ve been using lambda functions to define named functions, so you should be somewhat familiar with them.
Here’s a lambda function that adds 1 to its input:
(lambda (n) (+ n 1))
This function takes one input which it names n, and returns the value of
n + 1. The function itself has no name! You can all it like this:
((lambda (n) (+ n 1)) 5)
This passes 5 to the lambda function, and so the entire expression evaluates to 6.
Lambda functions are often a convenient way to write small functions. For example, suppose we want to count how many times 2 or 5 occurs in a list. Then we could do it like this:
(count-fn (lambda (n) (or (= n 2) (= n 5)))
'(2 2 6 5 7 5 2 1)
)
Once you get the hang of them, using lambda functions in this way is often very convenient.
Here’s another example where lambda functions are useful. The keep-if
function returns a list containing all the elements of a given list that match
a given test function:
(define keep-if
(lambda (pred? lst)
(cond
((null? lst)
'())
((pred? (car lst))
(cons (car lst) (keep-if pred? (cdr lst))))
(else
(keep-if pred? (cdr lst)))
)
)
)
1 ]=> (keep-if even? '(1 2 3 4 5))
;Value 13: (2 4)
1 ]=> (keep-if (lambda (n) (or (= n 1) (even? n))) '(1 2 3 4 5))
;Value 14: (1 2 4)
Here’s an expression that partitions a list of numbers so that all the evens come before all the odds:
1 ]=> (append (keep-if even? '(1 2 3 4 5)) (keep-if odd? '(1 2 3 4 5)))
;Value 18: (2 4 1 3 5)
We can write this as a function:
(define parity-partition
(lambda (nums)
(append (keep-if even? nums) (keep-if odd? nums))
)
)
1 ]=> (parity-partition '(1 2 3 4 5))
;Value 21: (2 4 1 3 5)
Note that Scheme has a built-in function called filter that does the same
thing as keep-if.
Another useful function is called map: it applies a function to each
element of a list, returning the result as a new list. Scheme already has a
map function built in, but lets write our own version called my-map:
(define my-map
(lambda (f lst)
(cond
((null? lst)
'())
(else
(cons (f (car lst)) (my-map f (cdr lst))))
)
)
)
1 ]=> (my-map (lambda (n) (* n n)) '(1 2 3))
;Value 23: (1 4 9)
1 ]=> (my-map list '(1 2 3))
;Value 24: ((1) (2) (3))
Notice that the function, f, that is passed into my-map takes one
input. The idea is that f is applied to every element of the list, e.g.
(my-map f (a b c d)) returns ((f a) (f b) (f c) (f d)). Thus, it is
similar to a loop in other languages.
Folding a List¶
Consider the following function for summing a list of numbers:
(define sum-list
(lambda (nums)
(cond
((null? nums)
0)
(else
(+ (car nums) (sum-list (cdr nums))))
)
)
)
1 ]=> (sum-list '(1 4 2))
;Value: 7
Compare it to this function that calculates the product of a list of numbers:
(define prod-list
(lambda (nums)
(cond
((null? nums)
1)
(else
(* (car nums) (prod-list (cdr nums))))
)
)
)
1 ]=> (prod-list '(1 4 2))
;Value: 8
sum-list and prod-list are very similar. There are three main
differences. First, sum-list returns 0 for the empty list, while
prod-list returns 1. Second, in the recursive case, sum-list use +
and prod-list uses *. Finally, the names of the recursive calls are
different.
Now lets write a general-purpose function that implements this pattern, taking the base case value and function to be passed in as parameters:
(define my-fold
(lambda (f empty-val lst)
(cond
((null? lst)
empty-val)
(else
(f (car lst) (my-fold f empty-val (cdr lst))))
)
)
)
1 ]=> (my-fold + 0 '(1 2 4))
;Value: 7
1 ]=> (my-fold * 1 '(1 2 4))
;Value: 8
In Scheme, there are a number of built-in functions similar to my-fold,
such as reduce-left, reduce-right, fold-left, and fold-right.
Each of these functions implements a variation of the same essential pattern
as my-fold.
An interesting way to think about my-fold is to see what it does to a list
when it is expanded into nested calls to cons. For example, we can write
the list (1 4 2) in the form (cons 1 (cons 4 (cons 2 ()))). When you
call my-fold on it, it as if each cons is replaced by f, and the
empty list is replaced by empty-val. For example:
(my-fold + 0 '(1 4 2))
= (my-fold + 0 (cons 1 (cons 4 (cons 2 ()))))
= (+ 1 (+ 4 (+ 2 0))
= 7
And:
(my-fold * 1 '(1 4 2))
= (my-fold * 1 (cons 1 (cons 4 (cons 2 ()))))
= (* 1 (* 4 (* 2 1))
= 8
With this trick in mind, it is easy to see, for instance, that (my-fold cons
() lst) returns lst itself.
It is also worth noting that the order in which my-fold evaluates its list
is from right to left, i.e. the first things that get evaluated are the last
element of lst and empty-val. Thus, this version of my-fold is
sometimes called a right fold (sometimes abbreviated foldr).
For functions like + and * the order of evaluation doesn’t matter
much, but it might for other functions. So another way to fold a list is from
left to right (a left fold):
(define my-fold-left
(lambda (f z lst)
(cond
((null? lst)
z)
(else
(my-fold-left f (f z (car lst)) (cdr lst)))
)
)
)
Here’s a trace:
(my-fold-left + 0 '(1 4 2))
= (my-fold-left + (+ 0 1) '(4 2))
= (my-fold-left + (+ (+ 0 1) 4)) '(2))
= (my-fold-left + (+ (+ (+ 0 1) 4) 2) '())
= (+ (+ (+ 0 1) 4) 2)
= 7
An advantage of my-fold-left over my-fold (i.e. a right fold) is that
the final function call of my-fold-left is a recursive call to my-fold-
left itself. This is an instance of tail recursion, and it is important
because Scheme automatically converts such recursion to a loop, thus avoiding
the use of the call stack. In contrast, the last function called in my-
fold function is to f, and so it must use the stack because there is no
general-purpose way to replace its recursive calls with a loop that avoids
using a linear amount of memory. Thus my-fold can run out of memory on
large lists that my-fold-left can handle without a problem.