10 Designing with Accumulators

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

Introduction

5 minutes

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.