Unit 2Introduction to Data Structures
Unit Overview

Students discover the need for compound date - data structures - using 2-dimentionsal animation. They learn the syntax for data blocks, constructors and dot-accessors, and practice each by creating a "digital bakery".

Product Outcomes:
• Students identify real-world behaviors that require data structures

• Students make use of a complex data structure: Cake

• Students define variables bound to Cakes

• Students will generalize their understanding of function constructors and accessors

• Students write code that extracts each field from those Cakes

• Students will write functions that access fields of a CakeT

Standards and Evidence Statements:

Standards with prefix BS are specific to Bootstrap; others are from the Common Core. Mouse over each standard to see its corresponding evidence statements. Our Standards Document shows which units cover each standard.

• BS-DR.1: The student is able to translate a word problem into a Contract and Purpose Statement

• given a word problem, identify the domain and range of a function

• given a word problem, write a Purpose Statement (i.e. - rewrite the problem in their own words)

• BS-DR.2: The student can derive test cases for a given contract and purpose statement

• given a Contract and a Purpose Statement, write multiple examples or test cases

• given multiple examples, identify patterns in order to label and name the variables

• BS-DR.3: Given multiple test cases, the student can define a function

• given examples and labeled variable(s), define the function

• BS-DR.4: The student can solve word problems that involve data structures

• write examples for a function that prodiuces a data structure

• write functions that produce data structures

• BS-DS.1: The student is able to read data blocks

• given a data block, create instances of the data structure

• given a data block, use dot-accessors to access fields of the data structure

• BS-DS.2: The student is able to solve problems using data structures

• identify problems that require use of a data structure

• BS-IDE: The student is familiar with using a REPL, entering expressions properly, and interpreting error messages

• enter and evaluate expressions on the computer

• BS-M: The student models a problem in context and determines the data needed to describe the problem

• identifying which quantities are fixed and which are variable

• identifying the datatype of a given quantity, in context

• BS-PL.1: The student is familiar with declaring values and applying built-in functions using the programming language

• representing (numeric, string, boolean, or image) values in the programming language

• BS-PL.3: The student is able to use the syntax of the programming language to define values and functions

• defining and using functions

Length: 120 minutes
Glossary:
• calling: Using a function by giving it inputs

• constructor: A function that creates instances of a data structure

• contract: a statement of the name, domain, and range of a function

• data structure: A datatype which packages several datatypes as fields

• data type: A way of classifying values, such as: Number, String, Image, Boolean, or any user-defined data structure

• domain: the type of data that a function expects

• dot-accessors: A way to extract the values of fields an instance

• field: A part of a data structure that has a name and holds a single value of a specified datatype

• instance: A specific, packaged value of a data structure that contains other values in its fields.

• name: how we refer to a function or value defined in a language (examples: +, *, star, circle)

• purpose statement: a brief description of what a function does

• range: the type of data that a function produces

• variable: something that changes

Materials:
• Pens/pencils for students, fresh whiteboard markers for teachers

• Class poster (List of rules, language table, course calendar)

• Language Table (see below)

• Student Workbook folders with names on covers, and something to write with

Preparation:
• Write Agenda on board

• Display class posters, Language Table, Design Recipe

• The Parachute Jumper file preloaded on student machines

• The Bakery file preloaded on students’ machines

 Types Functions Number + - * / num-sqr num-sqrt String string-append string-length Image rectangle circle triangle ellipse star text

Review

Overview

Learning Objectives

• Students will deepen their understanding of function definitions and the Design Recipe

Evidence Statements

Product Outcomes

Materials

• Pens/pencils for students, fresh whiteboard markers for teachers

• Class poster (List of rules, language table, course calendar)

• Language Table (see below)

• Student Workbook folders with names on covers, and something to write with

Preparation

• Write Agenda on board

• Display class posters, Language Table, Design Recipe

Review (Time 15 minutes)

• In the previous unit, you reviewed almost everything from Bootstrap:1 including Datatypes, Contracts, and the Design Recipe. In this unit you will go above and beyond all that, and learn an entirely new construct that will be the basis for everything you’ll do in Bootstrap:2.

