Reading: Online class notes about SML. Start Chapter 6 of
the text.
Catch up: If you are behind on
any of the Java material, now is the time to catch up!
A) Other Sets than HashSets.
You don't need to hand anything in for this part.
1) Look up the JavaDocs for Set. Notice that besides HashSet,
there are two other implementations: TreeSet and LinkedHashSet.
HashSet is the fastest, but when iterating through a HashSet the
elements arrive in no particular order. With a TreeSet they arrive in
sorted order and with a LinkedHashSet they arrive in the order of
insertion.
2) Your Sieve class last week printed out the primes up to 20 in a
meaningless order. Make a minimal modification to your class so the printPrimes()
method lists the primes in ascending order. Check it works on the
primes under 100, printing them in ascending order.
B) Some SML problems for
practice with recursion and lists. (Email your source
code to hand these in)
1) Write a recursive method, oddfactor(n),
which outputs the largest odd factor of n. (Hint: If n
is odd, that is
the answer, but if n is even you can divide n by 2 as
many times as
necessary until you have an odd number.)
- oddfactor(100);
val it = 25 : int
- oddfactor(16);
val it = 1 : int
2) Write a recursive method, zeroones(n), which
creates a list of n zeros alternating with n
ones. Assume n>=0.
- zeroone(6);
val it = [0,1,0,1,0,1,0,1,0,1,0,1] : int list
3) Write a recursive method, zerosones(n),
which creates a string of n zeros followed by n
ones. Assume n>=0. Look for an easy way to do this in one
recursive method, without any helper methods.
- zerosones(6);
val it = [0,0,0,0,0,0,1,1,1,1,1,1] : int list
4) Write a recursive method, copy(x,n), which
creates a list of n copies of x.
Assume n>=0.
- copy(7, 5);
val it = [7,7,7,7,7] : int list
5) Write a recursive method, rep(n), which
creates a list with one 1, two 2's, three 3's, ..., up to n n's. Hint: You may use
your copy() method from above.
- rep(5);
val it = [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5] : int list
6) Write a recursive
method, count(L,x)
which counts the number of times x appears in the given list.
Examples:
- count([1,4,4,4,5], 4);
val it = 3 : int
- count([1,4,4,4,5], 3);
val it = 0 : int
7) Write a recursive
method, remove(L,x)
which produces a list like the given list, but with any and all
appearances of x removed.
Examples:
- remove ([1,2,3,4,5,4,3,2,1], 2);
val it = [1,3,4,5,4,3,1] : int list
- remove([1,2,3,4,5], 7);
val it = [1,2,3,4,5] : int list
- remove([3,2,3,2,3,2,3,2], 3);
val it = [2,2,2,2] : int list
8) Write a recursive method listSum(L1, L2)
which takes two lists of integers and produces a list of corresponding
sums. The ith element of the result is the sum
of the ith element of L1 and the ith
element of L2. This is
a special case of matrix addition. You may assume both lists are the
same length. Your method will recurse down both lists together, adding
the two heads as it builds up its answer.
- listSum([1,2,3], [100,200,1000]);
val it = [101,202,1003] : int list
9) Write a recursive method last(L)
which returns the last element of a list. (Don't take the head of the
reverse.) Assume L is not nil.
- last([1,2,3]);
val it = 3 : int
10) Write a recursive method middle(L)
which returns the middle of a list, meaning a list of all the elements
except the first and last. Don't worry about lists of length less than
2, in other words you can return anything or generate an error in those
cases. You may want to write a helper function first.
- middle([1,2,3,4,5,6,7]);
val it = [2,3,4,5,6] : int list
Extra credit: Write a recursive method p(L) which
outputs true or false according to whether the list
L is a palindrome.
A palindrome is a sequence which is the same when reversed. Don't use a reverse method
to explicitly reverse the entire list. Instead consider a recursive
definition for palindromes involving the first term, the last term, and
the middle n-2 terms. Design
your base cases so the method works with both odd and
even length sequances.
- p([1,2,3,2,1]);
val it = true : bool
- p([1,2,3,4,2,3,1]);
val it = false : bool
- p([2,3,2,3]);
val it = false : bool
- p([3,1,1,3]);
val it = true : bool