Programming Assignment #2
ML Assignment

Due by Noon on March 31, 2009.

Part 0: Download and Install ML

Before you begin the assignment, you must install ML.  The version of ML that we will use for this assignment is Standard ML of New Jersey.  You should be able to find a binary for your system from this page.  Once you download and decompress the file, add the location of sml.exe to your path.  Now you should be able to run ML by simply typing "sml" from the command prompt.

Please download and install ML, as soon as possible, to avoid problems and stress closer to the due date.

Part 1:  Simulating a Deterministic Finite Automaton (45 points)

In this part, you will reimplement the DFA simulator, from Chapter 10 in the Scott's book, in ML.   The original code is written in Scheme and can be found on page 538 in Figure 10.1.   Your main function should be named simulate and take as arguments the list structure containing the DFA and an input list.  The following is an example of a call to simulate and the corresponding output:

         [(("q0", 0), "q2"), (("q0", 1), "q1"), (("q1", 0), "q3"), (("q1", 1), "q0"),
         (("q2", 0), "q0"), (("q2", 1), "q3"), (("q3", 0), "q1"), (("q3", 1), "q2")],
         [0, 1, 1, 0, 1]
=> val it = ["q0", "q2", "q3", "q2", "q0", "q1", "reject"] : string list

Part 2:  The Greedy Grocery Store Clerk (40 points)

A grocery store clerk has a line forming in their check-out aisle.  The clerk is very slow and knows that people will leave before the clerk can check-out every customer's order.  Therefore, since the clerk is greedy, the customers are asked to reform the line in decreasing order of their total purchases.  The clerk can serve them in this order to maximize total sales.  Your job is to write ML code to total each customer's purchase and sort the line.

Assume you are given a list of customers and their purchases in the following form:

[(customer_name1, [(num_items1, cost_of_item1),(num_items2, cost_of_item2),...])
(customer_name2, [(num_items1, cost_of_item1),....])
(customer_name_n, [(num_items1, cost_of_item1),...])

The interpretation is that customer_name1 has num_items1 of the first item at cost_of_item1 dollars for each item.  Your code should total the items in the customer's cart.  That is, the total amount in the first customer's cart is:
 (num_items1 * cost_of_item1) + (num_items2 * cost_of_item2) + ....
You should call your function grocery_store_line; the function should take the customer-item list as an argument.  Your sorting algorithm should be based on a quicksort algorithm.  The following is an example of a call to grocery_store_line and the corresponding output:

grocery_store_line [
              ("rebecca", [(3, 2.25), (10, 6.7), (2, 3.2)]),
              ("gene", [(8, 0.2), (3, 0.25), (15, 0.15)]),
              ("albert", [(1, 100.30)])

=>val it = [("albert",100.3),("rebecca",80.15),("gene",4.6)] : (string * real) list

Note the steps of the Quicksort algorithm (sorting least to greatest--the other way 'round is symmetrical):
1. If the list is empty or contains a single element it is sorted and no further action is required.
2. Otherwise, choose an element from the list to be the "pivot"
3. Create two sub-lists, one containing all elements less than the pivot and one containing all elements greater than the pivot.
4. Sort the two sub-lists recursively.
5. The sorted list is composed of a.) the sorted sub-list of elements less than the pivot, followed by b.) the pivot element itself, followed by c.) the sorted sub-list of elements greater than the pivot.

After we go over the algorithm in class, you should see me on office hours if you still have questions. I'll be happy to go over some examples with you.

Write-up and Questions (15 Points):

Describe, for both Parts 1 and 2, the functions you created to complete the task.  Briefly describe your reason for the way you structure the solution for each part.  In addition, answer the following questions:
1. What is the type of the simulate function from Part 1?
2. What is the type of the grocery_store_line function from Part 2?
3. In words, describe what changes you would need to make to the simulate function to handle nondeterministic finite automatons (NFAs).  Your description can be high-level.

What to Hand-in

Send me an email with a zip file containing code files for each Part 1 and 2, and your write-up. Title the email "COMP524 Program2" and call the attached zip file

• Use Professor Stotts' ML Notes;
• Think recursively, and use ML's pattern matching functionality to make things easy;
• Understand the let construct, and built-in functions such as map.
• To convert from int to real, use the real() function
• You need not type the while program at the interpreter each time you want to run it. Simple create a text file with your program in it... use whatever editor you like to write the program. Let's say I have my program in a file called Then when I run the interpreter I type this:
use "";


Your assignment will be graded not only on the ability to be correctly interpreted and produce the correct output, but also on the correct and efficient use of language constructs provided by ML such as
recursion, pattern matching, anonymous functions, and lists.  For instance, you should attempt to only use the functional language constructs.  I will grade both the quality of the source code, comments (on nearly every line for this assignment!), and the output. Collaboration is not allowed on this assignment; you may discuss the ML language but not approaches (or code) for the assignment. Also, you may not use outside resources such as the Internet, other then the online materials I have linked to here. See me during office hours if you need additional help. The Honor Code applies to this program. Please, read
for more details.