Unit 5: Reduce and map and filter. Oh my!

[ ] have two uses.

One is to create an array and potentially initialize it. So for example:
var a = [1,2,3];
That creates an array and assigns it to a variable. Is that variable an array now? No, it is not. Trick question. Variables don’t have types in Javascript. a is a variable that has an array value. It could just as easily hold a number or a string. Variables don’t care.

I see a lot of var cats = [getColumn("Cats","Name")]; I feel like people are thinking the variable has to be marked as an array by including []. It doesn’t. getColumn returns an array. Just like the expression [] returns an array. You can assign that array to any variable you like
var numberOfHats = getColumn("Cats","Name"); That variable will hold an array value.

The second use of [] is to access object properties. Yes, you heard me, they are not specific to arrays. AP CSP teaches lists by using arrays. We then talk about arrays as if they are neatly ordered locations in memory one after another and we get to a value by counting from the left to right. That isn’t how arrays work in App Lab.

Arrays are more like a dictionary. You have a word and you find that word to get the definition. Arrays are in fact a Javascript Object. Instead of words like a dictionary they use numbers to get the definition. But they don’t have to.

Have you ever wondered about the . accessor? We see it mixed in with arrays. For example, array objects have a property called length. You get that property by using the . accessor like this a.length. Well, it turns out there is a second accessor that uses []. You could get the length of an array like this a["length"]. You could even do this:

var i = "length";
var a = new Array(1,2,3);
console.log(a[i]); // prints 3, the length of the array

“Witch! Burn him!” Calm down, it isn’t magic. You see [1,2,3] is a syntactic short cut for new Array(1,2,3). Arrays are objects and you make one by saying new. Objects have properties. An array object has a property length which is one more than the highest numbered property. So if you do this:

var b = [];
b[100] = "hundred";
console.log(b.length); // prints 101 even though b has one element.

Consider this black magic:

var convert = ["zero","one","two","three"];
for (var i = 0; i < convert.length; ++i) {
  convert[convert[i]] = i;
}
console.log(convert["one"]); // prints 1
console.log(convert[1]); // prints "one"

We have created an array that can convert numbers to strings and strings to numbers. Using the fact that arrays are just objects we initialized the conversion from number to string. Then we use a for loop to add properties for the string to number conversion.

For completeness let me add that properties can also be functions. (Functions are also objects. I know!) Typically when a property is a function we call that a method. In App Lab we see list.join(separator). join is a property of an array object that holds a function as its value.

One more thing to know about arrays: How they work as parameters. Consider this code:

var a = 3;
five(a);
console.log(a); // prints 3

function five (n) {
  n = 5;
}

App Lab is call by value. That is, when we call five with a as a parameter it is the value 3 that goes to the function not the variable a. So when we change the value of n it has no affect on the value of a.

Now consider this code:

var a = [3];
five(a);
console.log(a); // prints [5]

function five (n) {
  n[0] = 5;
}

“Witch! Bur…” Will you stop that? This isn’t magic, it’s the way App Lab works. Remember that an array is just another value you can assign to a variable. Also recall that App Lab is call by value. So in this code the value sent to the function five is the array itself. When you change the array in the function five it is changed everywhere because there is one and only one array in this example. It doesn’t matter how many variables have that as a value. That value is changed. Look at this:

var a = [1,2,3];
var b = a;
var c = b;
var b = [4,5,6];
a[1] = 4;
console.log(c); // prints [1, 4, 3]
console.log(b); // prints [4, 5, 6]

Why does c get changed to [1,4,3] when we changed a? The first 3 lines creates only one array value and assigns that one array to 3 different variables a, b, and c. They all share one array value at that point. But then we create a new array for b. That has no impact on a nor c those two still have the same array value. So when we change a that array is shared with c and it changes too. The change to a doesn’t affect b because we gave it a new array value. Did I just blow your mind?

traverstals A traversal is when you do something with each element of a list. There are 3 major reasons to look at each and every element of a list. Gratuitous Wizard of Oz reference aside, they are reduce, map, and filter. But don’t forget the trivial case of just wanting to traverse a list. Here is some code from Unit 5 Lesson 6 Level 4:

var phrases = ["The quick brown fox jumps over the lazy dog", 
               "To be or not to be, that is the question", 
               "Lorem ipsum dolor sit amet",
               "Try to be a rainbow in someone's cloud"];
var fontBoxes = ["textInput","arial","georgia","comic","arialblack","courier"];
var SKIPINPUT = 1, INCLUDEINPUT = 0;
               
onEvent("textInput", "input", function( ) {
  for (var i = SKIPINPUT; i < fontBoxes.length; i++) {
    setProperty(fontBoxes[i], "text", getText("textInput"));
  }
});

onEvent("fontSizeSlider", "change", function( ) {
  for (var i = SKIPINPUT; i < fontBoxes.length; i++) {
    setProperty(fontBoxes[i], "font-size", getNumber("fontSizeSlider"));
  }
});

onEvent("colorDropdown", "input", function( ) {
  for (var i = SKIPINPUT; i < fontBoxes.length; i++) {
    setProperty(fontBoxes[i], "text-color", getText("colorDropdown"));
  }
});

