Due Date: Due by
midnight of the morning of your next
lab, in this case,
Monday 3 February. No assignments are accepted afterward.
Please submit the problems
marked “in lab” while in the laboratory and ask the instructor or grutor check
them before you leave. It would also be good, if you have time, to work on the
problems not to be turned in and ask questions about them. In this way, you can
anticipate areas of difficulty for the week to come.
Constraint: Since the
purpose of this assignment is to exercise higher-order functions, use of recursion is prohibited except within the functions that I
provide.
Submissions:
It would be a good idea read Chapters 2 and 3 in the
course text in conjunction with this assignment. You will also need to
familiarize yourself with Unix, the operating system used on turing, the computer we use. You will also need to learn the
basics of emacs, the recommended text editor. Finally, it may be worth spending
some time learning to an e-mail program such as elm or pine. Documentation on
Unix, emacs, and other items can be found on the CS department help page: http://www.cs.hmc.edu/help.html . Please spend some time
reading documentation, and trying out Unix, emacs, and e-mail before embarking
on the main part of the assignment. The instructor, grutors, and CS staff in
the terminal room will be happy to help you when you have questions.
Note:
Sometimes we have problems with people who resist learning these basic things,
thinking they will do them on their own windows platform or whatever. Be
assured that knowing a modest set of unix commands, as well as using emacs, are
life skills from which you will inevitably benefit. Emacs in particular is not
some flash-in-the pan editor; it has been around for over 25 years and will
continue to be around. If you resist, you may come up short at a time when you
cannot afford to be foundering on such things.
Note: In
Unix software (including rex and emacs), most things are case-senstive. For
example, First is not the same thing as first.
It would be a good idea to become familiar with the
following built-in rex functions.
They could be very useful in solving the problems presented. It is suggested
that you try a few examples to get familiar with these functions.
|
Function
calling form |
Returned
result |
|
first(L) |
the first element of non-empty list L |
|
rest(L) |
the list of all elements but the first of L |
|
second(L) |
the second element of non-empty list L |
|
third(L) |
the third element of non-empty list L |
|
null(L) |
1 if the list L is empty, 0 otherwise |
|
length(L) |
the number of elements in the list L. |
|
sort(L) |
a sorted list containing the elements of
list L |
|
map(F, L) |
a list formed by applying function F to
each of the elements of list L |
|
mappend(F, L) |
provided that F returns a list, the result
of appending together the results of applying F to each element of list L |
|
reduce(B, U, L) |
the value obtained by applying binary
operator B to the elements of L and an accumulated value, one at a time; U is
the unit returned for the empty list |
|
member(E, L) |
1 if E is a member of list L, 0 otherwise |
|
explode(S) |
the list of individual characters in string
S |
|
implode(L) |
assuming L is a list of characters, the
string formed from those characters |
|
keep(P, L) |
the list of elements in L for which
predicate P is true |
|
find(P, L) |
the suffix of L beginning with the first
element for which predicate P is true |
|
remove_duplicates(L) |
a list containing the elements of L without
duplication |
|
concat(S, T) |
the string resulting from concatenating
strings S and T (can be used with any number of arguments.) |
|
pow(N, P) |
number N raised to the power P |
|
Value1 == Value2 |
1 if the two values are the same, 0
otherwise |
|
Var =Value |
equate a variable Var to a value Value
(don’t use as if assignment.) |
|
Command |
Meaning |
|
ls |
list
directory contents |
|
mkdir
name |
make
a directory |
|
cd directory |
change
to a named directory |
|
cd
.. |
change
to the parent of the current directory |
|
cd |
change
to your home directory |
|
cat > file |
put
input into a file (terminate with control-D) |
|
rm file |
remove
(delete) a file |
|
rmdir
directory |
remove
(delete) a directory |
|
mv file directory |
move
a file to the named directory |
|
mv file name |
rename
a file to a new name |
|
cp file directory |
copy
a file to the named directory |
|
cp file name |
copy
a file to a new name |
|
more |
show
contents of a text file |
|
emacs |
text
editor |
|
elm or pine |
mailer |
|
rex |
rex
language execution |
|
Symbol |
Meaning |
|
. |
the current directory |
|
.. |
the parent directory of the
current directory |
|
~jones |
the home directory of jones |
|
~ |
your own home directory |
|
/ |
the root directory of the
entire system |
Note
carefully the difference between starting a file name with ~ vs. / vs. neither
of these. In the first case it is relative to the user’s home directory, in the
second it is absolute, and in the last case, the name is relative to the current directory.
|
Button |
Use |
|
left button |
select by clicking or
dragging |
|
middle button |
paste |
|
right button |
display pop-up menu |
Life will be simpler if you create a separate
directory for each assignment. Later on, some assignments have multiple files,
and it is easier to submit everything in a directory than pick things out of a
directory. To create a directory for a01, for example:
mkdir ~/courses/cs60/a01
To work in the directory you created:
cd ~/courses/cs60/a01
Copy the “skeleton” file to your directory:
cp /cs/cs60/a/01/a01.rex ~/courses/cs60/a01
which gives you a file named
a01.rex
that you can edit with your own code and comments.
This file must be loadable into the rex system without generating any errors,
so make sure you have comments around all the non-rex parts of your answers.
Submit your file by, while you are in the same directory:
cs60submit a01.rex
The cs60submit program will hassle you if you are in your home
directory instead. You will be prompted for the assignment number; answer with
the number 01.
You can submit the assignment as many times as you
want. Only the last submission you make before the deadline will be graded, so
this is a great way to make backups of your work as you go along.
[[2, 3], [3, 1]] 1267650600228229401496703205376[[2, 100]]/cs/cs60/a/01/a01.rexfactors that will factor numbers
for you. You don’t need to understand the coding of this function yet;
just use it. v24
v576
v1024
v255255
v139843693414425v24 = [[2, 3], [3, 1]];
unFactor that takes
the given representation as an argument and produces the number being
represented. For example,unFactor([[2, 3], [3, 1]])
==> 24.unFactor could be
called the inverse of
function factors because it
has the property thatunFactor(factors(N)) ==> Nfor
any positive N. Your definition should make use
of the higher-order functions reduce and map. It can employ the built-in
function pow, which raises numbers to a power.The text and lecture notes explain that binary
relations can be identified with sets of ordered pairs; two elements x and y
are said to be related by a
relation if the pair (x,y) is in the set. Any relation might or might not have
the following properties:
A relation is called reflexive if every element in the domain of interest is related
to itself; that is, if the pair [x,
x] is in the relation for every
relevant x.
A relation is symmetric if whenever [x, y] is in the relation so
is [y, x].
Finally, a relation is said to be transitive if whenever [x, y] and [y, z] are in the
relation, so is [x ,z].
An equivalence relation is a binary relation that is reflexive, symmetric and
transitive. For example, given the finite set S = {1,2,3,4,5,6,7}, the relation on this set that
relates two numbers in this set if they have the same remainder when divided by
three (also known as congruent mod 3)
is an equivalence relation.
As discussed in the text, we can represent relations on a finite set as a list
of all the pairs that are related. For example, the congruent mod 3 on the above set S could be represented as the following list of pairs:
[[1,1], [1,4], [1,7], [2,2], [2,5], [3,3], [3,6], [4,1], [4,4], [4,7], [5,2], [5,5], [6,3], [6,6], [7,1], [7,4], [7,7]]
However, the properties of equivalence relations
permit a more compact data representation:
as a set of equivalence classes,
wherein exactly the elements related to each other are grouped into a single
equivalence class. The definition of equivalence relation ensures that
equivalence classes don’t overlap (why?). For example, the relation above could
be represented as the set of equivalence classes below:
[[1, 4, 7], [2, 5], [3, 6]]
which is obviously more compact, as well as more readable.
factors provided in the skeleton a01.rex, along with other rex functions, define a
related function uniqueFactors that
gives the unique factors of a number, without regard to multiplicity of
the factors. For example, uniqueFactors(1025) ==>
[5, 41]ec32 uniqueFactors. A correct answer will have the property that
each number is in exactly one equivalence class. (Our solution checker
will not care about the order in which you listed the classes, nor will
it care about the order within the classes.)equiv
that will tell whether two elements are
equivalent with respect to a given list of equivalence classes:equiv(M,
N, EC) ==> 1 if M is equivalent to N in EC,
0 otherwiseequiv(14,
28, ec32) ==> 1 equiv(3,
28, ec32) ==> 0 equiv(7,
28, ec32) ==> 0 3.
Functional
Anagrams
One word is an anagram of another if it has exactly the same letters, with the
same multiplicity of each letter, but possibly in a different order. For
example, “elvis” is an anagram of “lives” but “eyes” is not an anagram of
“yes”. It should be obvious that we are dealing with an equivalence relation on
a set of words.
isAnagramOf that will
check whether one word is an anagram of another, for example: 1 isAnagramOf("eyes",
"yes")
==>
0anagramsOf that will create from a word and a list
of words the anagrams of the word that appear in the list. For example,anagramClasses that will create, from a list of words,
the list of equivalence classes for the relation isAnagramOf.4.
Double Anagrams (Optional extra credit, for those who
want more challenge)
Two pairs
of words are called a double anagram
if the concatenations of the words in each pair are an anagram. For example the
pair of pairs
[“apple”, “fast”] [“flap”, “paste”]
is a double anagram because “applefast” and “flappaste” are anagrams. Construct
a function doubleAnagramClasses that constructs
the double-anagram non-trivial equivalence classes for pairs of words formed
from the words in its argument list of words. For example:
doubleAnagramClasses(
["aced", "cadet", "cut", "duct",
"paint", "pine", "put",
"putt", "tape", "taped", "twin",
"watt", "wet"]) ==>
[[[“duct”, “tape”], [“cut”, “taped”], [“aced”, “putt”], [“cadet”, “put”]],
[[“tape”, “twin”], [“paint”,
“wet”], [“pine”, “watt”]]]
(so there are two non-trivial equivalence classes in this case).
By “non-trivial” here, we mean to exclude the case
where a word is paired with itself.