1 Plait🔗

Objectives:

• Become comfortable with using the Plait features for defining and calling functions, conditionals, arithmetic, and defining datatypes.

• Know how to translate a written problem statement into a Plait program.

• Learn how to test your code and write specifications.

Setup:

• Install DrRacket and Plait by following the instructions here

• Download the starter code from here

1.1 Max (10 Points)🔗

Implement a function my-max that takes as input two numbers as input and outputs whichever one is greater. Do not use the built-in max function. Example interaction:

> (my-max 10 3)

10

1.2 all-greater (10 Points)🔗

Implement the function all-greater? l k of type ((Listof Number) Number -> Boolean) that takes as input a list of numbers and number k and returns #t if every element in l is greater than k and #f otherwise. The empty list trivially satisfies the requirement, so (all-greater? '() k) should return #t for any k.

Example interaction:

> (all-greater? '(1 2 3) 1)

#f

If you are unfamiliar with working with lists in scheme-like languages, you should read the documentation for lists by follinwg the link here: list.

1.3 sorted? (10 Points)🔗

Implement the function sorted? l of type ((Listof Number) -> Boolean) that returns #t if the list is sorted from least to greatest and #f otherwise. Your solution should use a helper function.

Example:

> (sorted? '(2 3 4))

#t

1.4 sum-tree (10 Points)🔗

The following problems use a binary tree datatype whose leaves are numbers:

(define-type Tree

(leaf [value : Number])

(node [left : Tree] [right : Tree]))

Implement the function sum-tree t of type (Tree -> Number) and returns the result of summing all values contained in the leaves in the tree.

Example:

> (sum-tree (node (leaf 10) (leaf 20)))

30

Your solution must make use of the type-case construct.

1.5 right-linear? (10 Points)🔗

A binary tree is right-linear if, for every node in the tree, the left child is a leaf. For example, the following tree is right-linear:

Implement a function right-linear? t of type (Tree -> Boolean) that returns #t if the tree is right-linear and #f otherwise.

Example:

> (right-linear? (node (leaf 10) (leaf 20)))

#t

1.6 dfs-list (10 Points)🔗

A depth-first left-first traversal of a tree traverses the tree in depth-first order starting with the left child of each node. Consider this tree:

For the above tree, a depth-first left-first traversal explores leaf 1, then 2, then 3.

Implement a function dfs-list t of type (Tree -> (Listof Number)) that returns a list of all the leaf values traversed according to depth-first left-first order.

Example:

> (dfs-list (node (node (leaf 1) (leaf 2)) (leaf 3)))

'(1 2 3)

1.7 subst (10 Points)🔗

Implement a function subst t old n of type (Tree Number Number -> Tree) that takes a tree t and two numbers old and n as arguments and returns a tree that results from substituting all leaves of value old with n. This is like a "find and replace" for trees.

1.8 multi-subst (20 Points)🔗

Now we want to perform multiple substitutions at once. We will keep track of all the substitutions in a hash table. Explore the Plait documentation, or click on the relevant links in this document, to learn how hash tables in Plait work. You will need to use the functions make-hash, hash-ref. You will also need to make use of the Optionof type, which has variants none and some.

Implement the function multi-subst of type (Tree (Hashof Number Number) -> Tree) that takes a tree t and a hash table tbl as input and returns a new tree that results from performing all the substitutions specified by tbl. If a leaf’s value is not found in the substitution table, leave that leaf unchanged.

Example:

; define a substitution that maps 1 to 3 and 2 to 4

> (define test-tbl (make-hash (list (pair 1 3) (pair 2 4))))

> (test (multi-subst (node (leaf 1) (leaf 20)) test-tbl)

(node (leaf 3) (leaf 20)))

1.9 filter (10 Points)🔗

Implement a function my-filter l f of type ((Listof Number) (Number -> Boolean) -> (Listof Number)) that takes a list of numbers and a function as input that removes all elements of the list for which f evaluates to #f.

Example:

> (my-filter '(1 2 3) (lambda (x) (< x 3)))

'(1 2)