Lab 2: Contact List
Goal: review lists, abstract data types, and for each; develop deeper understanding of abstract data types (if we keep display and sorting form selectors)
Computers manipulate data and return processed information to the user. Numbers, strings of characters (letters, numbers, symbols, etc.), and Boolean values (true, false) are some of the basic pieces of information. Often, these small pieces are arranged in more complex structures: lists, ordered sets of data.
A list is not just a collection (set) but also a collection in a particular order (this order is tracked by an index number for each item on the list). If it has any elements at all, it has a first element, a last element, and so on. A list can also be totally empty, with no elements; often that is the way we want to set up (initialize) a list before we add elements to it. The length of an empty list is 0.
Lists are powerful. Databases are lists of lists of lists. Many operations can be performed on data in a list:
- Functional programming:
- Searching a list to see if it
contains some element.
- Creating new lists that
keep only certain items from a list you started with.
- You can create new lists with more or fewer elements than the list you have.
- You can pick an
item of a list by position or characteristic or just randomly.
- Imperative programming:
- Modifying lists to
add, delete, or replace items, or to insert an item in a specific spot.
- You can do something with each item of the list: you can process it in some way, or
for each element of the list, you can display it in some way.
Lists can contain anything: numbers, strings, other lists, even blocks. The objects in a list can be all of the same kind (all numbers, for example, or all lists that contain a name and a phone number) but they do not have to be. A list can, for example, contain an apartment number and a list of people at that address. The tabular data we are familiar with in spreadsheets can be represented as a list of same-length lists, the smaller lists representing each row in the table, and the enclosing list representing the entire spreadsheet.
In this lab, students construct a contact list app. The list's elements are themselves lists. This requires not only collecting and storing information, but being able to retrieve it in useful ways.
Pacing
The 4 required lab pages could be split across 2–4 days (
85–170 minutes). Expected times to complete follow:
Prepare
- This unit relies on prior learning about lists from Units 1 and 2. You may want to have students revisit the self-check quizzes in Unit 2 Lab 2 and discuss any questions students have about the List blocks used in that lab.
A Few General Tips:
Some of this (e.g., the first bullet) is explained in the student text. Is that OK? --MF, 7/3/20
- The words "item" and "element" have the same meaning. We use "item" here because that's the name of the block that examines an item in a list. You may want to favor that word, too.
- In Snap!, the first item of a list is considered item number 1, not number 0 as in some other languages. We think this is clearly advantageous for learners: "the third item" and "item 3" should refer to the same thing. Zero-origin list indexing is a leftover from low-level languages that do arithmetic on array indices. It's fine if some student thinks zero-origin is "right," but feel free also to say that one design goal of computer language is to be clear, and this language (Snap!) is designed so that ordinals (first, second, third) and cardinals (1, 2, 3) match.
- We are encouraging functional programming style, which in this case means favoring the list reporters (which report a new list) over the list commands (which change, or "mutate," the original list). Make sure that students understand, for example, that
all but first of makes a new list; the original list given as its input is not modified.
-
One advantage of functional programming is that it avoids circular structures, which can be made by mutation:
This won't come up in the curriculum, but some students may try it anyway. It won't break Snap!, but if it comes up, encourage such students to play with circularity on their own time.
Lab Pages
-
Page 1: Creating the Contact ADT.
-
Learning Goals:
- Create, initialize, and use a variable for storing a list.
- Use nested list data structures to create abstract data types, which let a user deal with data without having to know the details of how the data are stored and accessed.
- Notice the difference between returning a string (or a number) and returning a list—especially when that list contains only one item that is a string or a number.
- Discussion Questions:
- What kinds of things can you do with a list of lists?
- Do the lists inside a list need to be the same size?
- In what other situations might a list of lists be helpful?
-
Tips:
- Opener: Present a short script in which a list is used without having first been initialized, resulting in an error. Ask students: What might have caused the error? What is the proper way to address this issue?
- After most students have completed this page, you may wish to pause to review what an abstract data type is and the role of both constructor and selector.
-
The reference to Unit 2 Lab 2 Page 2: Planning a Quiz App in the Thinking Out Loud dialog is designed to stimulate thinking about the
contact ADT. For students who struggle to develop the contact constructor and selectors, suggest they look back at that lab, and ask them some questions like these:
- What's the structure of the
quiz item constructor? How is it used? What will the contact constructor look like? What does it need to report?
- What do the
question and answer selectors do? What will the selectors look like in Contact List?
- "Abstract data type" (or ADT) sounds like a complicated thing, but programmers actually use them to simplify and clarify the logical structure of their code. It is a thing to help people, not machines. An abstract data type is like a "template" for data—for example, a registration form on which individuals write their name, address, email, etc., in a particular place helps us know where to look for each part of the data. Such a definition consists of one (occasionally more) constructor block, and several selector blocks. Constructors create an instance of the data type; selectors pull out pieces from such an instance. Once the ADT is set up and is consistently used by the rest of the program, it's possible to change the internal representation without breaking anything other than the constructor and selectors.
-
Page 2: Adding Contact Data.
- Learning Goal: Write scripts for user interface buttons that control items in a contact list.
-
Tips:
- There are four button-sprites in the starter file, but only 3 are visible—the two that students program on this page ("Add Contact" and "Clear List") and the one they program on the next page ("Find Contact"). The fourth ("Delete Contact") is left as an optional exercise at the end of page 3.
-
Page 3: Adding Birthdays.
- Learning Goal: Develop and use nested abstract data types.
-
Tips:
- The selectors require students to think carefully about accessing items within lists of lists, offering opportunity for them to practice working in these structures and motivating the use of abstract data types.
-
Page 4: Selecting Specific Data.
-
Learning Goals:
- Use the
keep function to filter lists according to particular constraints.
-
Discussion: You may wish to review different types of data in Snap!: strings, lists, Booleans, numbers, functions, etc...
- What is is the difference between a string and a list? (Students without prior programming experience may wonder, "what's the same between a string and a list?" The answer is that they're both aggregates. A string is an aggregate whose items are restricted to single characters; a list is an aggregate whose items can be anything.)
- What actions can you perform on a list? What can you use lists for? (Actions might be "add an item" or "order the items"; project ideas might be "track earnings and expenses" or "organize sports data.")
- What data types can be list items? Invite students to experiment with Snap! to answer this question and to consider contexts for which including various data types in a list would be useful. (A list can contain any data type anywhere. Students will have seen only a limited set of values at this point.)
- Can you put a list in a list? (Yes, any data type anywhere.) What are some examples of a list within a list? (Students may not have examples just yet.) This is both a preview of the next lab, "Nesting Lists," and also an introduction to the idea that nesting computational objects is common in programming.
-
Tips:
- Programming a "Delete Contact" button is an If There Is Time exercise. Students are directed to move the button onto the stage and are left to figure out as an exercise in debugging how to recover "missing" sprites. There are many ways to do this, but one simple method is to change the x-coordinate of the
go to block in the sprite's script from 1500 to 150.
-
Page 5: Transforming Every List Item.
- Learning Goal: Use the
map block to apply procedures to every element in a list.
-
Tips:
- The
map block will be used more in upcoming labs. Here, students just learn the basics. Like keep and for each, the map block is a powerful higher-order function, and it will be used periodically throughout the remainder of the course. However, these functions are not required by the AP CSP Framework.
Solutions
Correlation with 2020 AP CS Principles Framework
Computational Thinking Practices: Skills
- 3.A: Generalize data sources through variables.
- 3.C: Explain how abstraction manages complexity.
Learning Objectives:
- CRD-2.C: Identify input(s) to a program. (3.A)
- CRD-2.D: Identify output(s) produced by a program. (3.A)
-
AAP-1.D: For data abstraction:
- Explain how the use of data abstraction manages complexity in program code. (3.C)
Essential Knowledge:
- CRD-2.C.1: Program input is data sent to a computer for processing by a program. Input can come in a variety of forms, such as tactile, audio, visual, or text.
- CRD-2.C.4: Inputs usually affect the output produced by a program.
- CRD-2.C.6: Input can come from a user or other programs.
- CRD-2.D.1: Program output is any data sent from a program to a device. Program output can come in a variety of forms, such as tactile, audio, visual, or text.
- CRD-2.D.2: Program output is usually based on a program’s input or prior state (e.g., internal values).
- DAT-2.D.3: Search tools are useful for efficiently finding information.
- AAP-1.D.5: Data abstractions often contain different types of elements.
- AAP-3.B.2: Procedural abstraction allows a solution to a large problem to be based on the solution of smaller subproblems. This is accomplished by creating procedures to solve each of the subproblems.
- AAP-3.B.3: The subdivision of a computer program into separate subprograms is called modularity.