Simple functions for SML/NJ

Question

I was required to write a set of functions for problems in class. I think the way I wrote them was a bit more complicated than they needed to be. I had to implement all the functions myself, without using and pre-defined ones. I'd like to know if there are any quick any easy "one line" versions of these answers?

Sets can be represented as lists. The members of a set may appear in any order on the list, but there shouldn't be more than one occurrence of an element on the list.

(a) Define dif(A, B) to compute the set difference of A and B, A-B.

(b) Define cartesian(A, B) to compute the Cartesian product of set A and set B, { (a, b) | a∈A, b∈B }.

(c) Consider the mathematical-induction proof of the following: If a set A has n elements, then the powerset of A has 2n elements. Following the proof, define powerset(A) to compute the powerset of set A, { B | B ⊆ A }.

(d) Define a function which, given a set A and a natural number k, returns the set of all the subsets of A of size k.

(* Takes in an element and a list and compares to see if element is in list*)

fun helperMem(x,[]) = false
|   helperMem(x,n::y) =
      if x=n then true
      else helperMem(x,y);

(* Takes in two lists and gives back a single list containing unique elements of each*)

fun helperUnion([],y) = y
|   helperUnion(a::x,y) =
       if helperMem(a,y) then helperUnion(x,y)
       else a::helperUnion(x,y);

(* Takes in an element and a list. Attaches new element to list or list of lists*)
 fun helperAttach(a,[]) = []
  helperAttach(a,b::y) = helperUnion([a],b)::helperAttach(a,y);


  (* Problem 1-a *)
fun myDifference([],y) = []
 |   myDifference(a::x,y) = 
    if helper(a,y) then myDifference(x,y)
    else a::myDifference(x,y);

 (* Problem 1-b *)
 fun myCartesian(xs, ys) =
    let fun first(x,[]) = []
    |       first(x, y::ys) = (x,y)::first(x,ys)
        fun second([], ys) = []
    |       second(x::xs, ys) = first(x, ys) @ second(xs,ys)
    in      second(xs,ys) 
    end;


 (* Problem 1-c *)
 fun power([]) = [[]]
 |   power(a::y) = union(power(y),insert(a,power(y)));

I never got to problem 1-d, as these took me a while to get. Any suggestions on cutting these shorter? There was another problem that I didn't get, but I'd like to know how to solve it for future tests.

(staircase problem) You want to go up a staircase of n (>0) steps. At one time, you can go by one step, two steps, or three steps. But, for example, if there is one step left to go, you can go only by one step, not by two or three steps. How many different ways are there to go up the staircase? Solve this problem with sml. (a) Solve it recursively. (b) Solve it iteratively.

Any help on how to solve this?

Simon Shine Simon Shine · Accepted Answer · 2013-10-12T11:17:40

Your set functions seem nice. I would not change anything principal about them except perhaps their formatting and naming:

fun member (x, [])    = false
  | member (x, y::ys) = x = y orelse member (x, ys)

fun dif ([],   B) = []
  | dif (a::A, B) = if member (a, B) then dif (A, B) else a::dif(A, B)

fun union ([],   B) = B
  | union (a::A, B) = if member (a, B) then union (A, B) else a::union(A, B)

(* Your cartesian looks nice as it is. Here is how you could do it using map: *)
local val concat = List.concat
      val map = List.map
in fun cartesian (A, B) = concat (map (fn a => map (fn b => (a,b)) B) A) end

Your power is also very neat. If you call your function insert, it deserves a comment about inserting something into many lists. Perhaps insertEach or similar is a better name.

On your last task, since this is a counting problem, you don't need to generate the actual combinations of steps (e.g. as lists of steps), only count them. Using the recursive approach, try and write the base cases down as they are in the problem description.

I.e., make a function steps : int -> int where the number of ways to take 0, 1 and 2 steps are pre-calculated, but for n steps, n > 2, you know that there is a set of combinations of steps that begin with either 1, 2 or 3 steps plus the number combinations of taking n-1, n-2 and n-3 steps respectively.

Using the iterative approach, start from the bottom and use parameterised counting variables. (Sorry for the vague hint here.)

Simple functions for SML/NJ

1 Answers