Ask a few introductory review questions to test students’ understanding:

• What are the three parts of a Contract?

• What is the Pyret code to draw a solid, green triangle of size 22?

• Why is it important to write at least 2 examples before defining a function?

• To make sure the material from the previous unit is fresh in your mind, tackle the following activity:

Turn to Page 8 in your workbook. Write a function called double-radius, which takes in a radius and a color. It produces an outlined circle of whatever color was passed in, with radius twice as big as the input.

If walking through this example as a class, use a projector so kids can see the function being written on the computer.

• Remember how to use the design recipe to work through word problems?
• What is the Name of this function? How do you know?

• How many inputs does it have in its Domain?

• What kind of data is the Domain?

• What is the Range of this function?

• What does this function do? Write a Purpose Statement describing what the function does in plain English.

Review the purpose of Contracts: once we know the Name, Domain, and Range of a function, it’s easy to write examples using those datatypes.

• Using only the Contract and Purpose Statement, see if you can answer the following questions:

• Every example begins with the name of the function. Where could you find the name of the function?

• Every example has to include sample inputs. Where could you find out how many inputs this function needs, and what type(s) they are?

• Every example has to include an expression for what the function should do when given an input. Where could you look to find out what this function does?

• Write two examples on your paper, then circle and label what is changing between them. When labeling, think about what the changing things represent.

Don’t forget to include the lines examples: and end! Your examples should look similar to:

Each one of these answers can be found in the Contract or Purpose Statement. Suggestion: Write these steps on the board, and draw arrows between them to highlight the process. The goal here is to get students into the habit of asking themselves these questions each time they write examples, and then using their own work from the previous step to find the answers.

• Once you know what is changing between our two examples, you can define the function easily. The things that were circled and labeled in the examples will be replaced with variables in the function definition.

Underneath your examples, copy everything that doesn’t change, and replace the changing things with the variable names you used. (Don’t forget to add the fun and end keywords, as well as the colon (:) after the function header!)

For more practice, turn to Page 9 in your workbook and complete the Design Recipe for the double-width function.

Check students understanding: Why do we use variables in place of specific values? Why is it important to have descriptive variable names, as opposed to n or x? Remind students about nested functions: A function whose range is a number can be used inside of a function requiring a number in its domain, as in circle(2 * 25, "outline", "red").

Introducing Structures

Overview

Learning Objectives

• Students will understand the limitations of atomic datatypes

Evidence Statements

Product Outcomes

• Students identify real-world behaviors that require data structures

Materials

Preparation

Introducing Structures (Time 30 minutes)

• Open the Parachute Jumper file on your computer and press ’Run’. What happens?

The parachute jumper jumps out of the airplane and falls straight down, into the water! It’s much safer to land on the shore. Let’s take a look at the code to see why he falls into the water instead. There are a few new concepts in this file, but first, let’s focus on what you already know.

Look at the function defined here called next-position.

• What is this function’s Domain? Its Range?

• What does next-position do with its inputs?

This function takes in two numbers, representing the x and y coordinate of the parachute jumper, but it changes and returns only the y-coordinate, by subtracting 5 from it. But if only the y-coordinate is changing, he’ll always fall straight down, landing in the water every time. To reach the land, he’ll have to fall diagonally. How could we make that happen?

How should the jumper’s x-coordinate change if he moves diagonally to the right (toward the land)? How should his y-coordinate change?

• Functions can return only one thing at a time, but we need to return both an x and a y-coordinate in order to make the jumper move diagonally. Thankfully, we have a way to combine multiple things within one container, called a Data Structure. Just like Racket and Pyret have built-in functions and also let you define your own functions, these languages allow you to create your own data structures as well. For this project, we’ve created a structure for you to use called JumperState, which contains two Numbers, representing an x and a y-coordinate.

Look at line 6, where we’ve defined JumperState. We’ll go through the new syntax for defining a data structure, because very soon you’ll be defining brand new structures of your own!

• First, we’ve written a comment to remind ourselves what we’re creating. In this case, we’re calling our new structure JumperState, which contains two numbers: an x and y-coordinate.

