(* 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? *)