Book - 3.6) Algorithms - Iteration in BlockPy (Part 1)

Patterns of Iteration ¶

There is a general pattern for processing a list that represents a data stream. The three steps in the pattern are:

Set the value of a variable to the stream data.
Perform the iteration using the “for each” where the variable denotes the item in the data stream used for each step in the iteration.
Apply some processing to the current item.

The general structure can be adapted to individual problems by specializing the kind of processing that is done on each item. The processing step is often one of four kinds:

Uniform: apply the same processing to each item in the stream.
Accumulate: compute a global property for the stream where the global property is updated by each item.
Filter: select certain items in the stream to process and ignore the others.
Transform: produce a new data stream from the original stream by transforming the individual items in some way.

We will look at examples of each of these four patterns. We will begin by examining the first two patterns, uniform and accumulate. After seeing how decision is represented in Blockly, we will examine the last two patterns, filter and transform.

Iteration: Uniform ¶

The BlockPy workspace below shows an example of combining lists and iteration to process each item in a data set in a uniform way. The list in this example contains amounts of precipitation reported for different cities. The list is produced by the weather block using the settings to select the Location of Blacksburg, VA. This algorithm simply prints each item of the data set, one item per line, in the Printer area of the workspace.

Run the code and see what values are in the data set for different cities. Note: you may need to use the scroll bar on the right of the Printer area to be able to see all of the output.

The example above was one of uniform processing. Each item in the data set was printed. No items were excluded.

Iteration: Accumulate ¶

An example of processing that involves accumulating is finding the average precipitation in a given city. To find the average, we need to know the total amount of precipitation recorded and the number of days over which the recording is done. For example, if there were a total of 3 inches of precipitation over a 30 day period, the average precipitation would be 0.1 inches of precipitation per day. The following BlockPy workspace shows an algorithm for this.

In this algorithm, the property "precipitation_list" is used to denote the list of the reported amounts of precipitation on each day. The list iteration in the algorithm acts over this list. The list iteration uses the property "precipitation" to denote the current individual item in the "precipitation_list". Recall that on each iteration the value of the property "precipitation" is set to another value in the "precipitation_list". Two properties of the data set are being accumulated as each item in the data set is examined. One property is the total amount of precipitation (this property is named total_precipitation). The second property is the total number of days involved in the reporting (this property is named number_of_days). On each iteration, a “set” block is used to update each of the two properties as follows:

set total_precipitation = total_precipitation + precipitation
set number_of_days = number+of_days + 1

The first of these means that the current value of the property "precipitation" is used to update the property "total_precipitation". This can be read as "increase the total amount of precipitation by the amount of precipitation on this day." The second of these means that the current value of the property "number_of_days" is updated by 1. This can be read as "increase by 1 the number of days on which a precipitation amount was reported."

An important part of the accumulating pattern is that the variables being used to accumulate the global properties are initialized. In this program, the two variables “total_precipitation” and “number_of_days” are each initialized to zero. The initialization is necessary so that on the first iteration the two “set” operations make sense. For example, with “number_of_days” initialized to zero, the block “set number_of_days = number_of_days + 1” on the first step of the iteration makes sense (updating the value of the property "number_of_days" from the initial value of 0 to the updated value of 1.

This pattern of data stream processing is called “accumulate” because on each iteration, some properties are accumulating information on each iteration step about the selected global properties of the data set. In this case, the program is accumulating information about the number of days in the data set and the total amount of precipitation.

Decision ¶

In addition to working with specific temperatures, we often want to know if the temperature is above or below some threshold. A threshold is one of the quantitative measures of an abstraction. Considering the abstraction of weather in a city, the amount of precipitation on a given day could be classified in one of three ways:

Dry - if there was no precipitation reported for that day
Light Rain - if some rain was reported for that day and the amount was 0,5 inches of rain or less
Heavy Rain - if more than 0.5 inches of rain was reported for that day.

Each of these categories represents a threshold. The work space below uses decision blocks (from the Decisions category) to characterize the precipitation reported for each day in Blacksburg according to the thresholds identified above.

There are two important things to notice about the algorithm in the above work space. The first is the block used for the decision: an if...else if...else" block. This block has slots for the "if" and "else if", each of which holds the condition to be tested. The second condition is only tested if the first condition is found to be false. This logic is used because if the amount of precipitation is zero then it cannot in the other two categories. and 85 degrees. Thus, if the precipitation is zero, the decision block causes “Dry” to be printed and does not evaluate the second condition. However, if the precipitation is not zero then it is necessary to evaluate the second condition to decide which of the other two categories applies.

It is slightly tricky in BlockyPy to create an “if...else if...else” decision block like the one used above. Here is how it is done:

In the Decisions category select an “if..do” block. Notice that the block has a star in a blue box to the left of the word “if”.
Click the star in the blue box. In the popup window there is an “if” form on the right, and on the left, an “else if” form and an “else” form. Drag the “else if” form from the left into the slot of “if” form on the right. When it snaps into place you will see the original “if..do” block change its shape.
Next, drag the "else" form from the left into the slot of :if: form on the right and place it below the "else if" form you added in the step above. When it snaps into place you will see the original “if..do” block change its shape to the desired block.
Click on the star in the blue box to close the popup window.

The algorithm above used simple conditions to test for thresholds. More complicated cases required more complicated logic. For example, imagine that a category was defined:

Moderate Rain - if the amount of reported precipitation for that day was more than 0.5 inches and less than 0.75 inches.

In this case we would need a condition that determined:

is the precipitation above the lower limit of the range (0.5 inches), AND
is the precipitation less than the upper limit of the range (0.75 inches).

To combine these two separate conditions into one compound condition, an “and” Boolean operator is used. A compound condition with an “and” operator in Boolean logic is true only if both of its two conditions are true (and false otherwise). A related Boolean operator, the “or” operator, is true if either of its two conditions is true (and false otherwise). The block for building compound and/or conditions is in the Decision category. The category also contains a third Boolean operator, “not”. This block has a single slot into which a condition can be inserted. The combination of the “not” and a condition form a compound condition which is true if the condition is false and false if the condition is true. For example, the compound condition

not (precipitation > 0.5)

true if the value of the property precipitation is not greater than 0.5,
false if the value of the property precipitation is greater than 0.5

Such negated conditions are sometimes used when the statement of a negative condition is easier to understand.