CSC151.01 2015S, Class 37: Trees ================================ * Continue Partners! _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Questions. * Debrief from yesterday. * How Scheme prints lists. * The `listp?` predicate. * Drawing trees vs. drawing lists. * Lab. Preliminaries ------------- ### Admin * Random sugar. * Homework grades coming soon! ### Upcoming Work * Lab writeup (optional): Exercises 2 and 4a. * Reading for Wednesday: [Vectors](../readings/vectors-reading.html) * HW7 due tonight at 10:30 p.m. * Exam 3 available now, officially distributed tomorrow. ### Extra Credit Opportunities #### Academic * Joe Palca talk Tuesday at 7:30 p.m. in Sebring-Lewis. * Scholars Convocation Wednesday at noon: Alison Bechdel. * CS Extras Thursday: ??? * CS Table Friday: Design for User Empowerment #### Peer Support (Afternoon Section) * Wednesday at 4:30 in ???. Psychology Alumni Job Talk Series, Alum '##, a Senior Research Analyst from ACT. * Womens Tennis Sunday against Central. * ISO Show, Saturday night 7-9 pm at Harris. Many live performances. * How an admitted student this coming Sunday night (or the following Sunday night)! Contact JMU for info. * Many things the following weeks. #### Miscellaneous _Nothing at present_ ### Other Good Things (no extra credit) * Student research seminar this week. ### Questions Debrief from yesterday ---------------------- What should we take from yesterday's lab? * We build things with pairs. * Lists * Trees (two-dimensional lists?) * Other things that have no clear name. * There is a close relationship between lists and pairs. * All non-empty lists are pairs * Null is a list, but not a pair * Not all pairs are lists; only a pair whose cdr is a list is a list * Sequences of pairs don't need to end with a null, but sequences of pairs that represent a list do need to end with a null. * We can provide unambiguous drawings of pair structures using a simple process. * For each cons, draw a pair of boxes * If an element is not null, draw that element separately and draw an arrow to it. Traditionally, the arrow from the left box goes downward and the arrow from the right box goes to the right * If an element is null, draw a slash in the box * We can turn these drawings back into code. * A list with N elements has a "spine" of N pairs. * N elements means N boxpairs * One boxpair per element Why are we studying this? * There is some value in understanding what a program or langauge does "behind the scenes". * Understanding the underlying representation can help you better explain some phenomena. * We will start building some pair structures that aren't lists, so you should know more about those structures. * Linked structures are a fundamental idea in CS. How Scheme prints lists ----------------------- Print If you have a pair print a single quotation mark print an open parentheis print the car move on to the cdr ^ if the cdr is null | print a close paren and stop | if the cdr is a pair | print a space | print the car +---+ loop back and do it all over again | otherwise | print a space | print a curse | print a space | print the cdr | print a right paren Writing `listp?` ---------------- Write a procedure, `(listp? val)` that returns #t if val is a list and #f otherwise. Reminder: A list is null or (cons VAL LIST) (define listp? (lambda (val) (or (null? val) (and (pair? val) (listp? (cdr val)))))) Drawing trees vs. drawing lists ------------------------------- Lab ---