University of Guadalajara Raquet Programming Project

Homework 4Include display statements and function calls as necessary to completely demonstrate that your code works for each of the following problems. Email your racket file to me when done (normally a .rkt extension). Note that you will need to paste in the accumulate function from page 31 of the notes.
Problem 1
Implement the following list manipulation procedures. You may find some of them useful in later exercises.
Note that for accumulate, the two parameters in the lamdba represent the first item of the list, and the result of accumulate applied to the rest of the list. So, something like (lambda (x y)… might instead be better named as something like (lambda (first-of-lst result-of-rest)…
The procedure (contains? list object) takes as arguments a list and an object, and returns #t iff list contains object. Implement two versions of contains?: one recursive with a conditional, and one without a conditional and without (explicit) recursion that uses accumulate and map. (The recursion here is hidden in the implementation of map and accumulate). Hint: The call to map should build a list of boolean values. Use or in the lambda of the accumulate.
Hint:
(define (contains? list object)
(accumulate (lambda (x y) …)
…
(map (lambda (x) …) …)))
Example:
(contains? (list 1 2 3 4) 3) ;Value: #t
The procedure (remove object list) returns the list with all occurences of the object removed. Implement two versions: one recursive, and one without recursion using accumulate. In the former, the returned list should have the same structure as the original one with just the object removed. In this version, cons will be used to keep an item in the list (with remove called recursively on the rest of the list), otherwise to remove an item, remove will be called recursively on the rest of the list.
Accumulate hint 1:
(define (remove object list)
(accumulate (lambda (item rest) …) … …)
Accumulate hint 2 (this code is very close but doesn’t remove anything… just reforms the list. The lambda will require a cond):
(define (remove object list)
(accumulate (lambda (item rest)
(cons item rest))
null
list))
Example:
(remove 2 (list 1 2 3 2 1)) ;Value: (1 3 1)
(let ((lst (list 1 2 3)))
(and (equal? (list 1 3) (remove 2 lst))
(equal? lst (remove 4 lst))))
;Value: #t
Problem 2
Assume that an arithmetic expression is either a primitive expression – a number – or a compound expression – a list containing an operator and any number of arithmetic expressions, in the prefix notation, just as in Scheme. Furthermore, let us use only the four operators +, -, *, and /.
Your task is to implement an interpreter for this arithmetic. In the following, object can be any Scheme object (possibly not an arithmetic expression), while expr is expected to be an arithmetic expression.
Implement the following procedures. Do not use the built in eval function because that is what your evaluate should do.
The predicate (operator? object) returns #t if object is any of +, -, *, and /. Hint: look at the member function.
The procedure (null-val operator) returns the null value corresponding to an operator (i.e., 0 for + and -, 1 for * and /). You might use the assoc function to implement this.
The predicate (expression? expr) returns #t iff expr is a valid arithmetic expression (see note above detailing what makes a valid expression). Use the (built-in) predicate list? to test if expr is a list, the (built-in) length to find out the length of a list, and operator? and the (built-in) predicate number? to test operators and operands. The andmap function will help with this…by allowing you to appl the expression? function to each of the operands and anding together the result.
The procedure (count-operators expr) returns the total count of operators in the expression (including those in nested compound expressions, if any). Similarly, (count-primitive-operands expr) returns the total count of primitive operands (i.e., numbers) in the expression.
The procedure (evaluate expr) returns the arithmetic value of the expression (the result of actually applying the operators to the operands). If you have an operator named op, you can apply that to operands by using it’s name followed by the operands (evaluated recursively). Alternatively, and more conveniently, you should be able to evaluate the operands by applying the function map to evaluate and the operand list, and then you can use the apply function to apply an operator to a list of evaluated operands.
Examples:
;; 1 + (2 / (3 * 5 + 1)) + (-4)
(define expr
(list +
1
(list /
2
(list +
(list * 3 5)
1))
(list – 0 4)))
expr
;Value: (+ 1 (/ 2 (+ (* 3 5) 1)) (- 0 4))
(operator? (car expr))
;Value: #t
(number? (cadr expr))
;Value: #t
(expression? expr)
;Value: #t
(expression? (list 1 + 2))
;Value: #f
(expression? (list + 1))
;Value: #f
(count-operators expr)
;Value: 5
(count-primitive-operands expr)
;Value: 7
(evaluate expr)
;Value: -23/8
Functional Programming
with Scheme
Data Abstraction (1)
Data
In FP, the data versus procedure distinction is blurred
– data can be implemented by using procedures
– procedures are represented as data
We can’t just define data as static objects or non‐procedural
objects, or “sectors of memory that can be read from and
written to…”
Both data and procedures are represented as lists (pairs)
slide 2
Data Abstraction
Compound (complex) data (data objects)
– increases modularity of programs
– enhances expressive power of the implementation language
Data abstraction
– separates details of how a data structure is represented
(implementation), and
– what a data structure represents – how it can be used (interface)
– programs that use abstract data do not have to know the
implementation details
– programs that implement abstract data do not have to know how
the data will be used
slide 3
Abstract Data
Defined in terms of an interface
–
–
–
constructors – create an object of a particular data type
selectors – retrieve a part of an object
predicates – test if an object is of a particular data type
(define (make-point x y)
(make‐a‐pair x y))
(define (point-x point)
(get‐the‐first‐element point))
(define (point-y point)
(get‐the‐second‐element point))
(define (point? object)
(is‐a‐pair? object)
slide 4
Pairs
Pair is the fundamental data structure in LISP
– lists are chained sequences of pairs
– pair constructor: cons
– pair selectors: car, cdr
– pair condition: pair?
(define my-pair (cons 0 1))
(pair? my-pair)
(car my-pair)
(cdr my-pair)
slide 5
Pairs (contd)
The printed representation of a pair is a dotted pair*
my-pair
;Value: (0 . 1)
The null object for the pair data structure, and its predicate
– identical to the truth value for false (#f)
() or nil**
null?
* This is only the printed representation of a pair, which is not the pair itself.
** Use (define nil ())
slide 6
Operations on Abstract Data
Defined in terms of an interface – what can be done with the
data structure
(define (add-point p1 p2)
(make-point (+ (point-x
(point-x
(+ (point-y
(point-y
(define (sub-point p1 p2)
…)
p1)
p2))
p1)
p2))))
…
slide 7
Abstraction Barriers
Abstraction barriers separate the user of a data type from its
implementation
programs that use points (graphics?)
WHAT
add-point sub-point …
HOW
abstraction
barrier
implementation of operations on points
WHAT
make-point point-x point-y
HOW
abstraction
barrier
implementation of points as an ADT
WHAT
cons car cdr
abstraction
barrier
HOW
implementation of pairs (actual implementation of Scheme)
slide 8
Data as Procedures
The pair data structure may be implemented in
terms of procedures
– employ the message passing programming style
(define (cons x y)
(lambda (message)
(cond ((eq? message 0) x)
((eq? message 1) y)
(else (error ”wrong argument to cons: ” message)))))
(define (car pair)
(pair 0))
(define (cdr pair)
(pair 1))
slide 9
Data as Procedures (contd)
The pair data structure may be implemented in terms of
procedures – alternative approach
(define (cons x y)
(lambda (selector)
(selector x y)))
(define (car pair)
(pair (lambda (x y) x)))
(define (cdr pair)
(pair (lambda (x y) y)))
slide 10
Box‐and‐Pointer Notation
Graphical representation of objects in Scheme
– an object is represented as a pointer to a box containing the value
of the object
– primitive objects: boxes with a single value
– pairs: double‐boxes (car and cdr of the pair)
Example:
– (cons 1 2)
slide 11
Pairs and the Closure Property
If an operation applied to a (subset of a) set of elements
returns an element of the set, then
– the set is closed under the operation
– the operation has the closure property over the set
cons
has the closure property over the pair data type
– consing pairs results in pairs
(pair? (cons 1 2))
(pair? (cons (cons 1 2) (cons 3 4)))
(pair? (cons 1 (cons 2 3)))
(pair? (cons (cons 1 2) 3))
slide 12
Structures with Pairs
Pairs can be combined to form various hierarchical
structures – structures whose components may also be
structures
slide 13
Sequences
A sequence is an ordered collection of objects
Sequences may be represented as chained pairs
– the ’car’ of a pair is (a pointer to) an object in the sequence
– the ’cdr’ of the pair is (a pointer to) the next element
– the ’cdr’ of the last pair is the empty pair*
;; the representation of the sequence 1 2 3 4
(cons 1
(cons 2
(cons 3
(cons 4 nil))))
* The empty pair is not represented as a pointer to an empty double box, but as a ’nowhere‐pointer’
slide 14
Lists
Lists are sequences of pairs formed by successive consing
– the ’car’ of a list is the first element of the list
– the ’cdr’ of a list is the rest of the list (a list)
– the ’cdr’ of a one‐element list is the empty pair (the empty list)
An object is a list (list?) iff
– it is either a pair (pair?), or
– it is an empty list (null?)
(cons 1 (cons 2 (cons 3 (cons 4 nil))))
(list 1 2 3 4)
;; (1 2 3 4)
(car (list 1 2 3 4))
;; 1
(cdr (list 1 2 3 4))
;; (2 3 4)
slide 15
Accessing List Elements
Lists are sequences of pairs
– elements may be accessed by a combination of cars and cdrs
(define my-list (list 1 2 3 4))
(car my-list)
;; 1
(car (cdr my-list))
;; 2
(cadr my-list)
;; 2
(car (cdr (cdr my-list)))
;; 3
(caddr my-list)
;; 3
slide 16
Operations on Lists
’Random’ access
(list-ref (list 1 2 3) 2)
;; 3 (0-based indexing)
(second (list 1 2 3))
;; 3
(last (list 1 2 3))
;; 3
Sublisting
(sublist (list 1 2 3) 1 2)
;; (2 3)
(list-tail (list 1 2 3) 1)
;; (2 3)
(list-head (list 1 2 3) 2)
;; (1 2)
(last-pair (list 1 2 3))
;; (3)
slide 17
Iteration and Recursion over Lists
The stop condition – is the list an empty list?
;; recursive process
(define (length list)
(if (null? list)
0
(+ 1 (length (cdr list)))))
;; iterative process (with named let)
(define (length list)
(let iter ((list list) (length 0))
(if (null? list)
length
(iter (cdr list) (+ length 1)))))
slide 18
Combining Lists
Consing, listing and appending
(cons 1
(list 2 3 4))
;; a list (1 2 3 4) with 4 elements
(cons (list 1 2 3)
4)
;; a pair (not a list!)
(list (list 1 2 3)
(list 4 5 6))
;; a list ((1 2 3) (4 5 6)) with 2 elements
(append (list 1 2 3)
(list 4 5 6))
;; a list (1 2 3 4 5 6) with 6 elements
slide 19
Append
How does append work?
;; recursive version
(define (append l1 l2)
(if (null? l1)
l2
(cons (car l1) (append (cdr l1) l2))))
;; iterative version?
slide 20
Mapping over Lists
Mapping = performing an operation on each element of a
list
(map square (list 1 2 3))
;; (1 4 9)
(map inverse
(map square (list 1 2 3)))
;; (1 1/4 1/9)
(map (lambda (x)
(inverse (square x)))
(list 1 2 3))
(map (compose inverse square)
(list 1 2 3))
slide 21
Mapping over Lists (contd)
Mapping over lists of procedures
(map (lambda (p)
(p 2))
(list zero? square -1+ factorial))
;; (#f 4 1 24)
Mapping over multiple lists
(map (lambda (p x)
(p x))
(list zero? square -1+ factorial)
(list 0 1 2 3))
;; (#t 1 1 6)
slide 22
Map
How does map work?
;; recursive version (for mapping over one list only)
(define (map operation list)
(if (null? list)
list
;; or nil
(cons (operation (car list))
(map operation (cdr list)))))
;; iterative version?
slide 23
Trees
Trees are hierarchical structures whose elements are
– leaves (objects other than trees)
– intermediate nodes (trees)
t
(define t
(make-tree (make-tree 1)
(make-tree 2
1
(make-tree 3 4))
(make-tree 5 6 7 8)))
2
5
3
6
7
8
4
slide 24
Trees (contd)
Trees can be implemented with pairs
(cons (cons 1
(cons 2 nil))
(cons 3
(cons 4 nil)))
slide 25
Mapping over Trees
Mapping over trees (tree‐mapping)
– recursively traverse the tree structure
– apply a procedure to every leaf node in a tree
(define t
(cons (list 1 2) (list 3 4)))
(tree-map square t)
;; ((1 4) 9 16)
(tree-map (lambda (x)
(list x (square x)))
t)
;; (((1 1) (2 4)) (3 9) (4 16))
slide 26
Tree‐map
How does tree-map work?
(define (tree-map procedure tree)
(cond ((null? tree) tree)
((not (pair? tree)) (procedure tree))
(else (cons (tree-map procedure (car tree))
(tree-map procedure (cdr tree))))))
(define (tree-double tree)
(tree-map (lambda (x) (list x x))
tree))
(tree-double (cons (list 1 2)
(list 3 4)))
;; (((1 1) (2 2)) (3 3) (4 4))
slide 27
Sequence Operations
General sequence operation types
– sequence generators (take a specification and produce a sequence)
– sequence processors (take a sequence and return a sequence) –
e.g., map, filter
– sequence sinks (take a sequence and produce a non‐sequence
result) – e.g., accumulate (reduce)
slide 28
Sequence Generators
Enumerators
(define (enumerate-interval from to)
(if (> from to)
nil
(cons from (enumerate-interval (+ from 1) to))))
(enumerate-interval 1 5)
;; (1 2 3 4 5)
(define (enumerate-tree tree)
(cond ((null? tree) tree)
((not (pair? tree)) (list tree))
(else (append (enumerate-tree (car tree))
(enumerate-tree (cdr tree))))))
(enumerate-tree (cons (list 1 2) (list 3 4))) ;; (1 2 3 4)
slide 29
Filters
How does filter work?
(define (filter predicate list)
(cond ((null? list) list)
((predicate (car list))
(cons (car list) (filter predicate (cdr list))))
(else (filter predicate (cdr list)))))
(filter even? (enumerate-interval 0 10))
;; (0 2 4 6 8 10)
slide 30
Accumulators
How does accumulate work?
(define (accumulate operator null list)
(if (null? list)
null
(operator (car list)
(accumulate operator null (cdr list)))))
(accumulate + 0 (list 1 2 3)
;; 6
(accumulate cons nil (list 1 2 3))
;; (1 2 3)
(a NOOP transducer)
slide 31
Sequences as Signals
Signal processing can be represented as passing a sequence
from a generator through processors to a sink
(define (even-fibs n)
(accumulate cons
nil
(filter even?
(map fib
(enumerate-interval 0 n)))))
slide 32
Nested Mapping
Problem: produce all ordered pairs of numbers from an
interval
(define (pairs interval)
(map (lambda (i)
(map (lambda (j)
(list i j))
interval))
interval))
(pairs (list 1 2))
;; (((1 1) (1 2)) ((2 1) (2 2)))
:\
;; now we ’flatten’ the result
(accumulate append nil (pairs (list 1 2)))
;; ((1 1) (1 2) (2 1) (2 2))
:))
slide 33
Flatmap
The pattern of mapping and successive flattening is
implemented in flatmap
(define (flatmap procedure list)
(accumulate append nil (map procedure list)))
(flatmap (lambda (i)
(map (lambda (j) (list i j))
interval))
interval)
;; ((1 1) (1 2) (2 1) (2 2))
slide 34
Displaying Pairs
A pair where the second element is not a pair is displayed
using the dot notation
(cons 1 2)
;; (1 . 2)
(cons (cons 1 2) 3)
;; ((1 . 2) . 3)
A pair where the second element is a pair or nil (the pair is
a list) is displayed with omission of the dot
(cons 1 (cons 2 nil))
;; (1 2)
(cons 1 (list 2 3))
;; (1 2 3), not (1 . (2 3))
slide 35
Displaying Pairs (contd)
A pretty‐printer for pairs
(define (print object)
(define (print-pair pair)
(print (car pair))
(cond ((null? (cdr pair)) nil)
((not (pair? (cdr pair)))
(display ” . ”) (display (cdr pair)))
(else (display ” ”) (print-pair (cdr pair)))))
(cond ((null? object) (display ”()”))
((not (pair? object)) (display object))
(else (display ”(”)
(print-pair object)
(display ”)”))))
slide 36
Picture Language
SICP 2.2.4
– some concepts are well explained in this section
slide 37