CMSC 15100: Homework 3

Homework 3 is due Monday, October 16, 2017 at 11:59pm.

As before, you will submit your work with filename hw3.rkt in a directory called hw3. The following commands, when run from within a copy of your repository, will get you started.

$ svn update
$ svn mkdir hw3
$ cd hw3
$ touch hw3.rkt
$ svn add hw3.rkt
$ cd ..
$ svn commit hw3 -m "preparing hw3"

After having done this, work in the file hw3/hw3.rkt

Starting with the last homework, continuing into this one, and persisting for the rest of the quarter, you should check for bogus inputs and raise an error if you receive one.

Preliminaries

(Same as last week.)

At the top of your hw3.rkt file, write this line to designate Typed Racket as the current language:

#lang typed/racket

Then, add the following lines:

(require typed/test-engine/racket-tests)
(require "../include/cs151-core.rkt")

At the bottom of the file, call the test function (with no arguments) to run the check tests:

(test)

This function call — (test) — should remain as the last line of your program even as you are working on the code above it.

Homework Problems

For every function you write, you must preface the function definition with a type ascription (also known as a contract) and a purpose, and you must follow it with tests with check testers (check-expect, check-within, check-error). Do write helper functions where it seems like a good idea to do so. All functions need contracts, purposes and tests, even if they are "only" helper functions. (In actuality, a function is just a function, and the "helper function" designation is an illusion.) You may also call functions from other functions whenever you like.

Problem 1

There are four major credit card brands in the United States. Credit card numbers are allocated such that the first digit in the sixteen-digit number indicates its brand:

• AmbivalentExpress cards (abbreviated AmEx) begin with a 3
• WorkPermit cards start with a 4
• DisasterCards have a 5 as their first digit
• Coverup cards use a 6

We define (and you should define, by copying-and-pasting the following into your hw3.rkt) the following data types to work with these cards:

(define-type CardBrand
  (U 'AmEx 'WorkPermit 'DisasterCard 'Coverup))

(define-struct CreditCard
  ([type : CardBrand]
   [num  : Integer]))

Write the following functions to work with credit card numbers:

• brand-digit which takes in a CardBrand and returns an Integer, the single digit which should be the first digit of a valid card number for a card issued by that brand
• brand-valid? which takes in a CreditCard and returns true if and only if the card number is in correspondence with the claimed brand
• build-card which takes in an Integer (the card number) and returns a properly branded CreditCard. If the card number does not correspond to any recognized brand, raise an error.

Please note the following ways to compare symbols for equality. There is a built in function symbol=? of type Symbol Symbol -> Boolean that behaves like other equality functions:

(symbol=? 'a 'A) => #f
(symbol=? 'A 'A) => #t
(symbol=? 'A 'b) => #f

Symbols can also be compared by pattern matching:

