Please make sure that your source code can be compiled and executed under Standard ML on Unix. For a brief explanation on how to run SML and how to load and execute programs, see http://www.cse.psu.edu/~catuscia/teaching/sml/sml.html

1. [Points 10] Define the function curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c such that, given a function f : 'a * 'b -> 'c, curry f gives the curried version of f, i.e. a function such that, for every x:'a and y:'b, (curry f) x y = f(x,y).

---

2. [Points 20] Define a function filter : ('a -> bool) -> 'a list -> 'a list such that, given a property (i.e. a predicate) p : 'a -> bool, and a list L : 'a list, filter p L returns the list of all elements of L which satisfy the property p.

   The following examples illustrate how filter should work:

   - fun positive x = x>0;
   val positive = fn : int -> bool
   - filter positive [];
   val it = [] : int list
   - filter positive [1];
   val it = [1] : int list
   - filter positive [1,~2,3,~4];
   val it = [1,3] : int list
   
   - fun first_is_a (x,y) = if x="a" then true else false;
   val first_is_a = fn : string * 'a -> bool
   - filter first_is_a [("a",1),("b",2),("a",3)] (* filters the pairs whose first element is an "a" *);
   val it = [("a",1),("a",3)] : (string * int) list
   
   -  filter (fn l=> not(l=[])) [[1],[],[1,2],[]] (* filters the lists which are not empty *);
   val it = [[1],[1,2]] : int list list
   

---

3. [Points 40] Consider the function reduce : (int * 'a -> 'a) -> 'a -> int list -> 'a defined as

      fun reduce f v [] = v
        | reduce f v ((x:int)::l) = f(x, reduce f v l);
   

   The function reduce works in the following way: given a function f : int * 'a -> 'a, an initial value v:'a, and a list of integers, the result is v if the list is empty, and otherwise the result is obtained by applying f to the first element and to the result obtained (by calling the function recursively) on the rest of the list (see also page 356 in Sethi).

   reduce represents a general algorithm on lists, which works by scanning the list (recursively) element by element, and performing a certain operation on every element (and on the result of the recursive call), and giving at the end a global result.

   For instance, we can define the functions sum_all : int list -> int and product_all : int list -> int (respectively sum and product of all the elements in a list of integers) as follows:

      val sum_all = reduce sum 0;
      val product_all = reduce times 1;
   

   where we assume that plus and times have been previously defined as the binary operations of sum and product on integers. (Alternatively, we can use (op +) and (op * ) ).

   Note that these are definitions of functions. We can apply them to lists of integers, as illustrated in the following examples:

      - sum_all [];         
      val it = 0 : int
      - sum_all [0];
      val it = 0 : int
      - sum_all [0,1,2];
      val it = 3 : int
      - sum_all [1,2,3,4];
      val it = 10 : int
   
      - product_all [];  
      val it = 1 : int
      - product_all [0];
      val it = 0 : int
      - product_all [0,1,2];
      val it = 0 : int
      - product_all [1,2,3,4];
      val it = 24 : int
   

1. Define the function length : int list -> int (length of a list) in terms of reduce, with a definition of the form:

      val length = reduce ... ; 
   

   (fill in the dots). You can use an auxiliary function if you want.

   The following examples illustrate how length should work:

   - length [];
   val it = 0 : int
   - length [0]; 
   val it = 1 : int
   - length [0,3,2,5];
   val it = 4 : int
   

2. Define the function maximum_positive : int list -> int. This function should return the maximum positive element of a list of integers, and 0 if all the elements are negative (or if the list is empty). The definition should be given in terms of reduce, as follows:

      val maximum_positive = reduce ... ; 
   

   (fill in the dots). You can use an auxiliary function if you want.

   The following examples illustrate how maximum_positive should work:

   - maximum_positive [];
   val it = 0 : int
   - maximum_positive [~1];  
   val it = 0 : int
   - maximum_positive [2,4,~5,3];
   val it = 4 : int
   

3. Define the function reverse : int list -> int list (reverse of a list of integers) in terms of reduce, as follows:

      val reverse = reduce ... ; 
   

   (fill in the dots). You can use an auxiliary function if you want.

   The following examples illustrate how reverse should work:

   - reverse [];
   val it = [] : int list
   - reverse [1,2];
   val it = [2,1] : int list
   - reverse [1,3,2];
   val it = [2,3,1] : int list
   

4. Define the function occurs : int -> int list -> bool (which checks whether a given integer occurs in a list of integers) in terms of reduce, as follows:

      fun occurs x = reduce ... ; 
   

   (fill in the dots). You can use an auxiliary function if you want.

   The following examples illustrate how occurs should work:

   - occurs 1 [];
   val it = false : bool
   - occurs 1 [0];
   val it = false : bool
   - occurs 1 [1,2];
   val it = true : bool
   - occurs 1 [2,1,3];
   val it = true : bool
   

---

4. [Points 30] Define in ML three functions f, g and h having the following types:

      f : 'a -> 'b -> 'a * 'b
      g : ('a * 'a -> 'b) -> 'a -> 'b
      h : ('a -> 'b) -> 'a list -> 'b list
   

   Any solution wich gives the requested types is fine; it is not required to define "meaningful" functions.