Assignment 8: Trees, forests, and ML

Due: Wednesday, October 31, 11:59:59 PM EST.

The following should be completed in cooperation with your latest assigned partner. You may not share code for this assignment with anyone but your partner.

You must use the design recipe and The Style guidelines to receive full credit.

1 Preparation

Make sure you have read all of Part III and through section 19.2 of Part IV of HtDP2e.

2 A walk in the forest

Edit a file named EXACTLY ft.rkt for this part of the assignment. Add your information to the standard file header at the top of the file.

Complete exercises 310–315 from HtDP2e Part IV. (Use the function name forest-average-age in exercise 315 to avoid conflicting with average-age in 311.)

3 Mark it

Edit a file named EXACTLY ml.rkt for this part of the assignment. Add your information to the standard file header at the top of the file.

Markup languages abound. Examples include HTML, XML, XHTML, LaTeX, troff, YAML, and many many more. A markup language is used to annotate textual information with "editor marks" that annotate how the text should be presented. For example, a snippet of HTML, the hypertext markup language for documents on the web, looks like this:

The content of this document contains elements, which are enclosed in balanced brackets like <p> and </p>. Each element has a tag, in this case the tag is "p", and a content, which may consist of textual data (strings) or elements.

This suggest the following data definitions for a simple, but general purpose, markup language:

; A Content is a [Listof Item]

; Interp: a collection of content in a markup document

; An Item is one of:

; - a String

; - an Element

; Interp: an item in a document, either text or an element

; An Element is a (make-elem Tag Content)

; Interp: an element is content annotated with a tag

(define-struct elem (tag content))

; A Tag is a String

; Interp: the name of the tag, e.g. "p"

Exercise 1 Make an example representing the content in the HTML document snippet above.

Exercise 2 Design a function content-to-HTML that converts content to a string representation of the HTML markup. For example, convert the example from exercise 1 should produce a string that starts "<h1>Mark it</h1><p>Edit the file named <b>EXACTLY</b> <tt>ml.rkt</tt> for...".

(There are some subtle issues like what to do if there is an item in the document which is a string that looks like HTML, e.g. "<tt>", but we will ignore those issues for now.)

Exercise 3 Design a function content-contains-tag? that determines if an element with a given tag occurs within any part of the content of document.

Exercise 4 Design a function content-length that sums up the length of all the textual items with a document.

Exercise 5 Design a function content-contains-elem? that consumes a predicate on elements and returns true if the content contains any element that satisfies the predicate.

Exercise 6 Design a function content-retag that takes two tags and renames every occurrence of the first tag to the second tag within the given content.

Exercise 7 Design a function content-max-nesting that determines the maximum level of element nesting within the given content. (The max nesting level in the example above is 2.)

Exercise 8 Design a function content-text that produces a list of all the text that occurs in a document, in the order it occurs.

Exercise 9 Design a function content-skeleton that, given content, produces a document that is like the given content, but with all text removed.

4 Project submission

You should submit two files named EXACTLY: ft.rkt and ml.rkt.

Submit your files directly to the submit server by uploading them. Select each of these files individually using the “Browse” button. Once you have selected all the files, press the “Submit project!” button. You do not need to put them in a zip file.