a. Make sure you have some blank pieces of paper (lined is okay) and something with which to write.
b. Make sure that your
csc151 package is up to date.
c. Open DrRacket and add the following procedure.
;;; Procedure: ;;; tree->code ;;; Parameters: ;;; tree, a tree (or tree-like structure) ;;; Purpose: ;;; Build a list that resembles the code to construct the tree. ;;; Produces: ;;; code, a list ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; If you evaluate code, you get tree ;;; Practica: ;;; > (tree->code (cons 'a 'b)) ;;; '(cons a b) ;;; > (tree->code '(a . b)) ;;; '(cons a b) ;;; > (tree->code '((a . b) c . d)) ;;; '(cons (cons a b) (cons c d)) ;;; > (tree->code (list 'a 'b 'c 'd)) ;;; '(cons a (cons b (cons c (cons d null)))) (define tree->code (lambda (tree) (cond [(null? tree) 'null] [(pair? tree) (list 'cons (tree->code (car tree)) (tree->code (cdr tree)))] [else tree])))
d. If you have not already, add an appropriate citation for the procedure.
Draw box-and-pointer diagrams for each of the following lists:
'((x) y z)
'(x (y z))
'((a) b (c ()))
If you’re not sure about how any of these are built with
(tree->code VALUE), e.g.,
(tree->code '((x) y z)).
Be prepared to share your pictures with me.
Enter each of the following expressions into Scheme. In each case, explain why Scheme does or does not use the dot notation when displaying the value.
(cons 'a "Walker")
(cons 'a null)
(cons 'a "null")
(cons 'a "()")
(cons null 'a)
(cons null (cons null null))
Draw a box-and-pointer representation of the value of the last two expressions in the previous exercise.
What do you think that
pair? will return for each of the following? How
list?. Attempt to confirm each answer experimentally and explain
any that you found particularly tricky.
(cons 'a 'b)
(cons 'a (cons 'b 'c))
(cons 'a null)
(list 'a 'b 'c)
You may recall that we told you that many kinds of data are defined recursively. For example, a list is either (1) null or (2) cons of anything and a list.
Using that recursive definition of lists, write a procedure,
(listp? val), that determines whether or not
val is a list.
You may not use
list? in your definition of
If you were able to complete the primary exercises with time to spare, you might want to consider the following problems:
listp? without using
Write a procedure,
(last pairthing) that finds the “last” value in
a list-like pairs structure. If the pair structure is actually a list,
return the last element of the list. Otherwise, follow the cdrs until
you find the last pair, and return the cdr of that pair.
In solving this problem you should only step through the structure once.
a Write a procedure,
(intlist->string ints) that takes as input a
list of integers and returns a string that represents the list.
> (intlist->string null) "()" > (intlist->string '(1)) "(1)" > (intlist->string '(1 2 3)) "(1 2 3)" > (intlist->string (cons 1 2)) BOOM!
b. Extend your procedure to print a period and the cdr when the cdr is not null.
> (intlist->string null) "()" > (intlist->string (cons 1 2)) "(1 . 2)" > (intlist->string (cons 1 (cons 2 3))) "(1 2 . 3)"
c. Extend your procedure to handle nested pair structure.
> (intpairs->string null) "()" > (intpairs->string (list (list 1))) "((1))" > (intpairs->string (list 1 (list 2 3) 4)) "(1 (2 3) 4)" > (intpairs->string (list 1 (cons 2 3) 4)) "(1 (2 . 3) 4)"