Out: Tuesday, January 12th, Due: Monday, February 22nd, 10:00pm
Administrative
This homework is for individual work and submission.
In this submission as well as future homeworks,
you are required to have tests that cover your whole code, otherwise your
submission will be penalized.
The language for this homework is:
#lang plait
For this problem set, make sure you enable Syntactic test
suite coverage: <ctrl>-L to bring up the customization panel and
choose Syntactic test suite coverage under Dynamic
Properties. With this enabled, uncovered branches in your code
will be highlighted.
Submitted code should have comments that describe the function and its
type, as well as enough test cases for complete coverage (DrRacket
indicates covered expressions with colors for covered and uncovered source
code, unless your code is completely covered). Your tests should have the
following form: (test <expression> <expected>).
Important: Your tests should cover your whole code, otherwise the
marker will penalize your submission. You should not have any uncovered
expressions after you hit run. Note that appeasing the automatic coverage
testing is a minimum requirement, and usually more tests are needed
1. Binary Trees
Define a binary tree as a something that is either empty, a Leaf
holding a number, or a Node that contains a binary tree on the left and
one on the right.
Use the following a define-type definition for BINTREE,
Using this BINTREE definition, write a (higher-order) function
called tree-map that takes in a numeric function f and a binary tree,
and returns a tree with the same shape but using f(n) for values in its
leaves. For example, here is a test case:
Using the same BINTREE type
implement tree-fold, which is the equivalent of the
foldl for lists. There are two differences
between tree-fold and foldl: first, foldl has a single init
argument that determines the result for the single empty list value. But
with our trees, the base cases are Empty or a Leaf that holds some
number — so we need both a value for Empty and a (numeric)
function for Leaf. The second difference
is that tree-fold’s combiner function receives different inputs: the two
results for the two subtrees. tree-fold should therefore consume four
values — the combiner function (a function of two arguments), the leaf
function (a function of a single number argument), the empty value to
return for empty subtrees and the BINTREE value
to process.
Note: tree-fold is a polymorphic function, so its type should be
parameterized over “some input type A”. The Typed Racket notation for
this is
(: tree-fold : (All (A) (Number -> A) (A A -> A) A BINTREE -> A))
(define (tree-fold leafer combiner empty tree)
...)
When your implementation is complete, you can use it, for example, to
implement a tree-flatten function that consumes a BINTREE and
returns a list of its values from left to right:
(: tree-flatten : BINTREE -> (Listof Number))
;; flattens a binary tree to a list of its values in
;; left-to-right order
(define (tree-flatten tree)
(tree-fold (inst list Number) (inst append Number) null tree))
You can use this function, as well as others you come up with, to test your
code.
Note the use of (inst f Number) — the Typed Racket inference has
certain limitations that prevent it from inferring the correct type. We need
to ‘help’ it in these cases, and say explicitly that we use the two
polymorphic functions append and list instantiated with Number.
Think about an (All (A) ...) type as a kind of a function at the type
world, and inst is similar to calling such a function with an argument
for A. You will not need to use this elsewhere in your answers.
Here is an example test case: