Wednesday April 24.
Assignment V: Scheme.
1. Write a function Weave, that takes three lists of the same lenght, and
builds a list of triples with the corresponding entries in each list. For
example, if the inputs are (English, day, book), (Francais, jour, livre),
and (Espanol, dia, libro), the function returns the list:
((English, Francais, Espanol), (day, jour, dia), (book, livre, libro)).
2. We can use sets to represent lists. A set is an unordered collection with
no duplicates. Define the following functions:
a) set? applies to a list, and returns true if the list contains no duplicates.
The built-in predicate member is useful here.
b) make-set takes an arbitrary list and removes duplicates
in it. thereby creating the corresponding set.
c) set-equal returns true if two lists that are sets have
the same elements, in any order.
d) set-intersect is a binary operation that returns the set of elements common to
e) power-set build the set of all subsets of a set. For example,
(power-set ' (a b c)) yields:
(() (a) (b) (c) (a b) (b c) (a c) (a b c))
The critical step here is to understand how the power-set is built recursively
out of the power-set of a set with one fewer element. A useful additional
function here is one that takes a function, a value, and a list of lists, and
returns the result of applying the function to that value and each element of
the list (something like map, but where the function takes two arguments).
f) (Harder) The elements of a set are arbitrary, and can themselves be sets.
Therefore, membership should be defined in terms of set equality, and viceversa.
For example, we want to say that
(1 3 5) is an element of ( (2 4) (5 3 1) (0 2 3 4)).
Similarly, ((1 2) (3 4)) and ((4 3) (2 1)) are equal as sets.
Write the proper definitions for set-member and
set-equal that handle arbitrary sets.
g) In a functional language. arrays and matrices are described (clumsily)
as lists. For example, a 3 by 3 matrix is represented as a list of 3 lists.
We want to define a function TRANSPOSE, that interchanges rows and colums of
a matrix. For example:
transpose [[1,2,3],[4,5,6], [7,8,9]];
val it = [[1,4,7],[2,5,8],[3,6,9]] : int list list
Write the definition for transpose. You might want to use the following
function, that obtains the first column of a matrix:
fun col mat = map hd mat;
that is to say, map the function hd onto the list of rows (which makes a
list consisting of the first elements of each sublist).