• The next line begins with data JumperState:. Similar to the keyword fun you learned in the last lesson, data tells the computer that you’re about to define a new type of data. This is a very powerful piece of code: In Bootstrap:1, you wrote programs using four data types: Numbers, Strings, Images, and Booleans. In this course, now you can create brand new data types. We can use these data types to create complex animations, multi-player video games, or account for both coordinates of a parachute jumper, so he moves in 2-dimensions! We called this data type JumperState, because it represents the current state, or position, of the parachute jumper. Pyret would let us write any name after data, but as a convention, the name of a new data structure is capitalized, and we choose a meaningful name for it.

• The next line begins with the | symbol, sometimes called a "bar" or "pipe", followed by the name of the constructor function for the structure (in this case, jumper.) A constructor function is similar to some functions you’ve seen before, for creating images. To create an Image, we call the function that creates it: rectangle, triangle, square, etc. Similarly, to create a JumperState, we can use the jumper constructor function with its inputs (two numbers, called x and y). Again, the names JumperState and jumper were chosen by us, the programmer, and putting them in a data definition makes them available as a new data type and as a constructor function.

Let’s get back to constructing a jumper, specifically how we knew the inputs would be numbers. The block of code we’ve given you defines all of this!

tells us that we’re defining a new data type called JumperState, whose constructor function jumper takes in two things: x, which is a Number, and y, which is also a number. Once we’ve listed each input and its data type, we finish defining the structure with the end keyword, just like finishing an example block.

This is the first data block students see in this course, but they will soon be writing their own to create new data structures. It’s worth spending the time to cover this new syntax, paying special attention to capitalization (the name of the structure is capitalized (JumperState), whereas its constructor function (jumper) is lowercase), double colons (::) before data types, and commas between inputs to the constructor function.

• Now it’s up to us to protect this parachute jumper, and make sure he lands safely on the shore.

Turn to Page 10 in your workbook, read the word problem, and fill in the Contract and Purpose Statement for the function next-position.

Point out that we’re now using a new data type in a contract: next-position consumes two Numbers, and produces a JumperState. Once we’ve defined a new data structure using the above data block, we can use it just like other datatypes.

• Now for our two examples. Using, or calling next-position with two numbers is easy, but what happens to those numbers? We can’t return both at the same time... unless we use a data structure! To do so we’ll need to use the constructor function to make a structure from the data we already have.
• According to the definition for JumperState, what function makes a JumperState? What is its contract?

• # jumper : Number Number -> JumperState

• What two things are part of a JumperState? Do we have values for those things as part of our first example?

• We don’t want our JumperState to contain the same x and y values we gave the next-position function. How will the values change? (Remember to show your work!)

• Your first example should look something like:

• Once your first example is complete, write one more example with different inputs for the x and y coordinates.

Remind students to show every step of their work in the example step of the design recipe: if the x-coordinate increases by 5 while the y-coordinate decreases by 5, they should show the addition and subtraction within the JumperState data structure, instead of just returning the new numbers.

• Now that you have two examples, it’s time to define the function. You know the drill: circle and label everything that changes between your two examples, copy everything that stays the same, and replace the changing things with the variables you chose.

When you finish, your function definition should look like:   Now, instead of just changing and returning one number (a y-coordinate), we can return both the x and y-coordinates of the parachute jumper within a Data Structure.

Open the Parachute Jumper code again and replace the original next-position function with the one in your workbook to make the parachute jumper land safely on the shore! Don’t forget to change the given examples to match your new function definition.

• In Bootstrap:1, a function could return only one value: either a Number, String, Image, or Boolean. In Bootstrap:2, our functions will still return one value, but that value can be a Data Structure, (or just "structure" for short) containing any number of things within it. This way we could return both the x and y-coordinate of a player using a JumperState, or create new structures and return even more detail about a player, like their health, position, amount of armor, or inventory.

In Bootstrap:1, students’ games were made by keeping track of just a few numbers: the x-positions of the danger and target, and y-position of the player. In Bootstrap:2, students’ games will be much more complex, and will require many more values to move characters, test conditions, keep track of the score, etc. Data structures simplify code by organizing multiple values: You couldn’t represent every part of a player (position, health, inventory, etc.) with one number or string, but you can refer to all these things collectively with a data structure. This way, we can have one value (a data structure) containing multiple other values that can be accessed individually.

