CSCI305.github.io

CSCI 305 Programming Languages

ML Part 4

Reading: Webster Ch. 11

Instructions

1. Watch This Video - (17:20)
2. Watch This Video - (39:33)
3. Watch This Video - (7:23)
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

Write a datatype definition for a type suit whose values are the four suits of a deck of playing cards. Then using this definition, write a function suitname of type suit -> string that returns a string giving the name of a suit.

Check Your Learning:

Solution:

datatype 'data suit = SPADES | HEARTS | DIAMONDS | CLUBS;

fun suitname SPADES = "spades"
|   suitname HEARTS = "hearts"
|   suitname DIAMODNS = "diamonds"
|   suitname CLUBS = "clubs";

Exercise 2

Using the following definition of a tree. Write a function isComplete of type 'a tree -> bool that tests whether a tree is complete. Note: a complete binary tree is one in which every Node has either two Empty children or two Node children, but not one of each.

datatype 'data tree =
   Empty |
   Node of 'data tree * 'data * 'data tree;

Check Your Learning:

Solution:

datatype 'data tree =
   Empty |
   Node of 'data tree * 'data * 'data tree;

fun isComplete Node(Empty _ Empty) = true
|   isComplete Empty = true
|   isComplete Node(x _ Empty) = false
|   isComplete Node(Empty _ x) = false
|   isComplete Node(left _ right) =
      isComplete left andalso isComplete right;

In Class Exercises

Exercise 1

A Binary Search Tree is a binary tree with special properties. It may be Empty. It may be a Node containing a left subtree, a data item x, and a right subtree. In this case all the data items in the tree are different, all the items in the left subtree are smaller than x, all the items in the right subtree are greater than x, and the left and right subtrees are also binary search trees. Write a function makeBST of type 'a list -> ('a * 'a -> bool) -> 'a tree that organizes the items in the list into a binary search tree. The tree need not be balanced. You may assume that no item in the list is repeated. You may want to start with the tree data type definition:

datatype 'data tree =
   Empty |
   Node of 'data tree * 'data * 'data tree;

Check Your Learning:

Solution:

datatype 'data tree =
        Empty |
        Node of 'data tree * 'data * 'data tree;

fun makeBST [] p = Empty
|   makeBST (z::zs) p =
        let
          fun insert Empty value = Node(Empty, value, Empty)
          |   insert (Node(left, x, right)) value =
                  if p(x, value) then Node((insert left value), x, right)
                  else Node(left, x, (insert right value))

          val y = makeBST zs p
        in
          insert y z
        end;

Exercise 2

Write a function searchBST of type ''a tree -> (''a * ''a -> bool) -> ''a -> bool that searches a binary search tree for a given data element. You should not search every node in the tree, but only those nodes that, according to the definition, might contain the element you are looking for.

Check Your Learning:

Solution:

fun searchBST Empty p value = false
|   searchBST (Node(left, x, right)) p value =
      if p(x, value) then searchBST left p value
      else if p(value, x) then searchBST right p value
      else true;