Local Procedures and Recursion

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: The Last Element
  • Exercise 2: Alternating Lists
  • Exercise 3: Iota, Revisited
  • Exercise 4: Taking Some Elements
  • Exercise 5: Intersection
• For Those with Extra Time
• Notes

Exercises

Exercise 0: Preparation

a. Review the corresponding notes on letrec and named let.

b. Start DrScheme.

Exercise 1: The Last Element

a. Define a recursive procedure, last-of-list, a recursive procedure that returns the last element of a list.

b. Using that procedure, compute the sum of the last elements of the lists (3 8 2), (7), and (8 5 9 8).

Note that you will probably need to make three calls to last-of-list.

c. Rewrite your solutions to the previous two problems using a letrec-expression in which

• the identifier last-of-list is locally bound to a recursive procedure that finds and returns the last element of a given list, and
• the body of the expression computes the sum of the last elements of the lists (3 8 2), (7), and (8 5 9 8).

The body of your expression should invoke last-of-list three times.

Note that you are to write an expression and not a procedure (other than the local last-of-list) for part c of this exercise.

Exercise 2: Alternating Lists

A non-empty list is an s-n-alternator if its elements are alternately symbols and numbers, beginning with a symbol. It is an n-s-alternator if its elements are alternately numbers and symbols, beginning with a number.

Write a letrec expression in which

• the identifiers s-n-alternator? and n-s-alternator? are bound to mutually recursive predicates, each of which determines whether a given non-empty list has the indicated characteristic, and
• the body invokes each of these predicates to determine whether the list (2 a 3 b 4 c 5) fits either description.

Your letrec expression should have the form

(letrec
  ((s-n-alternator? ...)
   (n-s-alternator? ...))
  ...)

Note: By mutually recursive, we mean two procedures that call each other.

Exercise 3: Iota, Revisited

As you may recall, Iota takes a natural number as argument and returns a list of all the lesser natural numbers in ascending order.

a. Define and test a version of the iota procedure that uses letrec to pack an appropriate kernel inside a husk that performs precondition testing. This version of iota should look something like

(define iota
  (lambda (num)
    (letrec ((kernel ...))
       ...)))

b. Define and test a version of the iota procedure that uses a named let. This version of iota should look something like

(define iota
  (lambda (num)
    ...
    (let kernel (...) 
      ...)))

Exercise 4: Taking Some Elements

Define and test a procedure, (take lst len), returns a list consisting of the first len elements of the list, lst, in their original order.

The procedure should signal an error if lst is not a list, if len is not an exact integer, if len is negative, or if len is greater than the length of lst.

Exercise 5: Intersection

a. Define and test a procedure (intersection left right) that takes two lists of symbols as arguments and returns a list of which the elements are precisely those symbols that are elements of both left and right.

b. What does your procedure do if a symbol appears in both lists and appears more than once in one or both of the lists?

For Those with Extra Time

• Rewrite take and intersect to use whichever of named let and letrec you didn't use the first time.
• Reflect on which of the two strategies you'd prefer and why (and when).

Notes

No notes yet.