Cakes

Overview

Learning Objectives

Evidence Statements

Product Outcomes

• Students make use of a complex data structure: Cake

• Students define variables bound to Cakes

• Students will generalize their understanding of function constructors and accessors

Materials

Preparation

• The Bakery file preloaded on students’ machines

Cakes (Time 30 minutes)

• Suppose you own a famous bakery. You bake things like cookies, pastries, and tarts, but you’re especially known for your world-famous cakes. What type of thing is a cake? Is it a number? String? Image? Boolean? You couldn’t describe all of the important things about a cake with any one of those data types. However, we could say that we care about a couple of details about each cake, each of which can be described with the types we already know.

For each of the following aspects of a cake, think about what datatype you might use to represent it:

• The flavor of the cake. That could be "Chocolate", "Strawberry", "Red Velvet", or something else.

• The number of layers

• Whether or not the cake is an ice cream cake.

What datatype could we use to represent the entire cake?

Now that we know everything that is part of a cake, we can use a data structure to represent the cake itself. Let’s take a look at how this works.

Open your workbook to Page 11.

On this page, we will define a data structure for cakes, which we call CakeT (T for "type"). At the top of this page we see a comment, stating what things are part of a CakeT. Below that is a line that says data CakeT:, which begins the definition of a new data structure, called CakeT. On the next line, we define the function that makes a CakeT (cake), and how exactly to make a CakeT—the names of each thing in a CakeT, and their data types. Each piece of information that makes up a cake (the flavor, etc) is called a field. A field has both a descriptive name (like flavor) and a datatype.

What name describes the first field in a CakeT? What data type can we use to represent it?

There is a little bit of new syntax involved in defining structures. On the first line on Page 11, we write flavor :: String,, which tells Pyret that the first element of any CakeT will be its flavor, represented by a String. This line shows how to define one field in a data structure.

What name describes the second field in a CakeT? What data type can we use to represent it?

On the next line, write layers :: Number,, which tells Pyret that the second element of any CakeT will be its number of layers, represented by a Number.

What data structure should we use to represent whether or not the CakeT is an ice cream cake? Use this to define another field.

On your paper, you should have:   This is the code that defines the CakeT data structure. It tells the computer what a CakeT is and what goes into it. It also defines its constructor function, called cake. To make a CakeT, you must call the constructor function with three things: a flavor, which is a String, layers, a Number, and is-iceCream, which is a Boolean. Remember that order matters! For now, these are the only things that we’re going to keep track of in a CakeT, but you can imagine how you might extend it to include other information.

Stress the importance of being able to define your own datatypes to students: no longer are they bound by the single values of numbers, strings, or booleans! Pyret allows you to define brand new Data Structures, containing any combination of values.

• Open the Bakery file and look at lines 3 - 8. Do they match what you have on your paper?

Now take a look farther down, at line 10: birthday-cake = cake("Vanilla", 4, false)

• What is the name of this variable?

• What is the flavor of birthday-cake?

• How many layers does birthday-cake have?

• Finally, is birthday-cake an ice cream cake, or not?

Below the data definition for CakeT there are four CakeTs defined and assigned to the variables birthday-cake, chocolate-cake, strawberry-cake, and red-velvet-cake. Ask students questions about these CakeTs to get them thinking about how they would define their own.

• On line 14, define another CakeT, which you can name however you like (but choose something descriptive, like pb-cake, lemon-cake, etc.) To start,

• how would you define this variable?

• What function is used to make a Cake?

• Which thing comes first in a Cake structure?

Now what do you expect to happen when you type the name of your new CakeT into the interactions area? Click ’Run’ and try it out.

pb-cake = cake("Peanut Butter", 2, true)

Have students walk you through the process of defining a new value and making a CakeT with whatever flavor, etc. they like.

• Define two new values for some of your favorite cakes. You can give them whatever names you prefer. You can make any kind of CakeTs that you want, as long as your structure has the right types in the right orders!

