This homework is due at 11:59PM on Monday, November 18. Submit your solutions in a single file using the COMP 50 Handin button on DrRacket; the homework is the loops homework.

All the exercises should be done using the Intermediate Student Language with lambda.

How to tackle this homework

This homework has a lot of parts. I want to call your attention to where I think the challenges are.

Data definitions

A (bst X) is either of

A (setof X) is either of

Finger exercises

The first group of finger exercises from the book are basic exercises in the topics needed for this homework. The last three finger exercises are there in case you are not sure of your ground; in that case, tackle them with a study partner or guidance of a TA. And definitely post your results to Piazza so you can be sure you are on the right track.

Problems to submit

Parametric data definitions and polymorphic signatures

I remind you of the rules for type variables:

Solve all parts of the following problem:

  1. Writing and applying parametric data definitions

    1. After a visit to a corn maze, Professor Hescott writes a maze-searching function that will run on a robot. This function is given a predicate and returns one of two kinds of results:

      • A value satisfying the predicate
      • An explanation indicating why no such value could be found

      An explanation always includes string, such as “I looked everywhere but the maze does not contain the object you wanted” or “I could not find my way through the entire maze” or “Part of the maze was closed for construction”.

      Write a parametric data definition that describes the results returned by this function. Be sure that if Professor Hescott sends the robot to look for a string containing both consonants and vowels, that there is some way to tell whether such a string has been found.

    2. Write a parametric data definition for a list containing an even number of elements, all of which are the same kind of data.

      Examples:

        '(10 20 30 40 50 60)
        '("Hi" "there" "I'm" "sorry" "about" "Greasy")

      Non-examples:

        '(1 "fish" 2 "fish" red "fish" blue "fish")
        '("Hi" "there" "I'm" "sorry" "about" "the" "frog")
    3. Using your parametric definition from the previous problem, describe the data of each of the examples.

    4. Write a parametric data definition for a list containing an even number of elements in which their are two possibly different kinds of data and elements alternate.

      Examples:

        '(one "fish" two "fish" red "fish" blue "fish")
        '("Hescott" 7 "Ramsey" 8 "Guyer" 4)
        '(lecture ("M" "W") lab ("W" "Th") main-office ("M" "T" "W" "Th" "F"))
        '(10 20 30 40 50 60)

      Non-examples:

        '(1 "fish" 2 "fish" red "fish" blue "fish")
        '(ol (li "Homework") (li "Lab") (li "Portfolio))
    5. Using your parametric definition from the previous problem, describe the data of each of the examples.

    6. The quote notation can easily be used to define a form of “association lists”, which is a list of lists. Each inner list contains two elements: a key and a value.

      Examples:

        '((one "fish") (two "fish") (red "fish") (blue "fish"))
        '(("Hescott" 7) ("Ramsey" 8) ("Guyer" 4))
        '((lecture ("M" "W")) (lab ("W" "Th")) (main-office ("M" "T" "W" "Th" "F")))
        '((10 20) (30 40) (50 60))

      Write a parametric data definition to describe this form of association list.

    7. Using your parametric definition from the previous problem, describe the data of each of the examples.

Binary search trees

