Activity: Scheme Recursion Practice

We want to write a function get-last that returns the last item in a list, or an empty list if given an empty list as input. Here are some example inputs and expected outputs:

(get-last '(13)) ;; Returns 13
(get-last '(1 4 6)) ;; Returns 6
(get-last '((1 2) 7)) ;; Returns 7 (the two items are (1 2) and 7).

Here's the beginning of the implementation, with ??? at spots in the code I haven't completed:

(define get-last
  (lambda (lst)
    (if (null? ???)
        '()
        (if (null? ???)
            ???
            (get-last ???)))))

Copy and paste this skeleton into main.scm, and then modify each ??? so that the code will work correctly.

(Hint: Walk yourself through each part of the code, talking about it out loud with your partner. For instance, to fill in the first ??? I might say "Okay, if ??? is null, then this will return an empty list. When what thing is null do we want to return an empty list?")

To test your code, you can try it with the examples in Scheme, and feel free to make up your own too! For most homeworks, you'll also have automated tests; this won't necessarily be true for most activities, but this activity does have some automated tests to show you how to run them. To run the tests for this function, type the following at the command line (not in Guile!):

./test-get-last

The tests in tests-get-last.scm will be run on your code, and you'll see how many passed and how many failed. I encourage you to try testing on your own first, and then if you think everything is working, try running my tests. (To run your code yourself, you can copy the function from main.scm into Guile, or alternatively, type (load "main.scm") in Guile to load the code in main.scm.)

Write a function list-length that computes the length of a list. Here are some example inputs and expected outputs:

(list-length '(13)) ;; Returns 1
(list-length '(1 4 6)) ;; Returns 3
(list-length '((1 2) 7)) ;; Returns 2 (the two items are (1 2) and 7).

You can assume that the input is a list, not a number or other structure. Do not use the built-in function length.

As above, first test the function yourself, and then try running my tests:

./test-length

Write a function nth that gets the nth item in a list. We'll assume that the first item is the 1st item. Here are some example inputs and expected outputs:

(nth 1 '(3 5 7)) ;; Returns 3
(nth 2 '(3 5 7)) ;; Returns 5
(nth 1 '((1 2) 7)) ;; Returns (1 2)

You can assume that the input is a list, not a number or other structure. If the index to look for is longer than the length of the list or less than 1, return an empty list.

As above, first test the function yourself, and then try running my tests:

./test-nth

You might wonder whether if can be implemented in Scheme like normal procedures, or if something special is needed to evaluate if. The starter code contains a function example-fn. Try calling example-fn with an unbound variable, e.g.: (example-fn WOW). What happens?

Now, try writing an if statement involving an unbound variable in either the consequent or alternative, and make sure that the test in the if statement will not lead to the expression with the unbound variable. Here's an example of what I mean:

(if #t
    3
    WOW)

Try running the if-statement. What happens?

Based on what you've seen here, discuss with your partner (or brainstorm on your own) about whether the following attempt at re-defining if would produce something that is equivalent to the original if:

(define new-if
  (lambda (predicate consequent alternative)
          (cond (predicate consequent)
                (else alternative))))

In a comment at the end of main.scm, indicate whether this is equivalent and briefly justify your answer. Consider what this means for when you write an interpreter for Scheme: will you be able to treat if like any other procedure, or will it need to be handled as a special case? Special forms are particular keywords or constructs that need to be handled differently.