Introduction to Data Structures

In the previous unit, you reviewed almost everything from Bootstrap:Algebra including data types, 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:Reactive.

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

Remember how to use the design recipe to work through word problems?

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 single colon (:) after the function header!)

Until now, a function could only return atomic values: single Numbers, Strings, Images, or Booleans. In Bootstrap:Reactive, our functions will still return one value, but that value can be a Data Structure, (or just “structure” for short) containing any number of values.

This way we can return both the x- and y-coordinate of a package using a DeliveryState. Later on, we’ll create new structures to record detail about characters in a game, like their health, position, amount of armor, or inventory.

In Bootstrap:Algebra, your 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:Reactive, your 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.

Students walk through the process of defining a data structure based on a word problem.

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.

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.

On this page, we’ll define a data structure called CakeType (since this is now a new data TYPE). The comment at the top of this page lists what things are part of a CakeType, and the line below (data CakeType:) starts the definition of a new data structure, called CakeType.

Each part of a data structure is called a field, which includes a descriptive name and a data type. The lines below we define the function that makes a CakeType (cake), and all the fields in a CakeType.

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

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

On your paper, you should have:

This is the code that defines the CakeType data structure. It tells the computer what a CakeType is and what goes into it. It also defines its constructor function, called cake. To make a CakeType, we call the constructor with three things in order: a flavor (a String!), layers (a Number!), and is-iceCream (a Boolean!). You can imagine how you might extend a CakeType with other fields as well.

Now take a look farther down, at line 10:

birthday-cake = cake("Vanilla", 4, false)

Below the data definition for CakeType there are four `CakeType`s defined:

At this point, you’ve worked with two different Data Structures: JumperStates and CakeTypes, and you’ve created different examples, or instances, of these structures. Instances are concrete uses of a data type, just as 3 is a concrete Number (where Number is the type). Here, CakeType 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) that data structure. When students define CakeType, 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 CakeType definition, they can’t answer such questions. Some people like the analogy of a cookie cutter here – CakeType 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 CakeTypes you just wrote:

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

Let’s make sense of this output. 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 CakeType, 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:

(1) It isn’t the same color as a normal function call, which is the first hint that something’s different.

(2) 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 value is an instance of a CakeType. 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).

Students are introduced to the syntax of dot accessors, which allow them retrieve data from instances.

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.

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

A way to prompt students to use these accessors is to ask: "How do you get the flavor out of a CakeType?" or "How do you get the layers out of a CakeType?" 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 syntax for getting a field from a structure is known as a dot accessor. They allow you to specify exactly what part of a structure you want. If we want to know if we can fit a certain CakeType 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 CakeType structure is defined using data CakeType: 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 CakeType is — we haven’t defined it.

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 CakeTypes.

For your first example, try comparing birthday-cake and chocolate-cake. Do we care about what flavor either of these CakeTypes 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.

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

Data Structures are a powerful tool for representing complex data in a computer program. Simple video games, 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.