(* ML-programming H20 *)
(* Exercise 1 Write the function
fun rep(v, n) = ...;
that creates a list with n
occurrences of v
. The function should work for arguments of any type.
Example:
- rep (17, 4);
val it = [17,17,17,17] : int list
- rep ("a", 5);
val it = ["a","a","a","a","a"] : string list
- rep ([1,2,3], 3);
val it = [[1,2,3],[1,2,3],[1,2,3]] : int list list
*)
(* Exercise 2 Write the function
fun mulall(v, l) = ...;
that multiplies all elements in l
with the integer v
.
NB! Your solution should use the map
-function!
Example:
- mulall(~1, [2, 4, ~7, 10]);
val it = [~2,~4,7,~10] : int list
*)
(* Exercise 3
Use the function mulall
to define the function
fun powlist(x, n) = ...;
that returns a list with the exponentiations x^n, x^(n-1), ... x, 1
(where ^
denotes "to the power of" ).
Example:
- powlist(3, 6);
val it = [729,243,81,27,9,3,1] : int list
*)
(* Exercise 4
We want to create a function mullist
, that sums up the product of two lists (which we assume to be non-empty and equally long).
Example:
- mullist([1, 0, ~1], [3, 4, 5]);
val it = ~2 : int
- mullist([1, 2, 3, 4], [1, 2, 3, 4]);
val it = 30 : int
(which is 13 + 04 + ~15 = ~2 and 11 + 22 + 33 + 4*4 = 30).
The exercise should be solved in the following manner:
a) Create a function pair
which builds a list of tuples (pairs) from the two lists:
- pair([1, 0, ~1], [3, 4, 5]);
val it = [(1,3),(0,4),(~1,5)] : (int * int) list
- pair([1, 2, 3, 4], [1, 2, 3, 4]);
val it = [(1,1),(2,2),(3,3),(4,4)] : (int * int) list
b) Multiply the pairs by using map
on the list.
c) Sum up the answer by using a fold
on the list.
(See the "Note on functionals" for information about the fold functionals.)
d) Is your solution to (c) tail-recursive or not, and why? *)
(* Exercise 5
Assume that a polynomial is represented by a list such that
[3, ~2, 0, 1]
is the polynomial 3x^3 - 2x^2 + 1.
Write the function
fun poly (x, p) = ... ;
that computes the polynomial p
for the given x
.
Example:
- val p = [3, ~2, 0, 1];
val p = [3,~2,0,1] : int list
- poly(2, p);
val it = 17 : int
- poly(~1, p);
val it = ~4 : int
Hint: Use the functions mullist
and powlist
from previous exercises.
*)
(* Exercise 6
Given the following definition of the function repeat
fun repeat(f,d,l) =
case l of [] => d
| x :: l' => f(x,repeat(f,d,l'));
where d
designates a "default"-value.
If we have a function:
fun minus (x:int, y:int) = x-y;
then
repeat(minus, 0, [1,2,3]);
will compute (1-(2-(3-0))) which gives the answer 2.
Write a repeat
-like function that computes (((1-2)-3)-0) which should
give the result -4. *)
(* Exercise 7 -- excursion into OO-land
Define a (Java) class hierarchy for lists: there should be an abstract superclass
called List
with an abstract method
int length().
Give the two subclasses of List, one that represents the empty list named Nil
,
and one that represents the "cons" operation that we have seen in ML which takes
a value and another object of type List
in its constructor. Implement the
abstract method in both subclasses. We have seen in ML that lists are
polymorphic -- is your implementation? How did you treat the type of the list
elements? Is your list homogeneous or heterogeneous (all elements must have the
same type/can have different types?
*)
(* Exercise 8
Recall the definition of our binary tree from the lecture:
datatype tree = Leaf of int | Node of int*tree*tree;
In an object-oriented model, we would probably choose the following Java solution (although this yields three Java-types, instead of only one type in SML). Assume that in addition, we also introduce another subclass TeaLeaf
:
abstract class Tree { abstract int sum(); }
class Leaf extends Tree { Leaf(int i) { .. }}
class Node extends Tree { Node(int i, Tree t1, Tree t2) { .. }}
class TeaLeaf extends Leaf { (* not relevant *) }
How do you achieve the same effect in SML datatype? *)