Approximate overview
Design and write recursive functions over lists.
Write a recursive procedure, (increasing-length? words), that takes
a list of strings as input and ensures that every string is at least as
long as the previous string. If so, it returns true. If not, it returns
false.
Here’s a partial test suite.
(check-equal? (increasing-length '())
#t
"No strings: They are in increasing length")
(check-equal? (increasing-length? '("hello"))
#t
"A singleton")
(check-equal? (increasing-length? '("a" "b" "cd" "efg" "hij" "klmn"))
#t
"Some duplicate-length words")
(check-equal? (increasing-length? '("a" "bb" "ccc" "dddd" "eee"))
#f
"Okay until the end.")
You’ve learned how a few primary procedures are written.
list-append (which is normally called append), which joins
two lists together.list-remove.reverse.An important moral: The computer spends a decent amount of work on
each of these. list-append, for example, has to step through
every element of the first list.
At times, DrRacket saves in what it calls “binary format”. Human beings cannot read binary format. Gradescope isn’t good at reading it either. If you get an error about binary format, please use
File -> Save Other -> Save Definitions As Text…
Copy/paste/change is often the best way to do a full trace.
(define fun
(lambda (x xs)
(if (null? xs)
(list x)
(cons (car xs) (fun x (cdr xs))))))
I’m putting the body on one line to make it easier.
(define fun
(lambda (x xs)
(if (null? xs) (list x) (cons (car xs) (fun x (cdr xs))))))
(fun 'a '(c d b))
-->
If you feel like you’ve understood tracing well enough, it’s okay to skip steps (but not on the SoLA).
Note that cons only builds a list when both parameters are complete.
You’ll often end up with something like the following in your trace.
--> (cons 'a (cons 'b (func ...)))
We need to keep the “delayed cons” until we reach the base case, just as we had the “delayed add” in sum.
What does the self check have to do with recursion?
To write recursive procedures, we need to identify the base case.
Was the reading as simple as it seemed?
I don’t know. If you can embrace “If the recursive call works …”, recursion will be straightforward. But enough people had trouble with the “simple enough for a CS prof” base cases that I guess that it’s not so simple.
How do we write drop?
The answer is forthcoming.
How do we write tally-value (e and f on self-check 2)
There’s something similar in the sample code on the lab. We’ll also do something similar in exercise 4.
Many of you didn’t make things simple enough. The base case is supposed to be the simplest possible input.
a. Suppose you want to count how many elements are in a list. What’s a list that’s so simple that even a cs prof can figure out how many elements are in the list?
A one element list, such as
'(a).
The empty list,
'()
b. And how many elements are in that list?
For the empty list, Sam can say “zero”
c. Suppose you want to find the last element of a list. What’s a list that’s so simple that even a cs prof can figure out the last element?
The empty list
'()
A list with one element.
d. How do they get that last element?
Whoops, there is no last element in an empty list.
(car lst)
e. Suppose we want to count how many times a value, val, appears in a list. What’s a list that’s so simple that even a CS prof can count the number of appearances of val?
'()
f. And how many times does val appear in the list?
Zero
g. Suppose we want to take the drop the first n elements of a list. What’s a value of n that’s so simple that even a cs prof can figure out how to drop n elements?
Zero
One
h. And how do they drop those n elements?
Zero: Don’t change the list at all
One:
(cdr lst)
Can I has extra stickers?
Sure.
I forgot to do Quiz 5. Can I make it up on the SoLA?
Certainly.
my-length and my-product.(*) is 1, so (product '()) should be 1.largest-in-list
or longest-string-in-list. (There’s a bit of decomposition there.)