handout #3

CS341¾ Programming Languages

Assignment #1 (ML)

due 11 pm, Thursday, 1/11/07

In this assignment you will practice the ML building blocks described in pages 1—64 of the Ullman text. Collect your answers for all questions in a single file called hw1.sml. You should use the turnin utility on attu to submit your solution. Except as noted, you are not allowed to use features that aren’t described in pages 1—64 of the book. That means that you should not use pattern matching or let constructs. You are allowed to define “helper” functions to solve these problems and you can include any testing code you develop (although it should be labeled as such). You are expected to use good programming style and to comment your functions.

Several of these problems mention a precondition for a function. Such preconditions should always be commented. When a precondition is violated in ML, the right thing to do (just as it is in Java) is to throw an exception (it’s called raising an exception in ML). If you want to work on developing good habits by including code to raise an exception when a precondition fails, that would be fine. We simply won’t grade that code because we aren’t testing those cases. You will find a good explanation of exceptions in section 5.2.1 of the Ullman book (pages 134—135).

1. (10 points) Define a function called pow that takes two integers as arguments and that returns the result of raising the first integer to the power of the second (i.e., pow(x, y) should return x^y). You may assume that the function is not asked to compute a negative power.

2. (10 points) Define a function called sumTo that takes an integer n as an argument and that computes the sum of the first n reciprocals:

For example, sumTo(2) should return 1.5. The function should return 0.0 if n is 0. You may assume that the function is not passed a negative value of n.

3. (10 points) Define a function called repeat that takes a string and an integer as arguments and that returns a string composed of the given number of occurrences of the string. For example, repeat(“abc”, 3) should return “abcabcabc”. You may assume that the function is not passed a value for the second argument that is negative.

4. (10 points) Define a function called twos that takes a single integer argument and that returns the number of factors of two in the number. For example, the number 84 when expressed as a product of prime factors is 2 * 2 * 3 * 7, which means that it has 2 factors of 2. Similarly the number ~30 would be expressed as ~(2 * 3 * 5), which means that it has 1 factor of 2.

5. (10 points) Define a function called range that takes two integers x and y as arguments and that returns a list composed of the sequence of consecutive integers starting with x and ending with y. For example, range(18, 23) should return [18, 19, 20, 21, 22, 23] and range(~7, ~7) should return [~7]. If there are no integers in the range, as in the call range(5, 1), the function should return an empty list.

6. (10 points) Define a function called numNegative that takes a list of integers as an argument and that returns a count of the number of negative integers in the list. For example, numNegative([3, 17, ~9, 34, ~7, 2]) should return 2.

7. (10 points) Define a function called absList that takes a list of int * int tuples and that returns a new list of int * int tuples where every int is replaced by its absolute value. For example, absList([(~38, 47), (983, ~14), (~17, ~92), (0, 34)]) should return [(38, 47), (983, 14), (17, 92), (0, 34)].

8. (15 points) Define a function isSorted that takes a list of integers and that returns whether or not the list is in sorted (nondecreasing) order (true if it is, false if it is not). By definition, the empty list and a list of one element are considered to be sorted. You may call the built-in function length that returns the length of a list.

9. (15 points) Define a function called collapse that takes a list of integers as an argument and that returns the list obtained by collapsing successive pairs in the original list by replacing each pair with its sum. For example, collapse([1, 3, 5, 19, 7, 4]) should return [4, 24, 11] because the first pair (1 and 3) is collapsed into its sum (4), the second pair (5 and 19) is collapsed into its sum (24) and the third pair (7 and 4) is collapsed into its sum (11). If the list has an odd length, the final number in the list is not collapsed. You may call the built-in function length that returns the length of a list.

Extra Credit

As will always be the case, extra credit problems will be worth very few points, especially when you consider how much work they involve. Extra credit is for people who want to explore a little further. Remember that you are limited to constructs in pages 1—64 of the Ullman text.

10. (2 points) Define a function called factors that takes an integer as an argument and that returns an ordered list of the factors of that integer. Recall that a factor is a number that goes evenly into another. For example, the call factors(12) should return[1,2,3,4,6,12]. Your list has to include the factors in increasing order without duplicates. You will need to write a helper function to solve this task and it will take more than one argument. Your solution is required to run in O(n^0.5) time (time proportional to the square root of n). This does not require a lot of code. Stuart’s solution is a one-line function that calls a 5-line helper function.