Held: Tuesday, 4 November 2014

Back to Outline 34 - Iteration. On to Outline 36 - Trees.

Summary

We consider pairs, the basic data type used to build lists and other structures in Scheme. We also consider why it is useful to understand about pairs.

Related Pages

• Reading: Pairs and Pair Structures
• Lab: Pairs and Pair Structures
• EBoard 35 (Source 35) (HTML 35)

Overview

• Representing lists: Pairs and cons cells.
• Why care about the underlying representation?

Administrivia

• New partners (provided I find all of the cards)!
• Extended/modified office hours continue this week and next.
  • Survey: Should I switch to online signup for office hours? (Choices are "Please have online signup" and "Please keep physical signup". You may also choose not to vote.)
• I've been answering a variety of prereg questions. Feel free to continue asking such questions.

Upcoming Work

• No lab writeup! (Two days in a row. What's wrong with me?)
• Reading for Wednesday: Trees
• Homework 6, due tonight.
• Exam 3, distributed tomorrow, due the following Tuesday.

Cool Upcoming Events on Campus

• Peace studies talk Monday Nov. 10 at 4:15 p.m. in JRC 101 "With All the World’s Violence, Where is Peace?"

Extra Credit Opportunities

Academic

• CS Extra Thursday: Study-Abroad Opportunities with a CS Component 4:30 p.m., Science 3821.
• CS Table Friday: Open Data. 12:10-12:50, Day PDR.

Peer Support

• Karan's radio show 11pm Thursday nights on KDIC
• Evan's radio show 5pm Friday nights on KDIC
• Donna's radio show Sunday midnight on KDIC
• Swimming on Saturday (sometime) against Luther.
• The gaming club is hosting a Smash Brothers tournament on Saturday (Loose at 11am ...) (And thats "Loose", not "Lose")

Cons Cells

• One set of interesting values in Scheme are the things that cons creates. We often call these cons cells or pairs
• The first value of a pair is a reference to the first parameter to cons.
  The second value is a reference to the second parameter.
• I'll also draw some pictures of these things in class.

Dotted Pairs

• Although we've used lists as the second parts of each cons cell, you can use other values. If the second part of a cons cell is not a list, you get what is called a dotted pair.
• The shorthand for a dotted pair is '(x . y).
• You'll also see the dot at the end of a long sequence of cons cells.
• Why is the dot there?
  
  • To distinguish things close to lists from lists.
• Why is it right before the last element, and not earlier?
  
  • Because we don't know until we hit the end that it's not a list.

Why Care?

• Why should we care about the underlying structure used for lists?
• Because it helps explain why Scheme does some things the way it does.
• Because it helps us understand the hidden costs associated with some operations.
• Because it helps us better understand recursion over lists.
• Because it provides background for future discussions.

Lab

• Any preliminary questions?
• Do the labthe lab.
• Be prepared to reflect.