Description
Question 1. [20 points] Write an Sml function that takes two integers in succession and
returns the stream that gives the infinite decimal expansion of the number. Of course, often
the decimal expansion terminates after a finite number of steps. In that case, I want the
stream to end with an infinite sequence of zeros. Here is the type and two examples.
val infiniteDecimal = fn : int -> int -> int str
– val oneHalf = infiniteDecimal 1 2;
val oneHalf = Str {hd=0,tl=Susp fn} : int str
– take 5 oneHalf;
val it = [0,5,0,0,0] : int list
– take 10 threeSeventh;
val it = [0,4,2,8,5,7,1,4,2,8] : int list
Question 2. [30 points] Write an Sml version of the sieve of Erasthosthenes. You will need
filter and some other utilities. I will put the code you need on the web site. Please submit
your code together with the code I provide so that we can run your program. If you just
submit the code you wrote I will give you zero.
val primes = Str {hd=2,tl=Susp fn} : int str
printIntStr primes 25;
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
1
Question 3. [25 points] What is the result of evaluating the following expression? Explain
your answer drawing the relevant environment diagrams. This expression just returns a
unit type, however, I want to know what is printed on the screen. I am not interested
in extraneous things like val it = () : unit. I am interested in what the three print
statements produce.
let val x = ref 1 in
let val y = x in
let fun f u = ((u := (!u) + 1); (!u + !x)) in
(print(“x is “^Int.toString(!x)^”; “));
(print(“f(y) is “^Int.toString(f(y))^”; “));
(print(“x is “^Int.toString(!x)^”. “))
end
end
end
Question 4. [25 points] Informally derive the most general type for the following function. I will give you zero if you instantiate everything to, for example, int, or some other
monomorphic type.
fun tricomp f g h = fn x => (f (g (h x)))
2