Overview

Patterns are a model of something; in our day-to-day experiences, we tend to categorize things by how closely they match some pattern. For example, we enter a classroom and automatically categorize the furniture based on our pattern of chairs and tables. This ability to recognize patterns and form categories allows us to more rapidly make sense of our world. We enter a new classroom and instantaneously we categorize students and chairs correctly, seldom do we mistake a chair for a student.

Programming patterns take advantage of this natural ability to recognize patterns in problems. We use patterns in problem solving in at least two ways: by grouping together distinct cases of a problem, and by abstracting (i.e. reducing) a large number of specific cases to a few general cases. By organizing problems by patterns, our understanding of the problem is generally clearer, the solution simpler and, therefore, more likely to be correct. For an example of abstraction, we could define the positive integer successor for each specific integer case by:

fun successor0 = 1;
fun successor1 = 2;
fun successor2 = 3;
         :

or in general by:

fun successor n = n+1;

ML further uses our pattern recognition and categorization ability by decomposing a single solution (e.g. function) into separate cases or categories of solutions. The ML pattern syntax is generally an alternative to if-then-else statements, something akin to the switch statement in C or Java. For example, the summation of an integer list of numbers can be defined using patterns, where each patterns solve one specific case of the summation problem. A pattern and non-pattern solution is given below:

fun sum L =       if null L then 0       else if null (tl L) then hd L             else (hd L) + sum (tl L);

fun sum [] = 0 |    sum [a] = a |    sum (h::t) = h + sum t;

The non-pattern solution at left requires that we first read the code to form categories in our mind to understand to the solution. The pattern solution at right defines and organizes the categories visually, avoiding extra effort and reducing the potential for our misunderstanding the solution.

Assignment

Write and give output from TESTING for the following:

1. Following the example of the text function halve define the function third that divides a list into a tuple of three lists.
           third [1,2,3,1,2,3,1,2,3];
           val it = ([1, 1, 1], [2, 2, 2], [3, 3, 3]) : int list * int list * int list
   
   
2. Define the functional dup so that dup (f, x) is f (f x). 
           dup (tl, [1,2,3]) 
           val it = [3] : int list
           
           fun inc x = x + 1;
   
           dup (inc, 5);
           val it = 7 : int
   
   
3. Define the functional comp so that comp(f,g,x) is g(f x).
           comp(inc,inc,5);
           val it = 7 : int
   
           fun above10 x = x > 10;
           above10 14;
           val it = true : bool
   
           comp(inc,above10, 10);
           val it = true : bool
   
   
4. Define a function sqlist to square every element of a given list using sq and the map functional where fun sq x = x * x;  Warning: be consistent on the use of parameters as tuples or multiple parameters, that is map sq [1,2,3] vs map (sq, [1,2,3]); .
           sqlist [1,2,3,4];
           val it = [1, 4, 9, 16] : int list
   
   
5. Define a function vecadd to add two integer lists using map2 and add where fun add x y = x + y;
           vecadd [1,2,3]  [4,5,6];
            val it = [5, 7, 9] : int list
           
6. Define a function matadd to add two integer matrices using vecadd for vector addition and map2 for recursion. Be consistent on use of tuples or multiple parameters. matadd is a one line function.
           matadd [[1,2],[3,4]] [[5,6],[7,8]];
           val it = [[6, 8], [10, 12]] : int list list
   
   
7. Define a function ip to compute the inner product of two lists using map2 and reduce. The inner product is the sum of the products of multiplying two lists. In the class notes we defined a function such that reduce add 0 [1,2,3] is 6 and map2 mul [1,2,3] [4,5,6]  is [4,10,18].  ip is a one line function. 
           ip ([1,2,3], [1,2,3]);
           val it = 14 : int

Turn In

1. Cover sheet with your name, date, and Homework 2.
2. Print out of each of Assignment 1-7 function definitions.
3. Print out of each of Assignment 1-7 interactions containing the evaluation results of all the functions using the given test examples.

Document last modified: