Question

In this assignment you will practice using the pattern-matching constructs described in chapter 7 of your textbook to write several short SML functions. If at all possible, write all functions using pattern-matching constructs.  Include your name as a comment in the file, like this (* John Q Adams *).

• To reiterate - Use the pattern matching constructs described in chapter 7 to define your functions.
• Do the two steps below:
  • Download the following file to a folder. It contains dummy, hence incorrect, implementations of all functions described below. Your task is to provide the correct implementation for each function. You will be submitting only this file. See the next item for instructions on how to test your code.
  • Download the following file and use it for testing your code, like this: sml test_hw2.sml. It has 10 tests written for the various functions. When you submit your assignment, I will test the functions you write in the same way.
• Other cautions, caveats etc.
  • For each function that fails one or more tests, you lose 14 points.
  • If you are unable to write a particular function, leave the dummy definition for that function in your file so that the remaining tests can be executed.
  • You are expected to use good programming style, such as naming, indentation, and avoiding redundancy when possible. You should also place a descriptive comment on each of your functions.
  • If the solution to a previous problem is useful in helping you solve a later problem, you may call the earlier function from the later function. You are also allowed to define "helper" functions to solve these problems.
  • You are expected to write all the code you use in this assignment. You may not use any functions in any libraries (for example List.partition) with the exception of standard functions abs and length, if needed.
  • Note: As with the previous assignment, this assignment does not require a lot of code.

Functions to implement (first 4 are from Chapter 7 of your textbook):

1. Exercise 6. Follow the algorithm outlined in your textbook on page 116. The code follows a pattern similar to that of the mergesort function discussed in class. A helper function named partition does most of the work. Write your own partition function. You may not use any functions in any libraries (for example List.partition)
2. Exercise 8. Once again, write your own function from scratch. Do not use any membership testing functions in any libraries.
3. Exercise 9. Again, write your own function from scratch. Do not use any union computing functions in any libraries.
4. Exercise 10. Again, write your own function from scratch. Do not use any intersection computing functions in any libraries.
5. A range function similar to the range function in Python. For example, range (2,12,3) returns the list [2,5,8,11]
6. A slice function, with functionality similar to the Python list slice operator. For example, slice ([11,22,3,14,5,6], 1, 4) returns the list [22,3,14]

first download file contains this information:

