Lab 4 Recursion, With A Twist

Purpose: The purpose of this lab is to get some more practice with recursive functions, specifically with recursion over natural numbers.

Notation improvement!

We know that it’s tedious to write (cons 1 (cons 2 (cons 3 (....... '())))) all the time, to write down lists of more than a few elements.

In this lab, we introduce a shorthand notation: BSL provides the function list, which allows you to write the following instead: (list 1 2 3 ...). Three key things about this:

• First, this means exactly the same thing as (cons 1 (cons 2 (cons 3 ...... '()))). In fact, try writing it in DrRacket:

  > (list 1 2 3 4)

  (cons 1 (cons 2 (cons 3 (cons 4 '()))))

  In the output below, we’ll just start using this list-shorthand.

• Second, notice that you only write the elements of the list; you skip writing the conses. You also skip writing down the trailing '(). That means that writing (list 1 2 '()) is not a list of numbers: it actually means (cons 1 (cons 2 (cons '() '()))) — notice the extra '() stuck in there as the third item.

• Finally, note that even if you get to use list, you still tear the list apart using the list template, first and rest.

Processing two lists

; An LoS (List of String) is one of:

; - empty

; - (cons String LoS)

(define LOS-SHORT (list "cat" "dog" "art"))

(define LOS-LONG (list "cataract" "artist"))

; los-temp : LoS -> ?

(define (los-temp los)

(cond [(empty? los) ...]

[else (... (first los) (los-temp (rest los)))]))

Sample Problem Design a function no-prefixes that takes in two lists of strings, l1 and l2, and returns all of the strings in l1 that are not prefixes of a string in l2.

Think:

• Which list are you processing "first", and so which list should you decompose in the template?

• If you need to decompose the "other" list also, then you'll need a helper function that processes the other list. What should its purpose be?

• If you ultimately need to compare two strings against each other to check for prefixes, you'll need another helper function. What should its signature and purpose be?

; no-prefixes : LoS LoS -> LoS

; Return all strings in l1 that are not prefixes of any string in l2

(define (no-prefixes l1 l2)

(cond [(empty? l1) '()]

[else (if (no-prefixes? (first l1) l2)

(cons (first l1) (no-prefixes (rest l1) l2))

(no-prefixes (rest l1) l2))]))

(check-expect (no-prefixes '() '()) '())

(check-expect (no-prefixes '() LOS-SHORT) '())

(check-expect (no-prefixes LOS-SHORT '()) LOS-SHORT)

(check-expect (no-prefixes LOS-SHORT LOS-LONG) (list "dog"))

; no-prefixes? : String LoS -> Boolean

; Is this string not a prefix of any string in LoS?

(define (no-prefixes? s los)

(or (empty? los)

(and (not (prefix? s (first los)))

(no-prefixes? s (rest los)))))

(check-expect (no-prefixes? "cat" '()) #t)

(check-expect (no-prefixes? "cat" LOS-LONG) #f)

(check-expect (no-prefixes? "dog" LOS-LONG) #t)

; prefix? : String String -> Boolean

; Is s1 a prefix of s2?

(define (prefix? s1 s2)

(and (>= (string-length s2) (string-length s1))

(string=? s1 (substring s2 0 (string-length s1)))))

(check-expect (prefix? "dog" "dog") #t)

(check-expect (prefix? "dog" "dogs") #t)

(check-expect (prefix? "dog" "") #f)

(check-expect (prefix? "dog" "cats") #f)

Recursion over natural numbers

A recursive data structure we use very often in programming is the collection of natural numbers:

; A Nat, or natural number, is one of:

;  - 0

;  - (add1 Nat)

;

; The predicate for 0 is: zero?

;

; The predicate for (add1 n): positive?

; The selector for (add1 n): sub1

Exercise 1 What is the template for Nat?

Exercise 2 Think about the relationship between the following functions and constants:

empty – 0

empty? – zero?

cons? – positive?

cons – add1

rest – sub1

first – ???

Does anything relate to the list function first? If so, what? If not, why not?

In the following exercises we will redefine some built-in arithmetic functions to get practice writing recursive functions over Nats, so don’t simply reuse the built-in functions.

Exercise 3 Design a function nat-even? that returns true if the given Nat is even. Use only sub1, zero?, nat-even? itself, and not. Do not use even?, odd?, modulo, etc. Also, calling sub1 twice in a row does not follow the template and is therefore wrong.

Exercise 4 Design a function double that doubles the given Nat. Again, you may only use add1 and sub1, and of course double.

Exercise 5 Design a function down-from that takes a Nat n and returns the list of Nats counting down from n. For example,

> (down-from 3)

(list 3 2 1 0)

Exercise 7 Design a function nat+ that takes two Nats and computes their sum. Use recursion instead of the built-in + function.

Exercise 8 Design a function nat* that takes two Nats and computes their product. Again, use recursion instead of the built-in * function, though consider making use of nat+.

Exercise 9 Design a function nat-factorial that takes a Nat and computes the factorial of that number. The factorial of a natural number n is given by the product of all natural numbers less than or equal to n (excluding zero). Use your nat* function.

Exercise 10 Challenge: Design a function nat-square that squares the given Nat, but don’t use nat*! You may use add1, sub1, double, nat+, and of course nat-square.

A World in Lists (75 minutes)

The goal is to design an interactive program that illustrates how a turtle moves when given a series of commands. That is, the program consumes a list of commands, sets up the turtle facing right in the center of the canvas, and then executes one of these commands per clock tick. Its return value is the last position of the turtle.

Clearly, commands and series of commands are the two key classes of data. Intuitively, we wish to use lists such as (list "turn-left" "move" "turn-right" "move") to represent a series of commands. Otherwise the world-program design is relatively straightforward, following the design recipe for interactive programs.

We have provided you with some constants, some data definitions, a main function, and a wishlist of functions to get you started. Please download the file and open it in DrRacket.

Exercise 11 Develop a template for each data definition given to you in the file.

Exercise 12 Design the function do-command in the wishlist. Look at the template for a World. Recall that when a template calls another template it is an indication that you need a helper function.

Exercise 13 Design the function draw-turtle in the wishlist.

Exercise 14 Design the function out-of-commands? in the wishlist.

You can now call your main function on the result of random-command-list to see a turtle follow a series of random commands!

Before You Go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.