CSCI305.github.io

CSCI 305 Programming Languages

ML Part 2

Reading: Webster Ch. 7

Instructions

1. Watch This Video - (23:22)
2. Watch This Video - (10:35)
3. Watch This Video - (18:35)
4. Review the Lecture Slides
5. Review the Example Code
6. Complete the Out of Class Exercise
7. Check Your Learning
8. Attend Class and Complete the In Class Exercises
9. Check Your Learning

Out of Class Exercise

Exercise 1:

Give a BNF grammar for the language ML patterns. Use the non-terminal symbol <pattern> as the start symbol. Use the non-terminal symbols <name> and <constant>, without defining productions for them, for the appropriate parts of the language.

Check Your Learning:

Solution:

<pattern> ::= <singular> | <tuple>
<singluar> ::= <list> | <name> | <constant> | <cons>
<tuple> ::= ( <tuple-list> )
<tuple-list> ::= <pattern> , <tuple-list> | <pattern>
<list> ::= [ <singular> ] | []
<cons> ::= <name> :: <cons-list> | <constant> :: <cons-list>
<cons-list> <name> | <constant> | <cons>

Exercise 2:

Define a function member of type ''a * ''a list -> bool so that member(e, L) is true if and only if e is an element of the list L.

Check Your Learning:

Solution:

fun member (_, []) = false
|   member (e, x::xs) =
      if e = x then true
      else member(e, xs);

(* Examples *)
member (1, [1,2,3,4]);
member (1, []);
member (1, [2,3,4]);

In Class Exercises

Exercise 1

Write a quicksort function of type in list -> int list. Here’s a review of the quicksort algorithm. First pick an element and call it the pivot. (The head of the list is an easy choice for the pivot.) Partition the rest of the list into two sublists, one with all the elements less than the pivot and another with all the elements not less than the pivot. Recursively sort the sublists. Combine the two sublists (and the pivot) into a final sorted list.

Check Your Learning:

Solution:

fun partition (pivot, nil) = (nil, nil)
|   partition (pivot, first::rest) =
      let
        val (small, large) = partition (pivot, rest)
      in
        if first < pivot
          then (first::small, large)
          else (small, first::large)
      end;

fun quickSort nil = nil
|   quickSort [single] = [single]
|   quickSort (first::rest) =
      let
        val (small, large) = partition(first, rest)
      in
        quickSort(small) @ [first] @ quickSort(large)
      end;

(* Example *)
quickSort [1, 4, 2, 7, 11, 8, 5]

Exercise 2

Make another version of your quicksort function, but this time of type 'a list * ('a * 'a -> bool) -> 'a list. The second parameters should be a function that performs the role of the < comparison in your original function. (Hint: This should only require minor changes to your previous quicksort definition).

Example functions:

fun icmp (a, b) = a < b;
fun rcmp (a : real, b) = a < b;

Check Your Learning:

Solution:

fun partition (pivot, nil, opLT) = (nil, nil)
|   partition (pivot, first::rest, opLT) =
      let
        val (small, large) = partition (pivot, rest, opLT)
      in
        if opLT (first, pivot)
          then (first::small, large)
          else (small, first::large)
      end;

fun quickSort (nil, opLT) = nil
|   quickSort ([single], opLT) = [single]
|   quickSort (first::rest, opLT) =
      let
        val (small, large) = partition(first, rest, opLT)
      in
        quickSort(small, opLT) @ [first] @ quickSort(large, opLT)
      end;

fun icmp (a, b) = a < b;
fun rcmp (a:real, b) = a < b;

(* Example *)
quickSort ([1, 4, 2, 7, 11, 8, 5], icmp)
quickSort [1.0, 4.5, 2.3, 7.0, 11.1, 8.2, 5.9] rcmp