Homework 9: Typed Racket
Due: Monday, December 2 at 23:59
In this assignment, you’ll be implementing some functions on lists using Typed Racket.
Your implementation will be in the hw9.rkt file. The start of the file should be
#lang typed/racket
; Your name(s) here.
The goals of this assignment are two-fold,
- Learn a new-ish language mostly on your own; and
- Reinforce your understanding of the standard list functions used in functional programming languages.
Preliminaries
Click on the assignment link. The same partner making rules apply as normal. You can work in new teams for Homework 9, as this is not part of the MiniScheme Project.
Once you have accepted the assignment and created/joined a team, you can clone the repository on your computer by following the instructions and begin working. But before you do, read the entire assignment and be sure to check out the expected coding style, as posted on Ed.
Submission
To submit your homework, you must commit and push to GitHub before the deadline.
Note that apart from a new HONORCODE.md, there are no starter files for Homework 8. This is because you will be directly building on your Homework 6 work!
Start by copying all of your .rkt files from Homework 6 into your repository and committing them. Upon submission, your repository should contain the following files:
Any additional files you have added to your repository should be removed from the main branch. (You’re free to make other branches, if you desire, but make sure main contains the version of the code you want graded.)
Make sure you put your name (and your partner’s name if you’re working with one) as a comment at the top of each file.
Some examples to start
Your task is to write implementations of several functions that operate on lists in Typed Racket.
You are definitely going to want to read The Typed Racket Guide before and during your work on this assignment. Refer to it often! In particular, you should read chapters 1 through 4 and section 8.2. (Section 8.2 is confusing! Please ask questions about it on Ed.) You can skip sections 3.1.4, 4.3, 4.7, and 4.10. You may also want to consult The Typed Racket Reference.
Each function you write must contain a proper type definition. This includes functions you define via define and those you define via lambda. Here’s an example function showing how to compute the maximum of a list of real numbers (see the reference for how the various types of numbers in Typed Racket relate).
(: maximum (-> (Listof Real) (U Real False)))
(define (maximum lst)
(if (empty? lst)
#f
(let ([head : Real (first lst)]
[max : (U Real False) (maximum (rest lst))])
(cond [(not max) head]
[(> max head) max]
[else head]))))
The first line declares the type of maximum to be a function that takes a list of real numbers as arguments and returns either a real number or #f (see Union types in the guide).
The definition of maximum is pretty standard: It walks to the end of the list first (see the recursive call on the rest of lst). Then, as the recursive calls return, it compares the first element of the list to the maximum of the rest of the list (if such a maximum exists) and returns whichever is larger.
Notice how I specified the types of the variables in the let bindings as [var : type expr] which says that var has type type and its value is computed by expr. For example, [head : Real (first lst)] says head has type Real and its value is (first lst). max is declared similarly but note that since the return type of maximum is (U Real False), the type of max is declared to be (U Real False). If that declaration is changed to
[max : Real (maximum (rest lst))]
then you get a type error
Type Checker: type mismatch
expected: Real
given: (U False Real) in: (maximum (rest lst))
The second example demonstrates parametric polymorphism, recursive helper functions, and specifying types of lambdas.
(: reverse (All (a) (-> (Listof a) (Listof a))))
(define (reverse lst)
(letrec ([f : (-> (Listof a) (Listof a) (Listof a))
(λ ([lst : (Listof a)]
[acc : (Listof a)]) : (Listof a)
(if (empty? lst)
acc
(f (rest lst) (cons (first lst) acc))))])
(f lst empty)))
The type of reverse tells us that it is a function that takes a list of elements of some arbitrary type a as an argument and returns a list of elements of the same type. See Polymorphic Functions in the guide.
The letrec defines a recursive function f that takes two lists of a as arguments and returns a list of a. Inside the lambda, each parameter is specified as [var : type] and the return type of the lambda is specified after the parameters. For example, (lambda ([x : Number]) : Number x) specifies that the lambda has one argument that’s a Number and returns a Number.
Your task
Implement the following functions in Typed Racket. Remember, each function you write must contain a proper type definition. This includes functions you define via define and those you define via lambda.
You may not implement these functions using any higher-order functions in the standard library (e.g., no map, foldl, foldr, or apply).
The provided starter code contains the examples as RackUnit tests. RackUnit in Typed Racket is buggy. The names of tests aren’t always reported correctly and the summary showing how many tests passed, failed, or had errors reports failed tests as having passed. Tests that fail still print their failure, they’re just counted as successes in the final summary.
(fold-left proc init lst). This should behave like the standard library foldl function when called with a single list. Here are some examples The second example includes (inst cons Symbol Null). This is instantiating the cons function to construct a (Listof Symbol). The issue here is cons is polymorphic and Typed Racket doesn’t know what concrete type to give it. cons has two type arguments (its type is (All (a b) …)) and (inst cons Symbol Null) instantiates with the concrete types Symbol and Null. We can see this by asking DrRacket to print out types
> (:print-type cons)
(All (a b) (case->
(-> a (Listof a) (Listof a))
(-> a b (Pairof a b))))
> (:print-type (inst cons Symbol Null))
(case->
(-> Symbol (Listof Symbol) (Listof Symbol))
(-> Symbol Symbol (List Symbol)))
The first type says cons either takes an element of some type a and a (Listof a) and produces a (Listof a) or it takes an element of some type a and an element of some type b and produces a pair. The second type instantiates a with Symbol and b with Null so it either takes a Symbol and a (Listof Symbol) and produces a (Listof Symbol), or it takes a Symbol and null (the type of null is Null) and produces a 1-element list containing a Symbol.
(fold-right proc init lst). This should behave like the standard library foldr function when called with a single list. Here are some examples (map proc lst). This should behave like the standard library function map when called with one list. Examples can be found in the provided starter code.
(scan-left proc init lst). This function behaves similarly to fold-left except that rather than return only the final value that comes from successively applying proc to elements of the list and the accumulator, it returns all of the values, starting with init and ending with the final value of (fold-left proc init lst). Here is one example, others are in the provided starter code. (scan-left + 0 '(1 2 3 4)) returns '(0 1 3 6 10).
(scan-right proc init lst). This function behaves analogously to scan-left except that it starts at the right end of the list. The last element of the returned list is init and the first element is the final value of (fold-right proc init lst). Here is one example, others are in the provided starter code. (scan-right + 0 '(1 2 3 4)) returns '(10 9 7 4 0).
Finishing up
Make sure you (and your partner, if you have one!) have signed the Honor Code and then add/commit/push. Also make sure your name(s) is in all of the files you submit. Your friendly graders thank you!