Module 07
Last updated: Thu, 12 Feb 2015 10:47:33 -0500
Readings
HTDP/2e, Part VI, Chapters 36-39
We are jumping ahead in the textbook, so ignore the generative recursion parts for now (e.g., Chapters 36.2, 38.2, 38.3)
Supplemental Materials
Read the short section in The Program Design Recipe guide on how to use Accumulators in this course.
Pre-lecture
Read the Readings and Supplemental Materials.
Goals
Understand how accumulators address the "loss of knowledge" in some functions by capturing additional context information.
Understand when and how to use accumulators.
Understand the expected style of accumulator-style functions.
In-class
This exercise demonstrates that accumulators are useful not only with lists.
Below is a data definition for a binary tree.
Complete the rest of the Data Design steps.
Then implement the function bt-depths. Make sure to satisfy
all the requirements for Accumulators if you use one
(or more).
; A BinaryTreeOf<X> (BTreeOf<X>) is one of: ; - X ; - (make-tree BTreeOf<X> BTreeOf<X>) ; Represents a binary tree where the X elements are stored at the leaves. ; A Depth is a Natural ; Representing the number of steps from the root of a tree to a node. ; bt-depths : BTreeOf<X> -> BTreeOf<Depth> ; Replaces the value at each node in bt with its depth. ; The root node has depth 0. (define (bt-depths bt) ...)