CS 2360
Spring 1998
Homework Assignment 3
Due no later than 8:00am, Monday, April 27, 1998
The purpose of this homework assignment is to give you some practice
with applicative programming. Now that you've had two whole weeks
of practice with recursion, we're taking that tool away from you for a
week. To get repetitive operations this week, you can use only MAPCAR
and MAPLIST. You can also use APPLY, FUNCALL, FUNCTION (or #'), LAMBDA
(which is really punctuation, not a function name), APPEND, LIST, CONS,
FIRST, SECOND, REST, IF, COND, DEFUN, QUOTE (or '), the arithmetic
operators, and the equality and inequality predicates. Again, you can't
use recursion this week. And remember to employ all those good
programming guidelines from the previous weeks.
Here's an example of applicative programming that might help you with
some of the problems that follow. Remember MY-ASSOC from homework
assignment 1? It worked like this:
? (my-assoc 'a '((c d)(a b)(e f)))
(A B)
? (my-assoc 'c '((c d)(a b)(e f)))
(C D)
The idea is that you give MY-ASSOC a key or index and a lookup table
called an association list, and MY-ASSOC searches the list for an
association pair that begins with the given key. You wrote a recursive
version of MY-ASSOC, but you could write a function with the same
behavior using only applicative programming. Here's one way:
(defun my-assoc (key a-list)
(apply #'append
(maplist #'(lambda (x)
(if (eql key (first (first x)))
(first x)
nil))
a-list)))
Try it out and see it work. And note that if your association list
contains dotted pairs (like an association list constructed by
PAIRLIS...remember those questions from your midterm?), this version of
MY-ASSOC has a tendency to blow up.
1) Speaking of PAIRLIS, you now get to limber up by making a new, applicative
version of PAIRLIS that you'll call MY-PAIRLIS. It works like it did on the
midterm, but it doesn't create dotted pairs. So it takes two lists of equal
length and makes an association list that associates elements of the first
list to corresponding elements of the second list. Here are some examples:
? (my-pairlis '(a b c) '(1 2 3))
((A 1) (B 2) (C 3))
? (my-pairlis '(a (b) c) '(1 2 3))
((A 1) ((B) 2) (C 3))
? (my-pairlis '(a b c) '(1 2 (3)))
((A 1) (B 2) (C (3)))
Don't worry about lists of unequal length.
2) Use applicative programming to write a function called SHUFFLE,
which takes two lists of equal length as input and interleaves or
shuffles the elements of those two lists to produce a single list which
is returned (like shuffling two halves of deck of cards one time). For
example:
? (shuffle '(1 2 3) '(4 5 6))
(1 4 2 5 3 6)
? (shuffle nil nil)
NIL
? (shuffle '(a b c d e) '(a b c d e))
(A A B B C C D D E E)
In the remaining problems, you'll write a program to transpose a song
from one key to another. In order to manipulate notes more efficiently,
we'll translate the notes into numbers. You may assume that anything
passed to the functions you construct will be valid input; don't worry
about error checking. Assume that all numbers are integers. Here is
the correspondence between notes and numbers for a one-octave scale:
C = 1
C-sharp = 2
D = 3
D-sharp = 4
E = 5
F = 6
F-sharp = 7
G = 8
G-sharp = 9
A = 10
A-sharp = 11
B = 12
Here is an association list, stored in a variable called NOTE-TABLE,
that contains the information above:
(setq note-table '((c 1)
(c-sharp 2)
(d 3)
(d-sharp 4)
(e 5)
(f 6)
(f-sharp 7)
(g 8)
(g-sharp 9)
(a 10)
(a-sharp 11)
(b 12)))
You'll want to pass this list to some of the functions you define below.
3) Write a function called NOTES-TO-NUMBERS that takes two arguments.
The first argument is the association list shown above. The second
argument is a list of notes. Your function should return the
corresponding list of numbers. Here's an example of a call to
NOTES-TO-NUMBERS with the first seven notes of "Mary Had a Little Lamb":
? (notes-to-numbers note-table '(e d c d e e e))
(5 3 1 3 5 5 5)
4) Write a function called NUMBERS-TO-NOTES that takes two arguments.
The first argument is the association list shown above. The second
argument is a list of numbers. Your function should return the
corresponding list of notes. Here's an example of a call to
NUMBERS-TO-NOTES:
? (numbers-to-notes note-table '(5 3 1 3 5 5 5))
(E D C D E E E)
Hint: Do problem 5 before you do problem 4.
5) Since NOTE-TABLE is keyed by note, your function MY-ASSOC can't
look up numbers in it. You'll need to write a table searching function
that's sort of like MY-ASSOC, except that it searches NOTE-TABLE by
number, not by note. Call this function MY-OTHER-ASSOC. It would
work like this:
? (my-other-assoc 10 note-table)
(A 10)
? (my-other-assoc 3 note-table)
(D 3)
? (my-other-assoc 0 note-table)
NIL
6) To transpose a piece of music by n half steps, we begin by adding
the value n to each note in the piece. Write a function called RAISE
that takes a number n and a list of numbers as arguments and raises
each number in the list by the value n. Here's an example of
transposing "Mary Had a Little Lamb" five half steps from the key of
C to the key of F:
? (raise 5 '(5 3 1 3 5 5 5))
(10 8 6 8 10 10 10)
7) Sometimes when we raise the value of a note, we may raise it right
into the next octave. For instance, if we raise the triad C-E-G
represented by the list (1 5 8) into the key of F by adding five to each
note, we get (6 10 13), or F-A-C. Here the C note, represented by the
number 13, is an octave above the regular C, represented by 1. Write a
function NORMALIZE that takes a list of numbers as input and
"normalizes" them so that they're all between 1 and 12 (inclusive).
A number greater than 12 should have 12 subtracted from it; a number
less than 1 should have 12 added to it. For example:
? (normalize '(6 10 13))
(6 10 1)
8) Write a function TRANSPOSE that takes three arguments: a number n,
a song represented by a list of notes, and the note table given way up
above, and returns the song transposed by n half steps. For example:
? (transpose 5 '(e d c d e e e) note-table)
(A G F G A A A)
That's it! Good luck with your remaining midterms.
Copyright by somebody else. This assignment was not invented by me.
Last revised: April 23, 1998