[ ^ CSE 341, Winter 2004 home page ]

Homework 2

Due: Fri 23 Jan 2004

Instructions

Complete the following and save them to a .sml file. Written explanations may be placed in comments within your .sml file. Run your .sml file and save the output. Do ALL of the following to recieve credit for your work:

Email your .sml file and output file as attachments to Sandra, with a subject line EXACTLY as follows, replacing lastname with your last name and firstname with your first name: [cse341-hw2-lastname-firstname]. If you email me more than once, the last email I recieve BEFORE class at 9:30 am will be the one I will look at.
Turn in a printout of your .sml file, and a printout of your sml output, on hard copy at the beginning of class on Friday. The email address you used to email Sandra the file must be written clearly at the top, underneath your name. These printouts should match whatever you emailed to Sandra.

Exercises

For each of the following functions, do the following:
- Write the function's type, and types of all bound names inside the function. Briefly explain your reasoning, using a combination of English narrative* and type equation deduction in the style of Friday's lecture. Show your work.
  * E.g., "fun divide (x) = x / 3.0 is of type fn : real -> real, x must be a real since the / operator takes only arguments of type real, and the function returns a real because the return type of the / operator is a real."
- Give an example of one inputs you could give, its type, the output that would result, and its type. If the function has polymorphic type, give the instantiation that is necessary to make the application to your example input well-typed.
1. ```
fun hello(n) = n
```
2. ```
fun we (x,y,z) = {me = x::nil, you = y, them = (fn z => z ^ " who")};
```
3. ```
fun fire(a,b,c::d) = [a,b] :: c;
```
4. ```
fun foobar _ a b nil = {c=a::b, d=nil}
  | foobar p q r (x::xs) =
    let
        val s = p::xs
        val t = [r]
    in
        {c=s, d=t}
    end;
```
Briefly explain why this isn't properly tail recursive function. Then change the it into a tail-recursive function.
```
fun pow3 0 = 1
  | pow3 n = 3 * pow3(n-1);
```
Write tail call recursive functions for the following. If you need to write a helper function, be sure to put it in a let expression.
1. Takes an argument x of type real and n of type int and returns x^n (x to the n-th power).
2. Takes two arguments, a of type int and n of type int, and returns a list of n multiples of a in order from greatest to least. (If a is 3 and n is 4, your function returns 12::9::6::3).
3. Take a list of ints as an argument, returns the value of the largest element of that list
4. Write a function that returns a list of the first n Fibonacci numbers, in order from least to greatest. (Fibonacci numbers: 0, 1, 1, 2, 3, 5,... add the previous two numbers to get the next). UPDATE: You do not have to use foldl, as previous versions of this assignment demanded.
UPDATE: This question has been changed, to ask you to find 20 instead of 50 Fibonacci numbers; also, a fourth subquestion has been added..

Using the function you wrote above, find the first 20 Fibonacci numbers and do the following:
1. Use the standard library map function to get a list of the square of each of the Fibonacci numbers, (e.g. 0 1 1 4 9 25)
2. Use the standard library filter function to get a list of all the odd numbers of this these squared Fibonacci numbers.
3. Use the standard library find function to find the smallest squared Fibonacci number divisble by 5 and greater than 1000.
4. Use the standard library foldl function to compute, for each element e_i in a list, the cumulative sum of all elements e₁ through e_i in the list. The list of cumulative sums for each position should be returned. For example, given the list [1, 2, 4, 8], your function should return [1, 3, 7, 15] (because 3 = 1 + 2, 7 = 1 + 2 + 4, and 15 = 1 + 2 + 4 + 8).
Write a function that takes as arguments (1) a real list, and (2) a function from reals to reals, and return a list of tuples where the first element of the tuple is the corresponding element from the real list, and the second item of the tuple is the result of the function on that element. (e.g. if we passed a list [2.0,3.0], and a function that increments by one, to the function you write, your function should return [(2.0,3.0),(3.0,4.0)].)