On this page:
Ancestor Trees
Code Review
Descendant Trees
Code Review

10 Designing with Accumulators

Claudia Vilcu (with a few edits from Matthias)

home work!

Purpose The purpose of this lab is to design functions using the accumulator-based approach.


5 minutes

Remember the basics of accumulator-based design:
  1. Recognize the need for introducing an accumulator and switch to an accumulator template. Common cases are generative recursion algorithms that fail in some cases due to lack of context knowledge, or structurally recursive function that traverses the result of its natural recursion with an auxiliary that is also recursive.

  2. The key step is to formulate an accumulator statement, also called an invariant. It must express what knowledge the accumulator gathers and what kind of data. In most cases, the accumulator statement describes the difference between the original argument and the current one.

  3. Deduce from the accumulator statement:

    1. what is the initial accumulator value?

    2. how can the function maintain the accumulator invariant when it recurs and drops pieces of its argument?

    3. how can the function exploit the knowledge in the accumulator?

Ancestor Trees

25 minutes

Ancestor Trees are one way of representing family-type data, by having each child point to its ancestors.

The following data definitions and examples, as well as a few "library functions" are provided for you in this file.

(define-struct child [name mother father])
; A AncestorTree (AT) is one of:
;  - ‘unknown
;  -  Child
; A Child is a
;    (make-child String AT AT)
; interpretation name is the child's name,
; mother is the maternal AncestorTree, and
; father is the paternal AncestorTree
(define Carmen (make-child "Carmen" 'unknown 'unknown))
(define John (make-child "John" 'unknown 'unknown))
(define Joel (make-child "Joel" 'unknown 'unknown))
(define Vladimir (make-child "Vladimir" 'unknown 'unknown))
(define Mike (make-child "Mike" Carmen John))
(define Lucy (make-child "Lucy" Joel Mike))
(define Terrence (make-child "Terrence" Joel Mike))
(define Priscilla (make-child "Priscilla" Lucy Vladimir))

Exercise 1 Design the function, path-to-child, which given an origin AncestorTree, and the name of an ancestor, returns the path from the ancestor to the child, or #false if no path exists. Include the ancestor and the child in the path.

Domain Knowledge A path describes the sequence of relationships (mother, father) that lead from one child structure to another in an AncestorTree.

Code Review

15 minutes

The Teaching Assistants will pick a pair who will explain a solution to their lab mates following the design recipe steps.

Descendant Trees

30 minutes

An alternative approach to representing family relations is using a Descendant Tree. Instead of referring to its ancestors, each person includes a list of descendants.

(define-struct person [name title children])
; A DescendantTree (DT) is a
;    (make-person String [Maybe String] [List-of DescendantTree])
; interpretation name is the person's name,
; title the title of a person relative to an ancestor, in the
;   form "2nd" or "3rd" etc. Note there is no "1st".
;   It indicates how many ancestors have previously had the
;   same name as thus person.
; children are the direct first-degree descendants,
;   listed from youngest to oldest child

Often times, families will name their children in honor of another family member, like a grandfather, an uncle or the parents themselves.

You may know that Fundamentals I is occasionally taught by the famous Professor Olin Shivers III, PhD. As you can tell, he is named after his father, Dr. Olin Shivers II, who in turn received his name from the original, Olin Shivers I. What you may not know is that Prof. Shivers has named his son Olin Shivers IV, and you can guess what the latter called his first born.

When checking for repeated ancestor names, don’t forget the strange parents that decide to give all their children the same name. I personally know three siblings with the same first name.

Exercise 2 Design a function, add-titles, that given a DescendantTree, fills in the title field of each direct and distant descendant appropriately (relative to the given one of course). Titles should be in the format: "3rd of Their Name" or "6th of Their Name", using the correct ordinal number in each case.

Code Review

20 minutes

The Teaching Assistants will pick a pair who will explain a solution to their lab mates following the design recipe steps.