2. The membership testing function, member, is described below:
fun member x [] = false
|member x (h::t) = (x=h) orelse (member x t);
(a) Define the functions below in standard ML:
add_new e S
(* add element e to the set S, so long as e is not already in S *)
delete e S
(* delete element e from the set S *)
intersection S1 S2
(* all elements that are common to S1 and S2 *)
subset S1 S2
(* true if all elements of S1 are in S2 *)
card S
(* cardinality of S, that is the number of elements in S *)
(10 marks)
(b) The Cartesian product of the sets S and T is the set of all pairs
(x,y) where x is in S and y is in T. For example, the Cartesian
product of the two sets S = [1,2,3] and T = ["a","b"] is the list
of pairs [(1,"a"),(1,"b"),(2,"a"),(2,"b"),(3,"a"),(3,"b")].
(i) Define in standard ML the function cartprod S T, where
cartprod delivers the Cartesian product of the sets S and T.
(ii) Explain, informally, how your function works.
(12 marks)
(c) The functions defined in (a) and (b) above are polymorphic, but
the functions in (a) will only operate over arguments that are
equality type variables (with the exception of card). Explain
what is meant by the term polymorphic and explain why the functions
cartprod, in (b) above, and card, in (a) above, do not require
equality type arguments.
(3 marks)