On this page:
1 Counting literature
2 Calder mobiles

Assignment 7: Lists and trees

This assignment is due on Wednesday, 2/21 at 11:59 PM. Submit it using the Handin server as assignment a7.

Important Note: Whenever we say to "design a function", we mean that you need to follow the design recipe. Any other time that you write a function in this class, you also need to follow the design recipe.

1 Counting literature

Exercise 1 Develop a data and structure definition for storing a Frequency, which combines a String and a Number and represents that many uses of that string. Call the structure frequency with fields word and count.

Exercise 2 Develop a data definition ListOfString that uses cons and empty to hold arbitrarily many Strings. Similarly, develop a data definition for ListOfFrequency that uses cons and empty to hold arbitrarily many Frequencys.

Exercise 3 Design a function count-word that consumes a ListOfFrequency and a String and adds 1 to the frequency for that string, producing a new ListOfFrequency. If there is no Frequency for that string, the resulting ListOfFrequency should have a Frequency with that string and the number 1.

Exercise 4 Design a function count-all-words that takes a ListOfString and produces a ListOfFrequency with the frequencies counted from the entire list of strings.

Exercise 5 Download the text of Hamlet into the same folder as your file where you are completing this assignment.

Then use the 2htdp/batch-io library to create a list of words from the file. As in the lab, you should use the built-in read-words function.

Then compute the frequencies of all of the words in the file. Because this operation might take a while, don’t define it as a constant. Instead, put it in a short comment, like this:
; (define hamlet-frequencies ...)

Exercise 6 Design a function frequents that consumes a ListOfFrequency and produces a ListOfFrequency that contains only the Frequencys from the original list where the number is more than 100. Use this to compute all the words used more than 100 times in Hamlet. Include this list in your submission, as another comment. (Did you know about the "Comment Out with Semicolons" command under the "Racket" menu in DrRacket? It’s handy.)

2 Calder mobiles

Calder mobiles are a kind of sculpture that can be represented using a self-referential data definition. Here are some ways to learn about them:
  • The Calder Foundation web site shows a variety of Calder mobiles.

  • Wikipedia describes a mobile as "a number of rods, from which weighted objects or further rods hang. The objects hanging from the rods balance each other, so that the rods remain more or less horizontal."

  • The Saint Louis Art Museum (free!) houses a nice Calder mobile in its collection.

Typically, each rod in a mobile has two sub-mobiles hanging off of it. Let’s represent such a mobile using this data definition:
; A Mobile is one of:
; - (make-leaf Number)
; - (make-rod Mobile Number Number Mobile)
(define-struct leaf [weight])
(define-struct rod [lm ld rd rm])
In the field names of rod, the letters l r m d stand for left, right, mobile, and distance, respectively. One way to familiarize yourself with this data definition is to define some Mobiles as constants. Also, read about binary trees in the textbook, in part IV Intertwined Data.

Exercise 7 Design a function weight that takes a Mobile as input and computes its total weight. For simplicity, assume that the connection between the two sub-mobiles of a rod adds no weight.

Exercise 8 Design a function average-leaf-weight that takes a Mobile as input and computes its leaves’ average weight. You’ll need a helper function that also takes a Mobile as input.

Exercise 9 Design a function all-balanced? that takes a Mobile as input and returns a Boolean indicating whether it is balanced everywhere. Use the following helper function to compute and compare torques, after providing its missing examples as tests.
; balanced? : Mobile -> Boolean
; determines whether the given mobile is balanced at the top
(define (balanced? m)
  (cond [(leaf? m) true]
        [(rod? m) (= (* (rod-ld m) (weight (rod-lm m)))
                     (* (rod-rd m) (weight (rod-rm m))))]))

Exercise 10 Design a function lighten that takes a Mobile as input and returns a new Mobile that is like the given one except everything weighs half as much as the given one. (So, your all-balanced? function should produce the same result for the given and returned mobiles.)

Exercise 11 Design a function enlarge that takes a Number and Mobile as inputs and returns a new Mobile that is like the given one except all the distances are that many times as long as the given one. (So, your weight, average-leaf-weight, and all-balanced? functions should produce the same results for the given and returned mobiles.)

Exercise 12 Design a function all-balanced-mobile that takes a positive integer as input and returns a Mobile that has exactly that many leaves and satisfies all-balanced?.

Hint: Develop a data definition for positive integers, then follow its template. If you already have a Mobile that satisfies all-balanced?, then one way to make a Mobile that has exactly one more leaf and also satisfies all-balanced? is to balance the existing mobile against a new leaf whose weight is the total weight of the entire existing mobile. So this helper function is useful (but if you use it, provide its missing examples as tests):
; counterbalance : Mobile -> Mobile
; adds a leaf to a given mobile in a balanced? way
(define (counterbalance m)
  (make-rod m 20 20 (make-leaf (weight m))))

Extra fun 1 Design a function that draws a given Mobile.

Extra fun 2 Generalize rod so that each rod can hold not just two mobiles but any number of mobiles. Revise your functions to operate on your new data definition.