Repetition is key in this lesson. Have students identify each part of the CakeT for every CakeT they’ve defined. What is the flavor of their first CakeT? Its number of layers? Ensure that students are using their inputs in the right order!

• At this point, you’ve worked with two different Data Structures: JumperStates and CakeTs, and you’ve created different examples, or instances, of these structures. Instances are concrete uses of a datatype, just as 3 is a concrete Number (where Number is the type). Here, CakeT is the type, and cake("Chocolate", 8, false) is a concrete cake with specific values for each field. In programming, we create instances much more often than we create new data structures. For now, the important point is to recognize the difference between a structure definition (the data.... piece of code) and specific instances of a data structure (like birthday-cake, or jumper(44, 75).

Students often struggle with the difference between the definition of a data structure and instances (items created from) a data structure. When students define CakeT, they haven’t created any specific cakes. They have defined a type that they can use to define specific cakes. If they have a specific cake, they can ask questions of it such as "is this a chocolate cake?" and produce an answer. If all they have is the CakeT definition, they can’t answer such questions. Some people like the analogy of a cookie cutter here – CakeT defines a cookie cutter, but doesn’t produce any cookies. To get a cookie, you use the cake constructor to define a specific cake with specific values for the fields.

• Based on these instances of CakeTs you just wrote:
• What is the name of the function that creates a CakeT?

• What is the Domain of this function?

• How many things are in the domain?

The three things in the domain of cake are, in fact, the three things that we have already listed on Page 11! With data structures, the order is very important: we always want the first string in cake to be the CakeT’s flavor, the first number to be its number of layers, etc.

CakeTs are the first example of defining a new datatype that students will see, but Pyret allows you to define any number of new data structures to hold any combination of values. The important points to remember about creating structures at this point is that whenever the constructor function is called (in this case, cake), it must take in the same number and type of values as in the structure’s definition, and its inputs must be in the same order as the definition.

• After clicking the "Run" button, in Pyret, type birthday-cake into the interactions area and hit enter. What do you get back?

Does this make sense? What happens when you type just a number into the interactions area? We get that same number back! What about Strings? Images? Booleans? If we don’t do anything to our input, or use any function on it, we get back exactly what we put in! Here, you put in a CakeT, let’s see what we get back. At first glance, it looks like a function call was the answer! But there’s a few things different about what appears in the output. First, it isn’t the same color as a normal function call, which is the first hint that something’s different. Second, we can click on it, and see that this value is storing three other values in its fields – the flavor, layers, and whether or not it’s ice cream. This compound value that’s printed is an instance of a CakeT. It’s a value in its own right, so when we type in birthday-cake it shows us this value (just like with numbers and strings).

Remind students that values will always evaluate to themselves. 4 evaluates to 4, the string "pizza" evaluates to "pizza", and birthday-cake evaluates to cake("Vanilla", 4, false)

Dot-Accessors

Overview

Learning Objectives

Evidence Statements

Product Outcomes

• Students write code that extracts each field from those Cakes

Materials

Preparation

Dot-Accessors (Time 10 minutes)

• Suppose you want to get the flavor out of chocolate-cake. You don’t care about the message, color, or anything else - you just want to know the flavor. Pyret has syntax for doing precisely that: .flavor.

If you type chocolate-cake.flavor into the interactions area, what should it evaluate to? Try it out!

• What kind of thing did it return: A Number, String, Image, Boolean, or structure?

• Practice taking the flavor out of every CakeT you have defined, using .flavor

Of course, there are ways to access any part of a CakeT, not just the flavor! What do you think you would get if you typed chocolate-cake.layers in the interactions area?

Try using the dot-accessors .layers and .is-iceCream on your CakeTs! Do they do what you expect?

A way to prompt students to use these accessors is to ask: "How do you get the flavor out of a CakeT?" or "How do you get the layers out of a CakeT?" Throughout the course you can set up a call and response system with students, where the question "How do you get the X out of a Y?" will prompt the name of the accessor.

• The previous syntax is known as Dot-Accessors. They allow you to specify exactly what part of a structure you want. If we want to know if we can fit a certain CakeT through a doorway, we probably care only whether the number of layers is less than a certain amount. Likewise, if we want to know whether or not a character in our game has lost, we need to know only if her health is less than 0: we might not care what her location is, or the color of her armor. Programmers use accessors a lot, because they often need to know only one piece of information from a complex data structure.

• Our CakeT structure is defined using data CakeT: and the cake(...) lines, which tell the computer what things make up that structure, and what order and type each thing is. In return, we get new functions to use. Until we write these lines, we don’t have cake(...) (to make a Cake), .flavor (to get the flavor out of the Cake), .layers, or any other dot-accessors, because Pyret doesn’t know what a CakeT is- we haven’t defined it.

To see this for yourself, type a pound sign (#) before the line which begins with cake(...) and each of the fields. This comments out the definition, so that the computer ignores it. Hit run, and see what happens.

When the cake(...) lines are commented out, Pyret returns some errors, saying you’re trying to use cake before its definition. It doesn’t know what cake is or does, because we defined a CakeT structure with no constructor. Make sure students understand that the line beginning with data and a line similar to cake(...) are needed in order to create and work with any structure.

Overview

Learning Objectives

• Students will write complex functions that consume, modify and produce structures

Evidence Statements

Product Outcomes

• Students will write functions that access fields of a CakeT

Materials

Preparation

• Of course, when programmers work with data structures, they don’t just define them and create instances. They also write functions that use and produce structures. Let’s get started writing some functions for CakeTs.

• Turn to Page 12 in your workbook. Write the contract and purpose statement for a function called taller-than, which consumes two CakeTs, and produces true if the first CakeT is taller than the second.

• What is the domain for this function?

• What is the range of taller-than?

• Which part(s) of the CakeTs will you need to check to determine if one is taller than the other?

For your first example, try comparing birthday-cake and chocolate-cake. Do we care about what flavor either of these CakeTs are? What about whether or not one of them is an ice cream cake? All we need to figure out which one is taller is their number of layers.

How do you get the number of layers out of birthday-cake? What about chocolate-cake? Write your first example to figure out if birthday-cake has a greater number of layers than chocolate-cake.

•

• Write one more example for the function taller-than, this time using it to compare any two CakeTs you defined earlier.

• Next, circle and label what changes between the two examples. How many variables will this function need? Then write the definition, using your examples to help you.

After replacing the changing things with variables, your definition should look similar to:

• Turn to Page 13 in your workbook. Your bakery needs to know if certain CakeTs needs to be refrigerated. If the temperature is greater than 32 degrees AND the given CakeT is an ice cream cake, the function should return true.

• Fill out the Contract and Purpose Statement for the function.

• Write two examples for how one would use will-melt.

• Circle and label what varies between those examples and label it with a variable name.

• Define the function.

Give students plenty of time to practice using dot-accessors, extracting pieces of the Cake structures and writing expressions that compute with them.

• Optional: In the Bakery file, extend the CakeT data structure to include one more field: a message, represented as a String. (Make sure you remember to change each CakeT instance below the data definition: if a CakeT now contains four fields, each instance will need to include all four fields!) Next, write a function called birthday-cake, which takes in a string representing someone’s name, and produces a 2-layer, chocolate CakeT with "Happy birthday [Name]!" as the message. Hint: You’ll want to use the string-append function to combine two strings into one. Here is its contract: # string-append : String, String -> String

Since this function returns a CakeT, remind students that they’ll need to use the cake constructor function to produce a CakeT.

Closing

Overview

Learning Objectives

Evidence Statements

Product Outcomes

Materials

Preparation

Closing (Time 5 minutes)

• Data Structures are a powerful tool for representing complex data in a computer program. Simple videogames, like Pong, might need to keep track of only a few numbers at once, such as the position of the ball, position of each paddle, and the score. But if a game has many different enemies, each with its own position and health, or multiple levels with their own background images, the game can get very complicated very fast, and structures are a great way to manage and make sense of all the data. Programmers can do a LOT with data structures, and in the upcoming lessons you’ll start creating your own structures to make a customized animation.

Have students volunteer what they learned in this lesson!