PART 1: Association Lists

Download a copy of this file and add the following definitions. Note: you should comment each function with a description of its behavior.

1. Define a function named translate that takes one input, a list representing a codon, and returns the abbreviation for the corresponding amino acid. For example, (translate '(G G A)) should evaluate to G.
   
   
2. Define a function named translate-sequence that takes one input, an arbitrarily long sequence of bases, and returns the corresponding list of amino acid abbreviations. That is, the first symbol in the returned list should be the amino acid corresponding to the first three bases, the second symbol should be the amino acid corresponding to the next three bases, etc. If the length of the sequence is not a multiple of three, any trailing bases should be ignored. For example, (translate-sequence '(G G A U U C A C C C)) should evaluate to (G F T).
   
   
3. When scientists extract mRNA samples from a cell, they invariably obtain partial sequences. Since the start of the sequence may be unknown, it is unclear exactly how the codons will be grouped in an actual translation. For example, in the sequence GGAUUCACCC the codons could be grouped starting at the beginning (yielding codons GGA UUC ACC), at the second base (yielding codons GAU UCA CCC), or at the third base (yielding codons AUU CAC). In addition, it is possible that the sequence has been read backwards, so the actual sequence to be translated should be CCCACUUAGG.

   Define a function named translate-all-possible that takes one input, an arbitrarily long sequence of bases, and returns a list containing all six possible translations of that sequence. Any extra bases at the beginning or end of the sequence should be ignored in the translation. For example, (translate-all-possible '(G G A U U C A C C C)) should evaluate to ((G F T) (N S P) (I H) (P T *) (P L R) (H L)).
   
   

PART 2: Binary Trees

In class, we discussed how structured lists could be used to represent binary trees. For example, the following binary tree is represented by the list to the right:

(define ANIMALS '(dog (bird (horse () ()) (cat () ())) (possum (dog () ()) ())))

Several utility functions (empty-tree?, root, left-subtree, and right-subtree) are provided for you in hw6.ss). Add the following functions for manipulating binary trees.

1. Define a function named rightmost that takes one input, a list representing a binary tree, and returns the value that is stored rightmost in the tree. For example, given the ANIMALS structure above, (rightmost ANIMALS) should evaluate to possum.
   
   
2. Define a function named height that takes one input, a list representing a binary tree, and returns the height (i.e., maximum root-to-leaf path length) in the tree. For example, given the ANIMALS structure above, (height ANIMALS) should evaluate to 3.
   
   
3. Define a function named num-occur that takes two inputs, a list representing a binary tree and a value, and returns the number of occurrences of the value in that tree. For example, given the ANIMALS structure above, (num-occur ANIMALS 'dog) should evaluate to 2.
   
   
4. Define a function named contains? that takes two inputs, a list representing a binary tree and a value, and returns #t if the list contains the value (otherwise #f). For example, given the ANIMALS structure above, (contains? ANIMALS 'emu) should evaluate to #f while (contains? ANIMALS 'cat) should evaluate to #t.
   
   

PART 3: Lazy Streams

Bizz-buzz is a children's game in which a circle of people take turns counting out numbers, but with a wrinkle. Two numbers are selected ahead of time, say 3 and 5. When counting out numbers, multiples of the first selected number (3) must be replaced with "bizz." Likewise, multiples of the second selected number (5) must be replaced by "buzz," and multiples of both (3 and 5) must be replaced by "bizz-buzz." For example:

You are to define Scheme functions that can be used to generate streams that represent bizz-buzz sequences.

1. Define a function named replaceStream that takes three inputs, a function, a value, and a stream. This function should behave similarly to the filterStream function written in class, except that instead of filtering the input stream based on the function, it replaces each qualifying element with the new value. For example: > (define naturals (arithSequence 1 1)) > (lazyHead naturals 10) (1 2 3 4 5 6 7 8 9 10) > (lazyHead (replaceStream even? 'boo naturals) 10) (1 boo 3 boo 5 boo 7 boo 9 boo) > (lazyHead (replaceStream (lambda (x) (and (>= x 3) (<= x 7))) 0 naturals) 15) (1 2 0 0 0 0 0 8 9 10 11 12 13 14 15)
2. Define a function named bbSeq that takes two inputs, the selected numbers, and returns the stream representing the corresponding bizz-buzz sequence. Note that constructing a particular bizz-buzz stream can be accomplished by starting with the natural number stream, then repeatedly transforming it (using replaceStream) so that multiples of the specified numbers are replaced the corresponding words. For example: