Homework 01
Install Racket
1) Download this install scipt:
wget http://download.racket-lang.org/installers/5.2/racket/racket-5.2-bin-i386-linux-ubuntu-karmic.sh
2) cd to the directory it's in and run it:
sudo sh racket-5.2-bin-i386-linux-ubuntu-karmic.sh
Accept all default settings.
3) Run DrRacket
/usr/racket/bin/drracket &
4) Select Language->Choose language..., select "Use the language declared in the source." Every module you create should begin with this line:
#lang racket
5) You might want to create a launcher for drracket, or a shell alias.
6) When you save a module, choose a file name with the suffix .rkt.
Warmup Exercises
We will do most of these in class; you don't have to turn them in.
The subset of the language in Lecture 1 is Turing complete, but it is not easy to see that yet.
But if we add cond (or if), it becomes clearer.
(define (myabs x)
(cond ((< x 0) (- x))
((= x 0) 0)
((> x 0) x)))
(myabs -3)
Many computations that would be expressed using iteration in an imperative paradigm are expressed using recursion in a functional paradigm:
(define (factorial n)
(cond ((< n 0) 'oops)
((= n 0) 1)
(else (* n (factorial (- n 1))))))
(factorial 6)
This has the apparent drawback of using stack space in proportion to n.
In some cases this drawback can be mitigated by writing a version of the procedure that is 'tail-recursive':
(define (tail-factorial n)
(define (iter product counter)
(cond ((> counter n) product)
(else (iter (* product counter)
(+ counter 1)))))
(iter 1 1))
(tail-factorial 6)
What is the defining characteristic of tail recursion?
What optimization does tail recursion admit?
What is the difference between a bound and unbound variable?
Write a procedure called fib that takes a parameter n and returns the nth element of the Fibonacci sequence that begins F0 = 0, F1 = 1.
Rewrite this procedure in tail recursive form. Hint: if you are not yet fluent in functional style, consider writing a draft in Python using local variables, then translate into Racket and replace the local variables with parameters.
List processing
If all of the elements of a list are available at once, you can assemble them into a list with an operator called (drum roll, please) list!
> (list 1 2 3)
(1 2 3)
The output format for lists is not a valid input format:
> (1 2 3)
. procedure application: expected procedure, given: 1; arguments were: 2 3
But if you quote it, all is well:
> '(1 2 3)
(1 2 3)
There are two operators that access elements of a list:
(first t) returns the first element of list t
(rest t) returns a list of all-but-the-first elements of t
Examples:
> (define t (list 1 2 3))
> (first t)
1
> (rest t)
(2 3)
Empty lists:
(list) creates an empty list
'() also an empty list
empty the most idiomatic way to create an empty list
(empty? t) returns #t if t is the empty list, #f otherwise
> '()
()
> (empty? '())
#t
> (empty? t)
#f
Write a procedure that takes a list of numbers and returns their sum:
Now write a tail-recursive version:
cons
If all of the elements of a list are available at the same time, you can use (list) to assemble them.
But often you want to assemble a list a little bit at a time.
cons takes two arguments and returns a pair, sometimes called a 2-tuple
> (cons 1 2)
(1 . 2)
Again, the output format is not a legal input format:
> (1 . 2)
application: bad syntax (illegal use of `.') in: (1 . 2)
Unless you quote it:
> '(1 . 2)
(1 . 2)
To access the elements of a pair, you can use (car) and (cdr) which are historically interesting, but not mnemonic. Let's define better names:
(define (left t) (car t))
(define (right t) (cdr t))
And here's how you use them.
(define pair (cons 1 2))
(left pair)
(right pair)
In general, you can build any data structure out of pairs.
Draw box and pointer diagrams for the following expressions:
(cons 1 2)
(cons (cons 1 2)
(cons 3 4))
(cons (cons 1
(cons 2 3))
4)
Notice the connection between the structure of the code and the structure of the data.
A list is a sequence of pairs where in each pair (first) is the cargo and (rest) is the rest of the list.
So every list is also a pair, but not every pair is a list.
Draw a box and pointer diagram for a list with the cargo 1 2 3 4.
Write an expression that builds this structure using cons.
(pair?) returns #t if the argument is a pair, #f otherwise.
(It is also written cons?, but I find that less readable.)
Write a procedure that takes a list as an argument and that builds a copy of the list (different list with the same cargo)
Does your procedure make a shallow or deep copy? Do we care?
What would a deep copy look like? What does it mean in this context?
map
Write a procedure called (square-list) that takes a list of integers and returns a list that contains the squares of the integers.
Write a more general procedure called (my-map) that takes a procedure as its first argument and applies it to each element of the list.
There is also an operator named map.
filter
(even?) returns #t if its argument is an even number, #f otherwise.
Write a procedure called (select-evens) that takes a list and returns a list that contains only the even elements.
Write a more general procedure called (my-filter) that takes a procedure as its first argument, applies the procedure to each element in the list, and returns a list of the elements that yield #t.
You will not be surprised to hear that there is an operator named (filter) that does the same thing.
Note: You can use (let) to eliminate common subexpressions.
reduce
Write a procedure called (product-list) that takes a list of integers and computes their product (using only binary multiplications).
How would you generalize this procedure? Hint: see (foldl).
Exercises
These are the ones you should turn in. Please put your answers in a file named hw01.rkt.
1) Write a procedure called (my-append) that takes two lists and returns a new list that contains all the elements from the first list followed by all the elements of the second.
2) Write a procedure called (my-reverse) that takes a list and returns a new list that contains the elements from the original list in reverse order. Hint: tail recurse!
3) Write a procedure called (deep-reverse) that takes a list and returns a new list that contains the elements from the original list in reverse order. If any of the elements are lists, they should also be reversed, and so on.
4) Write a procedure called (leaves) that takes a tree and returns list of the leaves (that is, all the elements that are not pairs).
Turnin
Please create a Dropbox folder named first.last.focs (filling in your first and last name) and share it with
downey@allendowney.com
sebastian@when.com
philip.loh@students.olin.edu
If you don't already have a Dropbox account, create one by following this link.
Please don't work in the shared folder (it causes a lot of unnecessary syncing). Work in another directory and then copy your solutions into the shared folder.