2.16 More on Hierarchies
Look at this code
Isn’t it neat?
Wouldn’t you think my data structures’re complete?
Wouldn’t you think I’m the girl
The girl who knows everything?
Look at this class
Functions: they fold
How many wonders can one template hold?
Looking around here you think
Sure, she’s knows everything
I’ve got compunds and mixed a-plenty
I’ve got lists and trees galore
You want DFTs?
I’ve got twenty!
But who cares?
No big deal
I want more
I wanna be the programmers are
I wanna see, wanna see them typin’
Using that —
what do you call it? Oh - co-inductive & cyclical data!
Countin’ your fingers, you don’t get too far
Co-induction’s required for lots of things
Like travering a —
what’s that word again? Stream
Up where they cycle, up where they unfold
Up where they stay all day in the lab
Typin’ away - wish I could be
Part of that world
What would I give if I could live out of 142?
What would I pay to spend a day in 240?
Bet’cha in there they understand
That they don’t reprimand their daughters
Proper women sick of design
Ready to stand
And ready to know what the programmers know
Ask ’em my questions and get some answers
What’s mutation and why does it - what’s the word?
Stink?
When’s it my turn?
Wouldn’t I love, love to explore that code up above?
Out of 142
Wish I could be
Part of that world
2.16.1 Objectives
that the data definition for a descendant family tree (a variable-width tree) requires two data definitions that refer to each other (mutually recursive data definitions).
write the data definition for a descendant family tree.
write functions over descendant family trees.
2.16.2 Exercises (due 2011/11/14 08:45:00)
1. Write a function called dyeGeneration that takes a parent, a generation number, and an eye color and produces a parent where everyone in the given generation’s eyes are the given color.
2. Add a boolean to the information about people that encodes if the person is living. Write a function called living that takes a parent and returns a list of info about all living descendants.
3. Write a function called birth that takes a parent object, the name of a descendant, and information about a new person. The function should return an updated family tree where the named descendant (assume there is only one) has a new descendant (with no children) specified by the given information.
4. Write a function called line that takes a list of information about people and returns a family tree where each person in the list is the ancestor of everyone to their right. (For example, the list The Boss:Big Boss:Solidus:Raiden would construct a portion of the Metal Gear trained-by family tree.)
2.16.3 Optional Exercises (due 2011/11/18 08:45:00)
5. Modify people so that rather than a boolean living attribute there is a status string that may be living, dead, or undead. Modify the function living to accomodate this new data structure.
6. Write a function called death that takes a parent and a name and returns a family tree where the named person is marked as non-living.
2.16.4 Practice Exercises
7. Write a function averageLifespan that takes a parent and returns the average age of dead descendants. (Their age is, of course, their last living age.)
8. Write a new function called vampires that returns all undead descdenents.
9. Generalize living and vampires so the status string is specified in an argument.
2.16.5 Notes
These notes are primarily for my sake, but I don’t see any reason to hide them from you.
See previous day. |
|
*** Talk about co-inductive and transfinite structures |