This is the last homework assignment. Notice the unusual date and time that it's due. I really meant to make it due at midnight, but I was afraid of confusion between the midnight at the beginnning of Thursday, and the midnight at the end of Thursday. 11:59 PM is unambiguous.
In the ML problems below, to get the highest score you
must use pattern matching, instead of selector functions
hd, tl, etc. You must also minimize the use
of explicit conditionals. Whenever a condition can be encoded in a
pattern, use the pattern.
Single-word anagrams are pairs of words with precisely the same letters, but in a different order. The number of occurrences of each letter must be preserved. For example, reel and leer, prat and trap, raptor and parrot, altair and lariat, crass and scars are anagram pairs, but not crass and cars. Visit the Internet Anagram Server (or is it I Rearrangement Servant?) to have fun with multiword anagrams. Did you notice that there is an anagram at the head of my own personal web page?
Some people like word games enough to buy an anagram dictionary (such a thing really exists), providing lots of one-word anagrams. An anagram dictionary is built by associating every word with its anagram-canonical form---that is, the letters of the word in alphabetical order. Since all anagram-equivalent words have the same anagram-canonical form, this allows a reader to look up all the anagrams of a given word rather easily. For example, the anagram-canonical form for reel and leer is eelr for altair and lariat it's aailrt. The anagram order on words is the normal lexicographical (alphabetical) order of their anagram-canonical forms. For fun, try to figure out the last word in an anagram dictionary.
The first two problems below are related to the creation of an anagram dictionary.
Write a tiny and simple ML function to sort words in
anagram order. Look at my examples of
functions related to
lexicographical and anagram sorting. Notice that I almost defined
anasort, but I left out four pieces. Fill in those pieces
to complete the definition. Please try to find the perfect code to
fill in for the missing pieces, rather than using your creative
originality.
Testing is not very interesting for this problem, so you
can have fun with your example executions. Notice that
anasort produces a list of the same words that are in the
input list, sorted in anagam order. It does not output the
anagram-canonical forms. The amusing thing about anasort
is the way that it uses the sort function to define a
comparator for the sort function.
The essential computation in this problem works on lists of
characters. I showed how to ``explode'' a word, presented
as a string, into a list of characters. But, the input and the final
output are lists of strings.
Write another simple ML function, anadict, to
create an actual anagram dictionary.
Look at my examples of
functions related to
lexicographical and anagram sorting again. Notice that I almost
defined anadict, but I left out ten pieces. Fill in those
pieces to complete the definition. The input is a list of words,
given as strings, just like the input to
anasort. The output is a list of lists of
strings. Each of the sublists starts with an
anagram-canonical form, which is followed by all of the words that
have that canonical form. The outer list is ordered lexicographically
by the anagram-canonical forms. The words in each sublist (not
including the anagram-canonical form at the head) are ordered
lexicographically.
You don't use anasort in the definition of
anadict, but the experience of writing
anasort should help you understand how to write
anadict. Use map to expand each word in the
input list into a pair of the word and its anagram-canonical form. You
will need the function implode, which is the inverse to
explode. Sort the pairs lexicographically on the
canonical forms. Merge all pairs with the same canonical form. Again,
try to write the perfect program based on these ideas, rather than
thinking of your own different approach to the problem.
This Prolog problem does not demonstrate normal Prolog programming. Instead, it explores the limits of computation with variable equivalences and unification.
Look at the equivalence
class example in the lecture notes. I provided partial
definitions of trivequiv, insert,
unitequiv, and join, with ellipses (...)
indicating missing parts for you to fill in. We will discuss
equivalence relations in class.
The basic idea in this problem is to represent an equivalence
relation as a list of variables, where the repetition of a
variable indicates an equivalence between positions in the list. I
provide the instequivclasses relation to fill in an
integer label for each equivalence class. The definition of
instequivclasses also illuminates the way that my weird
representation of equivalence relations works.
trivequiv(N,X) holds for integers N,
when X is the trivial equivalence relation of
size N (i.e., each position is equivalent only to
itself). unitequiv(N,I,J,X) is the unit
equivalence relation of size N, with positions
I and J equivalent, but no other nontrivial
equivalences. insert is a conventional operation for
inserting an item into a list: insert(I,X,Y,Z) holds
when Z is the result of inserting the item X
into the Ith position in the list
Y. insert is a key tool for defining
unitequiv.
join(X,Y) joins the two equivalence relations
X and Y, so that positions equivalent
whenever either of X or Y makes them
equivalent. join is destructive: both X and
Y take on the new value of the join. The destructive
quality of join is unavoidable with my weird
representation of equivalence relations. Also, my representation
supports increasing equivalence, but never decreasing equivalence.
All of the tools that you need for this problem are in the example file. Don't waste your time hunting through the Prolog documentation for tricky features.