Lab 2: Working with let and lists
This lab is due at 2359 on Wednesday, 6 September. It should be submitted to the course SI413 as Lab02, with the files named properly according to the lab instructions. See the submit page for details. You are highly encouraged to submit whatever you have done by the end of this lab time. Remember that you must thoroughly test your code; the tests that are visible before the deadline are only there to make sure you are using the right names and input/output formats.
1 Starter Code
2 Getting started
You should be using the same lab partners as the previous Scheme lab from last week.
Start (as always) by going to your git repo at si413/scheme
, and
run these commands to update from the starter code repo:
roche@ubuntu$
git pull starter main
roche@ubuntu$
git pull
(See git instructions here as a reminder, and don't ever hesitate to ask your instructor or a classmate for help dealing with git things. It should be a useful tool, not an annoying chore!)
You should see a new folder lab02
with a file lab02.scm
.
That is where you will do your work for this lab!
New this week: You should also see a file lab02.md
You need to fill this out using a text editor and submit along with your
code. Please follow the instructions on formatting and use the blank lines
between/after questions to put your responses.
There should also be a file submitme.sh
From the command line,
you should be able to just run this like ./submitme.sh
from the
lab folder, and it will submit all your files for the correct assignment
for the correct class. Neato!
3 Symbols
Recall that a symbol is just a quoted identifier, such as
'si413
, or 'wombats
.
We can use the function symbol?
to find out whether
something is a symbol, and eqv?
to compare two
symbols.
Exercises
For these exercises, use the following exchange rates:1 US dollar = 0.76 Euros (euro) 1 US dollar = 98.18 Japanese Yen (yen) 1 US Dollar = 1109.85 South Korean Won (won)
 Conversion to US dollars
Create a function(tousdollar amt cur)
that takes an amount of moneyamt
in some foreign currencycur
and returns that amount in US dollars. The parametercur
will be one of the symbols'euro
,'yen
,'won
, or'usd
.
So for instance(tousdollar 500 'yen)
produces \(500/98.18\), which comes out to \(5.0927\ldots\).  Conversion from US dollars
Create a function(fromusdollar amt cur)
that does the opposite: takes an amount in US Dollars and converts it to the named currency.
If you're clever, you can write a helper function for this problem and the previous one that will avoid your having to enter the conversion rates twice.  Any kind of conversion!
Create a function(convert amt fromCur toCur)
that takes an amount in currencyfromCur
and converts it to currencytoCur
. Use your functions from parts 1 and 2 and life will be easy!
4 Lists
Recall "big 4" of list processing:
'()
: the name for an empty list.(cons a L)
: Take an itema
and a listL
and return the new list witha
inserted in the front ofL
.(car L)
: Returns the first item inL
.(cdr L)
: Returns the list containing all the items inL
after the first item.
If you're faced with nested lists, you sometimes need cars of
cdrs, and cdrs of cars, and so forth. The shortcut for
a bunch of these in a row is cXXXr
, where
each X
is either a
or d
,
corresponding to car
and cdr
.
For example, calling
(caddr lst)
is exactly equivalent to calling
(car (cdr (cdr lst)))
.
There are two more extremely useful shortcuts:
list
: Takes an arbitrary number of items and makes a single list containing them.append
: Takes an arbitrary number of lists and makes a single list containing all their items.
Make sure you understand the difference between these two!
In class we looked at the general pattern for a recursive function
on a list. When that function is also producing a list, it extends
the pattern by (usually) returning '()
in the base case, and
(usually) returning a cons
in the general case. For example,
here is a simple recursive function that multiplies every number in a list
by 2:
; alon must be a list of numbers.
(define (mulby2 alon)
(if (null? alon)
'()
(cons (* 2 (car alon))
(mulby2 (cdr alon)))))
See what's happening? Make sure you can identify the base case condition, the base case return value, and the recursive call. Notice what gets multiplied by 2, and where it happens. If it's confusing, now is the time to ask your able and handsome instructor!
Exercises
 List of Squares
Write a functionsquares
that takes integers i and j and returns list of the squares \(i^2, (i+1)^2, \ldots, (j1)^2, j^2\).> (squares 2 12) (4 9 16 25 36 49 64 81 100 121 144)
 Length Comparison
In class we saw that there is a builtin Scheme function
length
which returns the length of a list. Using this, we could write a functionlonger?
to test whether the first list is longer than the second:; L1 and L2 must both be lists (define (longer? L1 L2) (> (length L1) (length L2)))
Now I want you to write your own version of
longer?
that doesn't use length calculation as a subroutine. Instead, you will have to recursively process bothL1
andL2
at the same time until one of them is empty.(I really mean it  no length, even if you write it yourself! I will test you code using an infinite list as one of the arguments. Yes, those exist in Scheme.)
 Count cash!
Write a function calledsumcash
that returns the value in US dollars of a collection of amounts of different currencies (same currencies as above). The amounts will be given in a list L, such that each element of L is itself a list, whose first element is an amount and whose second element is a currency name. So, for example,
as an argument to'((12.20 usd) (340 yen) (850 won))
sumcash
would mean adding 12.20 dollars, 340 yen and 850 won, and giving the total in dollars. Here's an example:> (sumcash '((12.20 usd) (340 yen) (850 won))) 16.4289...
 Topdown design in Scheme: standard deviation
Write a function calledstddev
that takes a list of numbers and returns their standard deviation. (Recall: the standard deviation of \(x_1, x_2, \ldots, x_n\) is \[\sqrt{\frac{(x_1\mu)^2 + (x_2\mu)^2 + \cdots + (x_n\mu)^2}{n1}},\] ... where \(\mu\) is the average of \(x_1,x_2,\ldots,x_n\).) When you write this function, use topdown design. In scheme this means writing thestddev
function using functions you wish were already defined, then going back and defining them later. It can be useful to quote these function calls before you implement them, so you can even do topdown testing!
Example:> (stddev '(34 18 25 23 29 11 28 24 27 29)) 6.460134157533676
 Uniquefication (OPTIONAL)
Write a functionuniquefy
that takes a list of numbers, and returns a list with all the distinct numbers in the original, i.e., with all the duplicate numbers removed. For example:
At the very least, you will probably want to also define at least one nice helper function. Try thinking about the efficiency of your function. Could you make it faster?> (uniquefy '(1 2 4 1 2 2 3 15)) (1 2 4 3 15)
5 Let
The let
construct in Scheme allows you to give a
name to a common subexpression. For example, consider the
expression
The natural way to code this in Scheme is probably
(/ (* 33 ( 501 33)) ( 1 (* 33 ( 501 33))))
But you could say "let a = 33 * (501  33), and return a / (1  a)".
That's what let
allows you to do:
(let ((a (* 33 ( 501 33))))
(/ a ( 1 a)))
Essentially, let
is the Scheme way of getting local
variable functionality. What you've got is the
let
keyword, followed by a list of
variablename/value pairs, followed by an expression
(presumably using the new names) that provides the value of
the whole let
expression. For example, the following code
produces 12
as a result:
(let ((a 2)
(b 4)
(c 6))
(+ a b c))
There is power in using
let
in functions. Suppose I want to define a function called
shiftedcube
, which computes (x + 1)^3 for a
value x.
(define (shiftedcube x)
(let ((a (+ x 1)))
(* a a a)))
Then running (shiftedcube 2)
produces the value 27
.
Exercises:
 Let for a common subexpression
Using what you just learned, write a function calledtestsin
that takes any numberx
and computes \[\frac{1}{(\sin x)^2 + 1} + \sqrt{(\sin x)^2 + 1}  \left((\sin x)^2 + 1\right)^2\]  Let for readability
Write a functiondist
that computes the absolute value of the difference (in inches) between two lengths (given in feet and inches). For example, to compute the distance between 3'7" and 2'11":
Write this function using a> (dist 3 7 2 11) 8
let
expression to create valuesL1
andL2
for the lengths in total number of inches for each of the input feetandinches values.
6 Functions as parameters to other functions
As you have perhaps noticed, you never actually tell scheme
what the type of a function parameter is. Thus, if I
define some function (f x y)
, there's nothing to stop me from
calling it like this: (f sqrt 4)
. In other words, there's
nothing to stop me from passing f a function as one of its
arguments. This is something very special about functional programming
languages: functions can be used like any other kind of data.
Take a moment to allow this to sink in.
Now check out this example. f
uses its first argument,
x
, as a function. So x
should be a function!
> (define (f x y)
(* y (x y)))
> (f sqrt 4)
8
What happened here? Well since
x
is sqrt
and y
is 4
,
the evaluation produces
(* 4 (sqrt 4))
which is 8. So f is the
"apply
function x to argument y and then multiply by y" function.
Passing functions
to functions like this is very powerful. This is part of what
we mean when we say that "functions are first class objects"
in a functional language.
Exercises:

Finite difference.
Given a function \(g(x)\), the finite difference of \(g(x)\) at \(x=n\) is \(g(n + 1)  g(n)\). Define a function(fdat g n)
that takes a functiong
and a valuen
and returns the finite difference of g at n. For example:> (define (f x) (* x x)) > (fdat f 3) 7
7 Functions and lists: map and apply
map
is a really useful function that takes functions as arguments.
The expression
(map f L)
applies the function f
to each element of the list L
and puts the results together in a new list. For example:
> (map abs '(4 12 3 8 11 0))
(4 12 3 8 11 0)
If you have a function with k arguments, then you give map
k
lists, and it will take the first argument from list1, the
second from list2, etc.
> (map * '(2 3 4) '(6 5 4))
(12 15 16)
Another useful function of this type is apply
.
The expression (apply f L)
calls the function f
with arguments the elements of
L
. Here
are some examples:
> (apply max '(4 6 2)) ; same as (max 4 6 2)
6
> (apply  '(3 7)) ; same as ( 3 7)
4
Combining map
and apply
can be very interesting.
> (define (sqr x) (* x x))
> (map sqr '(1 2 3 4 5 6 7 8 9 10))
(1 4 9 16 25 36 49 64 81 100)
> (apply + (map sqr '(1 2 3 4 5 6 7 8 9 10)))
385
Yet another useful functionthattakesafunction is filter
.
The expression (filter f? L)
applies the predicate function
f?
to each element in the list L
, and returns the
list containing only the elements for which the predicate returns true.
For example:
> (filter number? '(a b 2 #t + 4))
(2 4)
Exercises
For these, you will probably want to use this helper function. Just copy its definition into your code.
; Returns a list containing integers a, a+1, ..., b.
(define (range a b)
(if (> a b)
'()
(cons a (range (+ a 1) b))))
 Product of square roots
Create a functionsqrtprod
that takes a numbern
and computes the product of the square roots of the integers from 1 up to n. For example:> (sqrtprod 10) 1904.94...
 Find the special numbers
Define a functionspecialnums
that takes an integern
and computes a list of all integers between 1 and n that are both divisible by 3 and are perfect squares. For example:
Hint: you should make some helper functions that are predicates.> (specialnums 100) (9 36 81)
 Polygonal transformation (OPTIONAL)
Make the following definition for P1:
P1 represents a polygon whose vertex coordinates are given by the pairs in P1. Write a function(define P1 '((3 5) (9 2) (11 6) (8 8) (4 6)))
(translate p d)
that takes a polygon (in the sense of P1, i.e., a list of coordinate pairs) and an offset d (represented by a pair, the x offset and the y offset) and translates the given polygon by the given offset.
Depending on your approach, the following function might be useful to you:> (define P1 '((3 5) (9 2) (11 6) (8 8) (4 6))) > (translate P1 '(1 2)) ((4 7) (10 4) (12 8) (9 10) (5 8))
For full credit, your function should also work in higher dimensions. By this I mean, if each point has x, y, and z coordinates, for example, everything should still work, by providing a list of 3 offsets to the;Creates a list of k copies of x (define (repeat x k) (if (= k 0) '() (cons x (repeat x ( k 1)))))
translate
function.