Assignment 10
Due Date: Tuesday, 4/3 at 9:00pm (Week 12)
Purpose To practice designing generative recursive functions.
Exercise 1 The idea behind run-length encoding is to replace repeated sequences of the same character (a "run") with one copy of the character followed by the count of how many times it appeared in a row. For example, "AAAAAA" turns into "A6", and "AAABCCA" turns into "A3B1C2A1". Design a function run-length-encode that takes a [List-of 1String], and produces a single string containing the run-length encoded result. For convenience, use the explode function:(check-expect (run-length-encode (explode "AAABCCA")) "A3B1C2A1")
Graded Exercises
Exercise 2 Here is a data definition for a Wiki:
(define-struct page [title content]) ; A Wiki is a [List-of Page] ; A Page is a (make-page Symbol [List-of Symbol]) ; INTERPRETATION: An individual page contains a title and a ; list of links to other pages (represented by their titles). Design the function out-links that accepts a Symbol and a Wiki, and returns a [List-of Symbol] representing all pages that the given page links to. (This should not need to be a generative function.)
Exercise 3 Design the function in-links that accepts a Symbol and a Wiki, and returns a [List-of Symbol] representing all pages that link to the given page.
Exercise 4 Design the function cycle? that accepts a Wiki and returns a Boolean representing whether or not a cycle exists in the Wiki. In other words, is there a way to start on some page in the Wiki, follow links, and end up back at the same page?
Hint: You should not use accumulators for this problem; solve it generatively. Consider the structure of in-links and out-links in a Wiki, when there is a cycle present and when there is not. What cannot be true about the links for any pages involved in a cycle, and can you use that fact to come up with a generative idea?
Reminder: When designing a generative function, you need to explicitly write down the generative idea that guides why the recursion works, and you also need to explicitly write down the termination argument that explains why the function does not loop forever.