Exam 2 Review

Design Recipe

1. What are the components of data design?
2. What are the components of function design?

Recursion

1. What is structural recursion?
2. What is accumlative recursion?

Lists

1. What is the data definition for lists? Follow the DR.
2. For each of the following tasks, which is the most appropriate list abstraction?
   1. Multiply each element of a list of numbers by $n$.
   2. Determine if a list of strings contains an empty string.
   3. Determine if a list of lists contains only non-empty lists.
   4. Remove every empty string from a list of strings.
   5. Compute the concatenation of all elements in a list of lists.

Trees

1. What is the data definition for a binary tree? Follow the DR.
2. What is the traversal template for a binary tree? Include the two popular traversal strategies.
3. Remember that the order in which you visit child nodes during a traversal may be important.

Practie Problem: Zippers

A zipper is a representation of a list that makes it easier to navigate and update a list.¹

Note: Unlike the practice exam from class, this problem is not intended to be representative of an actual exam question. Indeed, it is much longer and more difficult. Instead, the goal is simply to offer additional practice.

(define-struct zip [left right])
;; A [Zip-of X] is a (make-zip [List-of X] [List-of X])
;; A (make-zip l r) represents the list (append (reverse l) r)
;; The cursor (or focus) is between the first element of l and the first element of r,
;; if they exist.

;; Represents (list * 1 2 3) where * indicates the position of the cursor
(define EZIP1 (make-zip empty (list 1 2 3)))
;; Represents (list 1 * 2 3) where * indicates the position of the cursor
(define EZIP2 (make-zip (list 1) (list 2 3)))

For the following problems, be sure to follow the DR where appropriate.

1. Examples.
   1. Define empty/zip to be the zipper representing the empty list.
   2. Unlike lists, it is possible to represent the same sequence with different zippers. Define at least one more zipper representing the same sequence as EZIP1 and EZIP2.
2. Predicates.
   1. Define a predicate empty/zip? that determines if a zipper represents to the empty sequence.
   2. Define the predicates leftmost? and rightmost? that determine if the cursor of a zipper is all the way to the left or right, respectively.
3. Conversions.
   1. Define a function list->zip that converts a list to a zipper representing the same sequence with the cursor all the way to the left.
   2. Define a function zip->list that converts a zipper to a list representing the same sequence regardless of where the cursor is.
4. Navigation.
   1. Define the functions left and right that move the cursor one position to the left or right, respectively. Your function may error whenever there is no such position.
   2. Define the functions cursor/left and cursor/right that produce the element to the left and right of the cursor, respectively. Your function may error whenever there is no such element.
5. Updates.
   1. Define the functions insert/left and insert/right that takes a zipper and an element and inserts it to the left and right of the cursor, respectively.
   2. Define the functions backspace and delete that takes a zipper and removes the element to the left and right of the cursor, respectively. Your function may error whenever there is no such element.
6. Abstractions. Implement foldr/zip without using list abstractions. Then implement it again using list abstractions.

Practice Problem: Arithmetic Expressions

In this problem you will define operations over a small programming language: the language of basic arithmetic expressions.

Note: Unlike the practice exam from class, this problem is not intended to be representative of an actual exam question. Indeed, it is much longer and more difficult. Instead, the goal is simply to offer additional practice.

;; An Op is one of
;; - "+"
;; - "-"
;; - "*"
;; - "/"

(define-struct const [val])
(define-struct expr [op left right])

;; An Expr is one of:
;; (make-const Number)
;; (make-expr Op Expr Expr)
;; Represents an arithmetic expression

(define EEXPR0 (make-const 0))
(define EEXPR1 (make-expr '+ (make-const 1) (make-expr '- (make-const 3) (make-const 2))))

Be sure to follow the DR for the following problems.

1. Define a function eval that evaluates an arithmetic expression a number (with each operator mapped to its usual meaning).
2. Not all expressions actually can be evaluated. Define a predicate div0? that determines if an arithmetic expression ever divides by 0.
3. Challenge Problem. Define a function show-work that produces a list including all intermediate expressions computed during evaluation. Your function may include duplicate expressions. For example, when evaluating (- (* 3 (+ 1 2)) (/ 25 5)), your function might output a list with the following entries (depending on your traversal order):

   (- (* 3 (+ 1 2)) (/ 25 5))
   (- (* 3 3) (/ 25 5))
   (- 9 (/ 25 5))
   (- 9 5)
   4