Class 37: Pairs and Pair Structures

This outline is also available in PDF.

Held: Friday, 6 November 2009

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:

Notes:

You have a writeup on today's lab.
Are there questions on Assignment 7?
Quiz 8 (finally) returned.
We'll go over the palette-darken! procedure from the lab on vectors.
Are there pre-quiz questions on topics from the last week (randomness, vectors, strings, geometric art, ...)?
When you finish the quiz, start the lab.
Reading for Monday: Trees. (The reading may be updated over the weekend.)

Overview:

Pairs and cons cells.
Why care?
Lab.

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 questions?
Do the lab (preferably in pairs :-).
Be prepared to reflect.

Back to Vectors. On to Trees.

[Skip to Body]
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.02 2009S (Weinman)] [CSC151.02 2009S (Davis)] [CSC151 2008S (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri Dec 11 09:38:48 2009.
The source to the document was last modified on Fri Aug 21 17:03:06 2009.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2009F/Outlines/outline.37.html.

You may wish to validate this document's HTML ; ;

Samuel A. Rebelsky, rebelsky@grinnell.edu

Copyright © 2007-9 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.) This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc/2.5/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.