Due Date: Friday, Feb. 9, 2007, in class

Fun with Lists

This homework provides some practice in Scheme programming. You can download MIT Scheme from http://www.gnu.org/software/mit-scheme. The DrScheme environment, which you can search for in google, is another, possibly friendlier, scheme implementation. Either system can be installed on most operating systems (eg,. Linux, Unix, Windows). The MIT software is also installed in the Sloan 353 labs.

Turning in your work

All homework should be typed, not handwritten.

General rules

Unless directed otherwise, you should implement your functions using recursive definitions built up from the basic built-in functions such as CONS, CAR, CDR. You may use the built-in function equal? to test equality of lists.

Don't use set! and don't define anything except functions. Use let, let* freely.

Practice

For practice, but not to turn in, be sure to do the scheme calisthentics from the course resources page.

append

Define a function to append two lists

>  (append '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)
>  (append () '(4 5))
(4 5)
>  (append '(a b) ())
(a b)
>  (append '(1 (2 3)) '(4 5))
(1 (2 3) 4 5)

intersection

This function should return the intersection of two lists

>  (intersection '(1) '(1))    
(1)
>  (intersection '(1 2) '(1))  
(1)
>  (intersection '(2 1 2) '((1) 2)) 
(2)

Each value should appear in the output list only once.

zip

This function of two lists pairs up corresponding elements of the two lists. If one list is longer than the other, extra elements of the longer list are ignored.

>  (zip '(1 2 3) '(a b c))    
((1 a) (2 b) (3 c))
>  (zip '(1 2) '(a))  
((1 a))

filter

This higher-order function takes as its first argument one-argument function, called a predicate, which returns #t or #f, and as its second argument a list. It returns a list of all elements in the second argument that satisfy that predicate. The elements must appear in the result in the same order that they appear in the original list.

> (filter (lambda (x) (= x 1)) '(1 2))
(1) 
> (filter (lambda (x) (< x 3)) '(1 2))
(1 2)

foldl

In class we talked about a fold function that was right-associative. Implement the analogous function that is left-associative. That is (foldl - 0 '(1 2 3)) computes (((0-1)-2)-3) while the fold as we defined it in class computes (1-(2-(3-0))). As another example of the difference consider the difference between (foldl cons () '(1 2 3)) and (fold cons () '(1 2 3)).

Challenge Based on your observations about the behavior of foldl and foldr on these examples, now define append and reverse using foldl and foldr.

Hints on working with MIT Scheme

The following are a few tips to help you get started on working with Scheme on the Windows machines in the Sloan 353 lab.
                   

Finding scheme in Windows

Click Start, point to All Programs, point to MIT Scheme, and then click 'Scheme'.

Invoking scheme on a file

• In order to load files in scheme you have to use the procedure 'load'.
• The procedure load has the following syntax
  (load filename)
  Here filename can be a string specifying a single file or a list of strings specifying multiple files.
• For example in order to load a file named "example.scm" (.scm is the extension for scheme source files) you would type (load "example.scm") at the prompt.
• If the file is not located in the current working directory you should specify the full path-name for the file. For example in windows for loading a file present in the users directory in the C drive you would type (load "c:\\users\\example.scm") at the prompt.

What to do when an error occurs in Scheme

When you start Scheme a program called Read-Eval-Print Loop (REPL) starts executing. This program will print a prompt (typically 1 ]=> ) and will wait for input from the user. When the user types an expression REPL evaluates the expression, prints the result and displays another prompt waiting for the next input.
The '1' in the prompt is the REPL level number and is the topmost level of execution. Whenever an error occurs this level number is incremented (implying that a new version of REPL has been started). For example if you type 'hi' at the prompt you would see the following error messages.

;Unbound variable: hi
;To continue, call RESTART with an option number:
; (RESTART 3) => Specify a value to use instead of hi.
; (RESTART 2) => Define hi to a given value.
; (RESTART 1) => Return to read-eval-print level 1.

2 error>

As you can see the earlier prompt has been replaced by a new one '2 error>'. This implies that a new REPL has been started over the old one. Also note that the prompt string displays both the current level number and another string 'error' (implying that this REPL is the result of an error). The original REPL is still running in the background and is waiting for you to return to it. You can return to the original REPL by typing (restart 1). For each error in each REPL different restart methods are available. For example when we typed 'hi' at the prompt we had three restart methods available to us (as shown above), they are (restart 1), (restart 2), (restart 3). The (restart 1) method as explained above returns us to the REPL level 1.
If another error occurs while you are executing in the REPL level 2, the level number is incremented to 3 and another REPL (level 3) is started over the current one . This can theoretically go on forever.


• Control Key Combinations (Interrupt Keys)
  Scheme also has some control key combinations (interrupt keys) which will do the various restarts with a lot less retyping for you. These are C-g (Ctrl-g -> press and hold down control key and press the key 'g' on the keyboard), C-b, C-x and C-u. The C-g key will halt any running scheme evaluation and will return you to the top-level REPL (short for typing (restart 1) at the error prompt). You can also press the control key combination C-c (C-c displays all the interrupt choices) which prompts for another character (either C-g, C-x, C-b, C-u) and performs the corresponding action. Short definitions for some of the interrupt keys are listed below.
  • C-g (or C-c C-g)
    Abort the scheme evaluation and return to the top-level REPL.
  • C-x (or C-c C-x)
    Abort the current evaluation process and return to the "current" REPL (stays in the same REPL).
  • C-u (or C-c C-u)
    Abort the current evaluation process and go to the previous REPL. For example if the current REPL level is 4 pressing C-u will take you to level 3