onEvent("randomPhraseButton", "click", function( ) {
  var currentPhrase = getText("textInput");
  var randomPhrase = currentPhrase;
  while(randomPhrase == currentPhrase){
    randomPhrase = phrases[randomNumber(0,phrases.length-1)];
  }
  for (var i = INCLUDEINPUT; i < fontBoxes.length; i++) {
    setProperty(fontBoxes[i], "text", randomPhrase);
  }
});

The exemplar for that bubble computes the ID of each text area using i. I prefer to use a traversal because I can name my text areas after the font they represent. For each element in the list we use it to set the color or text or anything we want on each element in the GUI. There is no output from the traversal itself, just a side effect.

I have also thrown in a twist to this traversal. I have put "textInput" into the list and then declared two constants SKIPINPUT and INCLUDEINPUT. I use these to document when I want my traversal to include the text input or not.

reduce Turn a list of values into a single value. It is called reduce because there is a function by that name that does that without a for loop getting involved. What types of actions fall under the reduce category? Find the minimum of a list. Find the maximum of a list. Calculate the total of a list of numbers. Or even find the average of a list of numbers (by first calculating the total).

The code.org people have given us a pattern for this: https://studio.code.org/s/csp5-2020/stage/10/puzzle/6 The basic idea is to use a variable as the accumulator and then use that with each element in the list. Consider finding the minimum:

var list = [1,5,3,7,0,-1];    // some random list for this example

var smallest = list[0];   // create the accumulator. In this case we 
                          // use the first element to start with.
for (var i = 1; i < list.length; ++i) {  // for each element after the first 
  smallest = Math.min(smallest,list[i]); // apply a function (min) using 
                         // the accumulator and each element of the list
}

console.log(smallest); // prints -1

Let’s look at another example that finds the sum of all elements:

var list = [1,5,3,7,0,-1];    // some random list for this example

var sum = list[0];      // Our accumulator will be a sum of all the elements 
                        // we can start with the first one.
for (var i = 1; i < list.length; ++i) { // for each value after the first
  sum = sum + list[i]; // apply a function (+) to the accumulator and
                       // each element of the array. Same as before.
}

console.log(sum); // prints 15

A pattern emerges.

  1. Create the accumulator and apply the function to the first value in the list. We have to initialize the accumulator and often it is trivial. Just assign it.
  2. For each element in the array after the first, apply the function to the accumulator and the element as a pair.
  3. Assign the new value of that function back into the accumulator.
  4. The accumulator is the final value of reduce.

map Named after the function of that name that originally came from Lisp, a language based on Lambda Calculus. Map is a mathematical term for transforming a set of values into a new set of values.

Map is a type of traversal that transforms or applies a function to each element of an array to create a new array of those transformed elements. You could use this type of traversal to create a list of the squares of some other list. Let’s look at some code:

var list = [1,5,3,7,0,-1]; // some random list to start with

var squares = [];         // a new list to fill
for (var i = 0; i < list.length; ++i) { // for each element in list
  squares[i] = list[i] * list[i];       // square the element in list and 
                         // assign it to squares. I am not using appendItem
                         // because I already know the index.
}

console.log(squares); // prints [1, 25, 9, 49, 0, 1]

This is the classic map, apply a function (square) to each element resulting in a new list. AP CSP doesn’t cover this type of traversal.

filter Create a subset of a set of values. You apply some kind of selection or rejection conditional to each element in a list. The result is a list where that condition is true for all the elements. It can be the same list as the original, but more often than not it is a smaller list. Filter is also named after a function that appears in many different languages including App Lab.

code.org provides us with a pattern for filter. https://studio.code.org/s/csp5-2020/stage/10/puzzle/5 Let’s look at some code:

var list = [1,5,3,7,0,-1]; // some random list to start with

var bigNumbers = [];      // a new list to fill
for (var i = 0; i < list.length; ++i) { // for each item in the list
  if (list[i] > 1) {      // my inclusion condition is greater than 1
    appendItem(bigNumbers,list[i]); // true, so add it to the list of 
                          // big numbers
  }
}

console.log(bigNumbers); // prints [5, 3, 7]

Here is some code from Unit 5 Lesson 11 Level 7:

var stateList   = getColumn("US States","State Name"); // this example uses 
var populationList = getColumn("US States","Population"); // two lists

var smallPopulationList = [];          // a new list to fill
for(var i = 0; i < stateList.length; i++){ // for each state in the nation
  if (populationList[i] < 1000000) {   // my inclusion condition is 
                                       // low population
    appendItem(smallPopulationList,stateList[i]); // condition met add 
                                       // the name of the state.
  }
}

console.log(smallPopulationList); // prints ["Alaska", "Delaware", "North Dakota", "South Dakota", "Vermont", "Wyoming"]

So here we have a filter operation with our condition being the population is under some amount. A pattern emerges:

  1. Create a new list to add elements into.
  2. For each element in the list apply the inclusion condition.
  3. If the inclusion condition is true add that element to the new list.
  4. The new list is the result of the filter operation.
1 Like