Assignment 2: More Programming in Plait

Objectives:

Become comfortable with solving recursive problems involves lists and trees in Plait.
Know how to translate a written problem statement into a Plait program

Resources:

The Plait tutorial and documentation page: https://docs.racket-lang.org/plait/
How to Design Programs: https://htdp.org/

Parameters:

Due date: Wednesday January 24 at 11:59PM
Upload a code.rkt file with your solution to Gradescope.
the first line in code.rkt should be #lang plait.
Ask questions on Piazza or during Office Hours.
Perform all the work for this project by yourself. You may discuss with your classmates, but you must write your own code.

Exercise 1: Basic lists

Write a function all-greater? l n that takes two arguments – l a list of numbers, and a number n – and returns #t if every element of l is greater than n and #f otherwise.

Example usage:

> (all-greater? '(1 2 9) 0)
#t
> (all-greater? '() 0)
#t

Your solution should make use of the following built-in list functions (see here):

empty?
first
rest

You are encouraged to include least 3 tests for your function.

Exercise 2: Helper functions

Write a function sorted? that takes a list of numbers as an argument and returns #t if the list is sorted from least to greatest and #f otherwise.

Example usage:

> (sorted? '(1 2 3))
#t
> (sorted? '())
#t

You are encouraged to include at least 3 tests for your function.

Exercise 3: Trees

The following Tree datatype implements a binary tree with a number in each node and leaf:

(define-type Tree
  (leaf [val : Number])
  (node [val : Number]
        [left : Tree]
        [right : Tree]))

As an example for how to use this data-type, suppose we want to encode the following tree:

We can write this using our Tree datatype as:

(node 2 (leaf 1) (node 3 (leaf 4) (leaf 5)))

Implement a sum function that takes a Tree as input and returns the sum of all numbers in the tree.

Example usage:

> (sum (node 5 (leaf 6) (leaf 7)))
18

You are encouraged to include at least 3 tests for your function.

Exercise 4: More trees

Implement the function contains?, which takes a tree and a number as input and returns #t if the number is in the tree and #f otherwise.

Example usage:

> (contains? (node 0 (leaf 4) (leaf 5)) 5)
#t

Exercise 5: Modifying trees

Implement the function nonneg, which takes a Tree as input and returns a tree that is identical to the input except negative values are replaced by 0.

Example usage:

> (nonneg (node -4 (leaf 6) (leaf 7)))
(node 0 (leaf 6) (leaf 7))

You are encouraged to include least 3 tests for your function.