handout #2

CSE341—Programming Languages

Assignment #1 (ML)

due 11 pm, Thursday, 4/8/10

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. There will be a catalyst turnin link available from the class web page. You are allowed to use the standard functions abs and length, but otherwise 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 each of your functions.

Below is a list of function signatures for the problems in this set:

val pow = fn : int * int -> int

val sumTo = fn : int -> real

val repeat = fn : string * int -> string

val twos = fn : int -> int

val numNegative = fn : int list -> int

val absList = fn : (int * int) list -> (int * int) list

val split = fn : int list -> (int * int) list

val range = fn : int * int -> int list

val hailstone = fn : int -> int list

val isSorted = fn : int list -> bool

val collapse = fn : int list -> int list

val insert = fn : int * int list -> int list

val isort = fn : int list -> int list

val factors = fn : int -> int list

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 (exceptions are described starting on page 134 of the Ullman text). We simply won’t grade that code because we aren’t testing those cases.

1. (5 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. For our purposes, we will assume that every integer to the 0 power is 1 (this isn’t really true of 0 to the 0, but that’s okay).

2. (5 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. (5 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. (5 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. You may assume that the value passed to the function is not equal to 0.

5. (5 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.

6. (5 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 integer 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)]. This is easier to solve if you write a helper function to process one tuple.

7. (10 points) Define a function called split that takes a list of integers as an argument and that returns a list of the tuples obtained by splitting each integer in the list. Each integer should be split into a pair of integers whose sum equals the integer and which are each half of the original. For odd numbers, the second value should be one higher than the first. For example, split([5, 6, 8, 17, 93, 0]) should return [(2, 3), (3, 3), (4, 4), (8, 9), (46, 47), (0, 0)]. You may assume that all of the integers in the list passed to the function are greater than or equal to 0.

8. (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.

9. (10 points) Define a function called hailstone that takes an integer n as an argument and that returns the hailstone sequence starting with n and ending with 1. In the hailstone sequence, each integer n is followed by:

· n/2 if n is even

· 3n + 1 if n is odd

The sequences are called hailstone sequences because they rise and fall somewhat unpredictably. It is conjectured that all such sequences for positive integers eventually reach the value 1, at which point they start to repeat the sequence 1, 4, 2, 1, 4, 2, 1, 4, 2, and so on. Your function should return the list of integers obtained by computing the sequence until it reaches 1. For example, hailstone(7) should return [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]. The call hailstone(1) should return [1]. You may assume that the value passed to the function is greater than 0.

10. (10 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.

11. (10 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. For example, collapse([1, 2, 3, 4, 5]) should return [3, 7, 5].

12. (10 points) Define a function called insert that take an int and a sorted (nondecreasing) int list as parameters and that returns the list obtained by inserting the int into the list so as to preserve sorted order. For example, insert(8, [1, 3, 7, 9, 22, 38]) should return [1, 3, 7, 8, 9, 22, 38].

13. (10 points) Define a function isort that takes an int list as a parameter and that returns the list obtained by sorting the list into nondecreasing order. In writing isort, you should call your insert function from the previous problem. The result will be an ML solution to the classic insertion sort algorithm.

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.

14. (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 may assume that that the value passed to the function is greater than 0. 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.