(match 'xyz
  ['abc 1]
  ['mno 2]
  ['xyz 3]
  [_ 0])

=> 3

Problem 2

The following data structures represent binary trees of integers and strings. These trees are just collections: there is no meaning embedded in the shape of the tree, and elements are not arranged in any particular order.

(define-type IntTree (U IntNode 'IEmpty))

(define-struct IntNode
  ([val   : Integer]
   [left  : IntTree]
   [right : IntTree]))

(define-type StringTree (U StringNode 'SEmpty))

(define-struct StringNode
  ([val   : String]
   [left  : StringTree]
   [right : StringTree]))

Write the following functions:

• mirror takes an IntTree and returns an IntTree with the same values and structure, except that at each node, the left and right subtrees are swapped. In other words, this function creates a mirror image of its argument. The following figure shows a pair of mirrored trees:

  

• int-tree->string-tree takes a tree with Integer values and generates a tree, with the same structure, that contains String values; the corresponding node in the string tree is the string representation of the original Integer (yielded by calling number->string).

  

• right-edge consumes a StringTree and produces a String. The result must be the concatenation of all the strings that appear along the right edge of the tree, in root-to-leaf order. The function should take no left turns; the right-edge contains the root and its right child, and its right child's child, and so on. For example, the right edge string of the following tree is "xyyz".

  

  Recall that the function string-append can be used to concatenate String values.

Problem 3

A 3Tree is a tree of degree 3 with integers at nodes. Here is a depiction of an example:

Please notice that the tree's degree does not mean there must be 3 children under every node, just that there may be as many as 3. Note also that there is no requirement that all the integers in a 3Tree be distinct; these are all distinct because it makes examples clearer.

The following data definitions define the 3Tree data structure.

(define-type 3Tree (U 3Node '3Empty))

(define-struct 3Node
  ([root : Integer]
   [lsub : 3Tree]
   [msub : 3Tree]
   [rsub : 3Tree]))

Please copy and paste this code into your hw3.rkt.

Note that the tree in the figure is written as follows as a Typed Racket value:

(3Node 1
       (3Node 2
              (3Node 3 '3Empty '3Empty '3Empty)
              (3Node 4 '3Empty '3Empty '3Empty)
              '3Empty)
       (3Node 8
              '3Empty
              (3Node 7
                     (3Node 5 '3Empty '3Empty '3Empty)
                     '3Empty
                     (3Node 6 '3Empty '3Empty '3Empty))
              '3Empty)
       (3Node 9
              '3Empty
              '3Empty
              (3Node 0 '3Empty '3Empty '3Empty)))

Then write implementations for each of the following operations:

• (: num-nodes : 3Tree -> Integer)

  This function should count the number of nodes in the tree. The tree illustrated above has 10 nodes.

• (: sum-nodes : 3Tree -> Integer)

  This function should add together all the values in a tree. The tree above has sum 45.

• (: height : 3Tree -> Integer)

  This function should measure the height of the tree, defined as follows: the empty tree has height 0; the tree consisting of only one node with no children (in other words, a leaf node), has height 1; a tree with 1 or more children has height one more than the height of its tallest child. The tree above has height 4.

• (: contains? : 3Tree Integer -> Boolean)

  This function should return true if the given tree contains the given integer anywhere among its node values.

• (: leftmost : 3Tree -> (U Integer 'None))

  This function should return the item farthest to the left in the tree. The leftmost item above is 3. The empty tree should return the symbol 'None for its leftmost.

• (: farthest-item : 3Tree -> (U Integer 'None))

  This function should return the item that is farthest away from the root of the tree; that is, the item whose path is the maximum number of steps away from the root. Break any ties by favoring the item on the left. The farthest item in the tree above is 5.

• (: increment : 3Tree -> 3Tree)

  This function consumes a tree and returns a new tree such that every integer is 1 larger. In other words, it is a "plus one" operation for the whole tree.

Problem 4

In this problem, we will gain practice with lists. Please note that lists are to be introduced in lecture on Friday, October 13; you may wish to delay working on this problem until you've heard that lecture.

Imagine that you work at an online retailer that sells books, food, and electronics. The following data type definitions represent one of your products:

(define-type Category (U 'Book 'Food 'Electronics))

(define-struct Product
  ([name  : String]
   [cat   : Category]
   [price : Integer]))

Note an item's price is represented by an integer number of pennies. It is bad practice to use inexact numbers to represent money (people, and institutions, don't take kindly to numerical inaccuracies where their finances are concerned).

You use lists for two purposes: to represent an order (the list of items that a customer is purchasing), and to represent your in-stock items (the list of items for which you can currently fulfill orders). For simplicity, we assume that customers only buy one of a particular item in a single order.

The following data types represent a list of products, which can be used in either of the above roles:

(define-type Products (U 'NoProducts ProductCons))
(define-struct ProductCons
  ([p    : Product]
   [rest : Products]))

Your task is to write the following functions:

• (: order-total : Products -> Integer)

  This function, given a list of products in an order, sums the prices of the items to yield the order total. The result is in pennies.

• (: media-mail? : Products -> Boolean)

  Determines if an order is eligible to be shipped via media mail (which is cheaper for the shipper than other methods, but permits only books to be sent). Return true if and only if all the items are books.

• (: perishable? : Products -> Boolean)

  Returns true if and only if at least one item in the order is a food (requiring that we stamp "Perishable" on the outside of the box).

• (: product=? : Product Product -> Boolean)

  Determines if two Products have the same name, category, and price.

• (: in-stock? : Product Products -> Boolean)

  Returns true if and only if a given Product is contained in the specified list.

• (: can-ship? : Products Products -> Boolean)

  Returns true if and only if all the Products in the first list (representing an order) are in the second list (representing those Products that are in stock).

• (: back-ordered : Products Products -> Products)

  Returns a list, possibly empty, of the Products in the order (the first parameter) that are not in stock (the second parameter represents those Products that are in stock), and thus must be back ordered.

Submit Your Work

Submit your work by committing hw3/hw3.rkt to your CS151 subversion repository by Monday, October 16 at 11:59pm. All your work must be contained in that one file.

You should commit your work early and often. Intermediate commits — that is, commits made along the way to the final commit — are strongly encouraged; only your last commit before the deadline will be evaluated by your graders.

A note on style. Please make sure your lines of code are not more than 80 characters long. You can see the current character number at the bottom center of the DrRacket window. Use line breaks to clarify your code, and press TAB frequently within DrRacket to align the code correctly. A more fully elaborated style guide is available as Appendix A of our Typed Racket guide.