Introduction

In this assignment you will work on recursion on structures in racket. We will use the same structure definitions from Section 4 of FICS as in the compare exercise in lab 4. You will also need your solution to that exercise.

(define-struct Z ())
(define-struct S (pred))

In order to make tests easier to read, we will pre-define some structure based numbers.

(define zero (make-Z))
(define one (make-S zero))
(define two (make-S one))
(define three (make-S two))
(define four (make-S three))

What to hand in, and how to hand it in, and when

• Make a directory ~/cs2613/assignments/A1 (i.e. in your git repo for this class).

• Use "#lang htdp/bsl" for this assignment

• Hand in all your work for this assignment in a file ~/cs2613/assignments/A1/div.rkt

• Make sure you commit and push all your work using git before 16:30h on Thursday January 23.

Marking

• This assignment will be worth 5% of your final grade.
• You will be marked on the last version pushed to coursegit
• For a rubric (marking scheme), see racket-assignment

Question 1

Modify the compare function from L04 to write a function sub that subtracts two natural numbers. If the result would be negative, your function should throw an error. Use the structural recursion on natural number structures pattern. Your function should pass (at least) the following tests

(check-expect (sub zero zero) zero)
(check-expect (sub one zero) one)
(check-expect (sub one one) zero)
(check-error (sub one two) "negative numbers not implemented")

Question 2

Modify the compare function from L04 to write a function less that returns true if the first one is smaller than the second, and false otherwise. Use the structural recursion on natural number structures pattern. Your function should pass (at least) the following tests

(check-expect (less zero zero) false)
(check-expect (less zero one) true)
(check-expect (less one zero) false) 
(check-expect (less two one) false)
(check-expect (less one two) true)

Question 3

Use your solutions to Questions 1 and 2, along with structural recursion to write a function div the does integer division on natural numbers. Your function should pass at least the following tests

(check-error (div zero zero) "divide by zero")
(check-error (div one zero) "divide by zero")
(check-expect (div  one one) one)
(check-expect (div three two) one)
(check-expect (div four two) two)