Binary search trees will play a significant role in your final homework (identify what language a web page is written in). In all the problems below, We will pay special attention to signatures and purpose statements.

  1. Adding information to a binary search tree
    Solve all three parts:

    1. Key properties
      Design a function every-key? which tests to see if every key in a binary search tree satisfies a given predicate.

    2. Adding information to a binary search tree
      Design a function insert which takes a key, a value, and a binary search tree. It returns a new binary search tree that is exactly like the given tree, except that in the new tree, the given key is associated with the given value. If the original tree contains the given key, then the new tree should have the same number of nodes as the original.

    3. Test the results of insert to be sure that insert always returns a true binary search tree that respects ordering properties.

  2. Converting between trees and lists.

    1. Without using recursion, write a function that takes an association list with string-valued keys and returns the corresponding binary search tree. Assume that the list contains no duplicate keys.

      We will pay special attention to your signature and purpose statement.

    2. Design a function that converts a binary search tree to an association list. Your function should make sure that for any node in the tree, the key-value pair of that node always precedes the key-value pairs of the nodes in its two subtrees.

      It may help you name the function to know that the resulting list is called a preorder listing of the tree

    3. Design another function that converts a binary search tree to an association list. Your function should make sure that for any node in the tree, the key-value pair of that node always follows the key-value pairs of the nodes in its two subtrees.

      It may help you name the function to know that the resulting list is called a postorder listing of the tree

    4. Design a third function that converts a binary search tree to an association list. Your function should make sure that in the association list, keys appear in increasing order.

      It may help you name the function to know that the resulting list is called an inorder listing of the tree

    5. For long-term-storage, trees are written out to disk as a sequence of characters. It should be possible to recover the tree exactly.

      Demonstrate by testing that if you run one of the three tree-to-list functions, then convert the list back to a tree using your function from part (a), then you will recover the original tree exactly.

More standard abstract functions on lists

  1. Using the built-in abstract functions for list processing, solve the following parts. In this problem of the assignment, do not use any recursion.

    1. Define a function is-in? that tests to see if a number is in a set of numbers.

    2. Define a function set-insert that inserts a number into a set of numbers. That is, if number z is inserted into set zs, the resulting value is a set that contains all the elements of zs and also contains z.

    3. Define a function set-difference that computes the difference between two sets of numbers. (The difference of two sets contains all elements that are in the first set but not in the second.)

    4. Define a function set-intersection that computes the intersection of two sets of numbers. (The intersection of two sets contains all element that are in both sets.)

    5. Define a function set-union that computes the union of two sets of numbers. (The union of two sets contains every element that is in either set.)

Improving code through abstraction and local definitions

In this section you use local definition and abstraction to improve my solution to the nearest-point problem (Problem 5 on the abstractions homework).

  1. My solution to nearest-point uses a number of helper functions. Without trying to combine maybe-above-or-below and maybe-left-or-right, improve my solution as follows:

    Does this refactoring improve the solution overall? Why or why not? In a comment, write your opinion.

    How to solve this problem without making yourself crazy:

    Slow is fast: if you are methodical and you press Run at each step of the process, the only things you’ll really have to think about are which parameters are superfluous. Everything else will just work.

    If you’re greedy and you try to do big chunks at once, you could get lucky… or you could create a mess that you cannot debug.

    When you finish, don’t forget to write your opinion.

Karma Problems

Some abstractions can go too far:

  1. In my solution to nearest-point, the functions maybe-above-or-below and maybe-left-or-right are nearly identical. Please write a signature, purpose statement, and header that answer these two questions:

    1. If the nearly identical functions were replaced by a single abstraction, what additional parameter(s) would have to be passed?

    2. If the nearly identical functions were replaced by a single abstraction, what would be its purpose statement?

    Is this abstraction worth it? Why or why not? In a comment, write your opinion.

It would be pleasant to use 2D-tree search directly on the USGS points-of-interest dataset. But the USGS uses GPS coordinates, not Euclidean coordinates. Address this deficiency by solving the following two problems:

  1. Copy your improved solution from problem 6 and use it to implement a function nearest-point-gps, in which the x coordinate is longitude in degrees and the y coordinate is latitude in degrees. Your computation of distance will have to change:

  2. Abstract over your two 2D-search functions to define a single higher-order function that takes as arguments functions that compute distances and returns as result an efficient 2D-search function.

    Take care with the signature and purpose statement.

    Demonstrate your solution by

    1. Instantiating the function for Euclidean distance and showing it computes the same results as my original

    2. Instantiating the function for GPS distance and showing it computes the same results as your modified code

    Is the abstraction worth it? Why or why not? In a comment, write your opinion.

Hint for testing: A point 1.2 degrees west of Boston is actually closer to Boston than a point 1.0 degrees north of Boston.


  1. The formula above gives the distance traveling along a line of latitude. As you get further from the equator, the shortest route loops away from the equator, and the actual distance is shorter.