(* #1 - quicksort *)
fun quicksort x:int list = nil;

(* #2 - member *)
fun member (e, s) = true;


(* #3 - returns the union of sets (lists) s1 and s2*)
(* You may assume that s1 and s2 do not have any duplicate elements *)
fun union (s1, s2) = nil;

(* #4 - returns the intersection of sets (lists) s1 and s2 *)
(* You may assume that s1 and s2 do not have any duplicate elements *)
fun intersection (s1, s2) = nil;

(* #5 - Return list of integers from start (inclusive) to stop (exclusive) by step *)
fun range(start, stop, step) = nil;

(* #6 - Return a slice of a list between indices start inclusive, and stop exclusive. Assume first element of list is at index 0*)
fun slice(aList, start, stop) = nil;

Second downloadable file contains this information:

(* Sort a list of integers. *)
fun myMergeSort nil = nil
| myMergeSort [e] = [e]
| myMergeSort theList =
let
(* From the given list make a pair of lists
* (x,y), where half the elements of the
* original are in x and half are in y. *)
fun halve nil = (nil, nil)
| halve [a] = ([a], nil)
| halve (a::b::cs) =
let
val (x, y) = halve cs
in
(a::x, b::y)
end;
(* Merge two sorted lists of integers into
* a single sorted list. *)
fun merge (nil, ys) = ys
| merge (xs, nil) = xs
| merge (x::xs, y::ys) =
if (x < y) then x :: merge(xs, y::ys)
else y :: merge(x::xs, ys);
val (x, y) = halve theList
in
merge(myMergeSort x, myMergeSort y)
end;

fun pass_fail x = if x then "Pass" else "\t\tFail";

fun test(function, input, expected_output) = pass_fail (function(input) = expected_output);

fun test_set(function, input, expected_output) = pass_fail (myMergeSort(function(input)) = expected_output);

print("*********TEST RESULTS******************\n");
print("\n1.Quicksort "^test(quicksort, [1,3,2,5,4,8,7,9,0], [0,1,2,3,4,5,7,8,9])^"\n");
print("\n2.Quicksort "^test(quicksort, [1,3,2,5,4,2, 8,6,7,9,0], [0,1,2,2,3,4,5,6,7,8,9])^"\n");
print("\n3.Member "^test(member, (2,[1,3,2,5,4,2, 8,6,7,9,0]), true)^"\n");
print("\n4.Member "^test(member, (12,[1,3,2,5,4,2, 8,6,7,9,0]), false)^"\n");
print("\n5.Union "^test_set(union, ([1,3,2,5], [0,1,2,33]),[0,1,2,3,5,33])^"\n");
print("\n6.Union "^test_set(union, ([1,3,2,5], [5,2,3,1]),[1,2,3,5])^"\n");
print("\n7.Union "^test_set(union, ([1,3,2,5], []),[1,2,3,5])^"\n");
print("\n8.intersection "^test_set(intersection, ([1,3,22,5], [5,12,3,1]),[1,3,5])^"\n");
print("\n9.intersection "^test_set(intersection, ([1,3,2,5], [15,12,13,11]),[])^"\n");
print("\n10.intersection "^test_set(intersection, ([1,3,2,5], [5,2,3,1]),[1,2,3,5])^"\n");
print("\n11.Range "^test(range, (2,12,3), [2,5,8,11])^"\n");
print("\n12.Range "^test(range, (12,34,5), [12,17,22,27,32])^"\n");
print("\n13.Range "^test(range, (10,2,~1), [10,9,8,7,6,5,4,3])^"\n");
print("\n14.Slice "^test(slice, (range(2,20,2),2,7), [6,8,10,12,14])^"\n");
print("\n15.Slice "^test(slice, (range(1,100,4),3,12), [13, 17, 21, 25, 29, 33, 37, 41, 45])^"\n");

Answer 1

Due to time constraint i cannot solve the range and slice functions...please write them...i think theyre easy

(* #1 - quicksort *)
fun par_helper([], x, l, r) = (l, r) 
  | par_helper(h::t, x, l, r) = 
                if h <= x then 
                        par_helper(t, x, l @ [h], r)
                else
                        par_helper(t, x, l, r @ [h]);
 
fun par(l, x) = par_helper(l, x, [], []);
 
fun quicksort [] = []
  | quicksort (h::t) =
    let 
        val (left, right) = par(t, h)
    in
        quicksort left @ [h] @ quicksort right
    end;


(* #2 - member *)
fun member (x, nil) = false | member (x, y::ys) = x=y orelse member (x,ys);



(* #3 - returns the union of sets (lists) s1 and s2*)
(* You may assume that s1 and s2 do not have any duplicate elements *)
fun union([],y) = y
|   union(a::x,y) =
       if member(a,y) then union(x,y)
       else a::union(x,y);




(* #4 - returns the intersection of sets (lists) s1 and s2 *)
(* You may assume that s1 and s2 do not have any duplicate elements *)
fun intersection([],y) = []
 |   intersection(a::x,y) =
       if member(a,y) then a::intersection(x,y)
       else intersection(x,y);

(* #5 - Return list of integers from start (inclusive) to stop (exclusive) by step *)
fun range (start, stop , step) = nil

(* #6 - Return a slice of a list between indices start inclusive, and stop exclusive. Assume first element of list is at index 0*)
fun slice(aList, start, stop) = nil;

(* Sort a list of integers. *)
fun myMergeSort nil = nil
| myMergeSort [e] = [e]
| myMergeSort theList =
let
(* From the given list make a pair of lists
* (x,y), where half the elements of the
* original are in x and half are in y. *)
fun halve nil = (nil, nil)
| halve [a] = ([a], nil)
| halve (a::b::cs) =
let
val (x, y) = halve cs
in
(a::x, b::y)
end;
(* Merge two sorted lists of integers into
* a single sorted list. *)
fun merge (nil, ys) = ys
| merge (xs, nil) = xs
| merge (x::xs, y::ys) =
if (x < y) then x :: merge(xs, y::ys)
else y :: merge(x::xs, ys);
val (x, y) = halve theList
in
merge(myMergeSort x, myMergeSort y)
end;

fun pass_fail x = if x then "Pass" else "\t\tFail";

fun test(function, input, expected_output) = pass_fail (function(input) = expected_output);

fun test_set(function, input, expected_output) = pass_fail (myMergeSort(function(input)) = expected_output);

print("*********TEST RESULTS******************\n");
print("\n1.Quicksort "^test(quicksort, [1,3,2,5,4,8,7,9,0], [0,1,2,3,4,5,7,8,9])^"\n");
print("\n2.Quicksort "^test(quicksort, [1,3,2,5,4,2, 8,6,7,9,0], [0,1,2,2,3,4,5,6,7,8,9])^"\n");
print("\n3.Member "^test(member, (2,[1,3,2,5,4,2, 8,6,7,9,0]), true)^"\n");
print("\n4.Member "^test(member, (12,[1,3,2,5,4,2, 8,6,7,9,0]), false)^"\n");
print("\n5.Union "^test_set(union, ([1,3,2,5], [0,1,2,33]),[0,1,2,3,5,33])^"\n");
print("\n6.Union "^test_set(union, ([1,3,2,5], [5,2,3,1]),[1,2,3,5])^"\n");
print("\n7.Union "^test_set(union, ([1,3,2,5], []),[1,2,3,5])^"\n");
print("\n8.intersection "^test_set(intersection, ([1,3,22,5], [5,12,3,1]),[1,3,5])^"\n");
print("\n9.intersection "^test_set(intersection, ([1,3,2,5], [15,12,13,11]),[])^"\n");
print("\n10.intersection "^test_set(intersection, ([1,3,2,5], [5,2,3,1]),[1,2,3,5])^"\n");
print("\n11.Range "^test(range, (2,12,3), [2,5,8,11])^"\n");
print("\n12.Range "^test(range, (12,34,5), [12,17,22,27,32])^"\n");
print("\n13.Range "^test(range, (10,2,~1), [10,9,8,7,6,5,4,3])^"\n");
print("\n14.Slice "^test(slice, (range(2,20,2),2,7), [6,8,10,12,14])^"\n");
print("\n15.Slice "^test(slice, (range(1,100,4),3,12), [13, 17, 21, 25, 29, 33, 37, 41, 45])^"\n");
(* #1 - quicksort *)
fun par_helper([], x, l, r) = (l, r) 
  | par_helper(h::t, x, l, r) = 
                if h <= x then 
                        par_helper(t, x, l @ [h], r)
                else
                        par_helper(t, x, l, r @ [h]);
 
fun par(l, x) = par_helper(l, x, [], []);
 
fun quicksort [] = []
  | quicksort (h::t) =
    let 
        val (left, right) = par(t, h)
    in
        quicksort left @ [h] @ quicksort right
    end;


(* #2 - member *)
fun member (x, nil) = false | member (x, y::ys) = x=y orelse member (x,ys);



(* #3 - returns the union of sets (lists) s1 and s2*)
(* You may assume that s1 and s2 do not have any duplicate elements *)
fun union([],y) = y
|   union(a::x,y) =
       if member(a,y) then union(x,y)
       else a::union(x,y);




(* #4 - returns the intersection of sets (lists) s1 and s2 *)
(* You may assume that s1 and s2 do not have any duplicate elements *)
fun intersection([],y) = []
 |   intersection(a::x,y) =
       if member(a,y) then a::intersection(x,y)
       else intersection(x,y);

(* #5 - Return list of integers from start (inclusive) to stop (exclusive) by step *)
fun range (start, stop , step) = nil

(* #6 - Return a slice of a list between indices start inclusive, and stop exclusive. Assume first element of list is at index 0*)
fun slice(aList, start, stop) = nil;

(* Sort a list of integers. *)
fun myMergeSort nil = nil
| myMergeSort [e] = [e]
| myMergeSort theList =
let
(* From the given list make a pair of lists
* (x,y), where half the elements of the
* original are in x and half are in y. *)
fun halve nil = (nil, nil)
| halve [a] = ([a], nil)
| halve (a::b::cs) =
let
val (x, y) = halve cs
in
(a::x, b::y)
end;
(* Merge two sorted lists of integers into
* a single sorted list. *)
fun merge (nil, ys) = ys
| merge (xs, nil) = xs
| merge (x::xs, y::ys) =
if (x < y) then x :: merge(xs, y::ys)
else y :: merge(x::xs, ys);
val (x, y) = halve theList
in
merge(myMergeSort x, myMergeSort y)
end;

fun pass_fail x = if x then "Pass" else "\t\tFail";

fun test(function, input, expected_output) = pass_fail (function(input) = expected_output);

fun test_set(function, input, expected_output) = pass_fail (myMergeSort(function(input)) = expected_output);

print("*********TEST RESULTS******************\n");
print("\n1.Quicksort "^test(quicksort, [1,3,2,5,4,8,7,9,0], [0,1,2,3,4,5,7,8,9])^"\n");
print("\n2.Quicksort "^test(quicksort, [1,3,2,5,4,2, 8,6,7,9,0], [0,1,2,2,3,4,5,6,7,8,9])^"\n");
print("\n3.Member "^test(member, (2,[1,3,2,5,4,2, 8,6,7,9,0]), true)^"\n");
print("\n4.Member "^test(member, (12,[1,3,2,5,4,2, 8,6,7,9,0]), false)^"\n");
print("\n5.Union "^test_set(union, ([1,3,2,5], [0,1,2,33]),[0,1,2,3,5,33])^"\n");
print("\n6.Union "^test_set(union, ([1,3,2,5], [5,2,3,1]),[1,2,3,5])^"\n");
print("\n7.Union "^test_set(union, ([1,3,2,5], []),[1,2,3,5])^"\n");
print("\n8.intersection "^test_set(intersection, ([1,3,22,5], [5,12,3,1]),[1,3,5])^"\n");
print("\n9.intersection "^test_set(intersection, ([1,3,2,5], [15,12,13,11]),[])^"\n");
print("\n10.intersection "^test_set(intersection, ([1,3,2,5], [5,2,3,1]),[1,2,3,5])^"\n");
print("\n11.Range "^test(range, (2,12,3), [2,5,8,11])^"\n");
print("\n12.Range "^test(range, (12,34,5), [12,17,22,27,32])^"\n");
print("\n13.Range "^test(range, (10,2,~1), [10,9,8,7,6,5,4,3])^"\n");
print("\n14.Slice "^test(slice, (range(2,20,2),2,7), [6,8,10,12,14])^"\n");
print("\n15.Slice "^test(slice, (range(1,100,4),3,12), [13, 17, 21, 25, 29, 33, 37, 41, 45])^"\n");