Description
Objectives
• Work with lists
Activities
1. There are a number of equality functions in Scheme: =, eq?, eqv?, equal? for example, but
none of them “do it all” that is, work for symbols, numbers, and lists. For example, none of
these will say #t when comparing ’(a b c (1 2) 3.0) and ’(a b c (1 2) 3), although (= 3 3.0) is
true, and (equal? ’(a b c (1 2) 3.0) ’(a b c (1 2) 3.0) is true.
Write a Scheme function (better-equal? a b) that works for symbols, numbers, and lists
using the following definition:
(better-equal? a b) =
#t if a and b are symbols and (eq? a b),
#t if a and b are numbers and (= a b),
#t if a and b are lists whose corresponding members are better-equal?,
#f otherwise
2. Define a Scheme function (remove-all x l) that takes a number or symbol and a list, and
returns a list that is the same as l with all elements equal to x removed. This is different from
the remove presented in lecture that removed one element, but like the lecture version it should
not try to remove x from any nested elements. For examples
>( remove-all ’a ’(a b a c ))
(b c)
>( remove-all ’z ’(a b a c ))
(a b a c)
>( remove-all ’a ’(a ( a b c) b a (( a ))) c )
(( a b c) b (( a ))) c)
3. The dot product of two lists of numbers (x1 x2 x3) and (y1 y2 y3) is
x1 ∗ y1 + x2 ∗ y2 + x3 ∗ y3
(a) Define a Scheme function dot-prod that takes two lists of numbers as its inputs and returns
the dot product of those two lists. Do not use the built-in map function in this function.
You can assume the two lists have the same length.
1 CSE 1729
(b) Define a Scheme function dot-prod-with-map that computes the dot product (as defined
above), but uses the built-in map function. You may find a use for a function you defined
in Lab 6.
4. For Question 3, use an unordered list to represent sets (as in Section 2.3.3 in the textbook).
Use the following functions from the book as a starting point:
( define ( element-of-set ? x set )
( cond (( null ? set ) #f)
(( equal ? x ( car set )) # t)
( else ( element-of-set ? x ( cdr set )))))
( define ( adjoin-set x set )
( if ( element-of-set ? x set )
set
( cons x set )))
( define ( intersection-set set1 set2 )
( cond (( or ( null ? set1 ) ( null ? set2 )) ’())
(( element-of-set ? ( car set1 ) set2 )
( cons ( car set1 )
( intersection-set ( cdr set1 ) set2 )))
( else ( intersection-set ( cdr set1 ) set2 ))))
Define a Scheme function union-set which takes a two sets and returns the union of those two
sets (which is a set).
5. Define a Scheme function has-duplicates? which takes a list and returns #f if no two of its
members are equal, #t otherwise. Hint: Use the member function.
6. Define a Scheme function num-zeroes which takes a (possibly nested) list, and return the
number of zeros in the list. You should also include any zeroes in nested sublists in the count.
The list may include items of any type, and should count both 0 and 0.0 as zero.
7. Define a Scheme function (nested-reverse lst) which reverses a possibly nested list as follows:
• the elements of the list are in reverse order in the result, and
• any nested list is also reversed using (nested-reverse lst).
For example:
> ( nested-reverse ’(a b c ))
(c b a )
> ( nested-reverse ’(( a b c) 42 ( do re mi (1 2 3))))
(((3 2 1) mi re do ) 42 (c b a ))
2 CSE 1729