2 Basic List Manipulations Problem 1 (5 points) Write an ML function, called alternate: 0a list ? 0a list ? 0a list, that takes two lists, having the same length, as input and produces an output list whose elements are alternately taken from the first and second input list respectively.

Example: alternate([1,3,5],[2,4,6]) = [1,2,3,4,5,6]

Problem 2 (5 points) Write an ML function, called minus: int list ? int list ? int list, that takes two non-decreasing integer lists and produces a non-decreasing integer list obtained by removing the elements from the first input list which are also found in the second input list.

For example, minus( [1,1,1,2,2], [1,1,2,3] ) = [1,2] minus( [1,1,2,3],[1,1,1,2,2] ) = [3]

Problem 3 (20 points) Write a function, called union: 00a list ? 00a list ? 00a list, that when called with two lists, denoting sets, returns their union. In other words, union(s1,s2) = s1 ? s2 where s1 and s2 are lists. Recall that sets may not contain duplicate elements. (Hence s1 ? s2 may not contain duplicate elements).

Problem 4 (20 points) Write a function, called multiSetIntersection: 00a list list ? 00a list, that when passed a list of sets (which are also represented as lists) as input will return their intersection as output.

For example, multiSetIntersection([s1,s2,s3,s4]) = s1 ? s2 ? s3 ? s4

multiSetIntersection( [] ) = []

Remark. An intersection of two sets is the set of all elements that are common to both sets. That is, an element x is a member of the intersection of S1 and S2, if and only if x is a member of S1 and x is a member of S2.

This can be formally expressed as follows: x ? (S1 ? S2) ? x ? S1 ? x ? S2

Problem 5 (10 points) The Cartesian product (or cross product) of two sets, S1 and S2, is often denoted by the symbol and is defined follows: S1 S2 = {(x, y) | x ? S1 ? y ? S2}. Using tuple and list notation, write a function called crossProduct: 0a list ? 0 b list ? ( 0a ? 0 b) list that takes two lists as input and returns their Cartesian product.

Problem 6 (20 points) The powerset of a set S is defined as the set of all subsets of S (including the empty set). For example, the powerset of {1, 2} is {{1, 2}, {1}, {2}, {}}. Write an SML function called powerset: 0a list ?0 a list list that when given a list representation of a set as input returns its powerset as output. 2

3 Representing Functions as Sets (or Lists) Any function from integers to integers can be expressed as a set of input-output pairs. Consider the function posIntegerSquare: pos integer ? pos integer, that takes a positive integer, x, as input and returns x ? x. Function represented as a computation. fun posIntegerSquare x = x*x Function represented as a set. val posIntegerSquare = [(1,1), (2,4), (3,9),...] The advantage of set representation is that, aside from the lookup operation, no calculations need to be performed in order to obtain the output value of the function. On the other hand, the disadvantage of the set representation is that, for most functions, the set of input-output pairs will be infinite. Thus, constructing such a list is not feasible.

Problem 7 (10 points) Write an SML function, called finiteListRepresentation: (int ? 0a) ? int ? (int ? 0a) list, that takes as input an arbitrary function f: int ? 0a, and a positive integer, n, and returns the list representation of f corresponding to the first n input-output pairs.

Example. finiteListRepresentation( posIntegerSquare, 5) = [ (1,1), (2,4), (3,9), (4,16), (5,25) ]

Remark. Note that in this problem, the output list denotes a set. Also note that in a set the order of elements is not important.

Problem 8 (10 points) Write an SML function, called update: ( 00a ? 0 b) list ? ( 00a ? 0 b) ? ( 00a ? 0 b) list, that takes a finite list representation of a function as a list of input-output pairs and returns an updated finite list representation.

For example, let (x, f(x)) denote an arbitrary input-output pair, and let F LR = [(x1, y1),(x2, y2), . . . ,(xn, yn)] denote an arbitrary finite list representation. If there exists a value for i such that 1 ? i ? n ? xi = x, then update(F LR,(x, f(x))) will cause the element (xi , yi) in F LR to be replaced with (x, f(x)). On the other hand, if there does not exist a value for i such that 1 ? i ? n ? xi = x, then the element (x, f(x)) should be added to F LR.

Let FLR = [(1,1),(2,4),(3,9),(4,16),(5,25)].

1. update(FLR, (2,3)) = [(1,1),(2,3),(3,9),(4,16),(5,25)]

2. update(FLR, (6,36)) = [(1,1),(2,4),(3,9),(4,16),(5,25),(6,36)]