Luet oppimateriaalin englanninkielistä versiota. Mainitsit kuitenkin taustakyselyssä osaavasi suomea. Siksi suosittelemme, että käytät suomenkielistä versiota, joka on testatumpi ja hieman laajempi ja muutenkin mukava.

Suomenkielinen materiaali kyllä esittelee englanninkielisetkin termit. Myös suomenkielisessä materiaalissa käytetään ohjelmaprojektien koodissa englanninkielisiä nimiä kurssin alkupään johdantoesimerkkejä lukuunottamatta.

Voit vaihtaa kieltä A+:n valikon yläreunassa olevasta painikkeesta. Tai tästä: Vaihda suomeksi.

Chapter 5.3: Looping through Elements

About This Page

Questions Answered: How do I process a lot of data in one go? How do I repeat an operation on each of the elements in a collection?

Topics: Iterating over a collection with a for loop. Implementing algorithms by combining loops with local variables.

What Will I Do? Read and work on a few pocket-sized assignments. There will be more practice problems on these topics in the next chapter.

Rough Estimate of Workload:? An hour.

Points Available: A30.

Related Projects: AuctionHouse1, ForLoops (new).

Our Goal: An `AuctionHouse` Class

In Chapter 4.4, you hopefully wrote at least a FixedPriceSale class that represents items put up for sale at a set price. The same chapter also featured two optional activities that tasked you to implement classes EnglishAuction and DutchAuction. In this chapter, we’ll work with EnglishAuction.

If you didn’t implement EnglishAuction earlier, no problem. Much like a FixedPriceSale object, an EnglishAuction too represents an item put up for sale. An auction, too, has a price, a potential buyer, and an advanceOneDay method just like a FixedPriceSale does. The difference is that in an EnglishAuction, the item’ price goes up as potential buyers place higher bids on it. That’s pretty much all you need to know about EnglishAuctions. (Still, if you have the time and inclination, go ahead and do the optional assignment from Chapter 4.4 now or look at its example solution.)

So, let’s assume we have an existing EnglishAuction class that represents individual items. We’ll now look into implementing a class AuctionHouse. The plan is that each AuctionHouse instance should represent a site that runs auctions and contains a number of EnglishAuctions.

Here’s an outline for the class:

class AuctionHouse(val name: String) {

  private val items = Buffer[EnglishAuction]()

  def addItem(item: EnglishAuction) = {
    this.items += item
  }

  def removeItem(item: EnglishAuction) = {
    this.items -= item
  }

  override def toString = this.name

  // We'll add more methods here.
}

Each AuctionHouse object has its own buffer that we can access through the items variable. We can add items to the buffer and remove them, too.

Suppose we’d now like to add the following methods:

a method that advances every auction in the auction house (i.e., calls advanceOneDay on every EnglishAuction object stored in the items buffer;
a method for computing the total price of all auctions;
a method for computing the average price of all auctions;
a method for finding the auction with the highest current price;
a method for counting how many auctions are currently open; and
a method that produces all the auctions that a given buyer has won.

See below for examples of how these methods should work.

Usage examples

We should be able to creating a new AuctionHouse instance like this:

import o1.auctionhouse._import o1.auctionhouse._
val house = new AuctionHouse("ReBay")house: AuctionHouse = ReBay

The priciest method should return the most expensive item. We’ll have it return None in case the auction house contains no items, as is initially the case.

house.priciestres0: Option[EnglishAuction] = None

Let’s set up three auctions and use addItem to add them to the auction house. Each auction has a description, an initial price, and a duration in days.

val bag = new EnglishAuction("A glorious handbag", 100, 14)bag: EnglishAuction = A glorious handbag
house.addItem(bag)val camera = new EnglishAuction("Nikon COOLPIX", 150, 3)camera: EnglishAuction = Nikon COOLPIX
house.addItem(camera)house.addItem(new EnglishAuction("Collectible Easter Bunny China Thimble", 1, 10))

As illustrated in the output below, calling nextDay on the AuctionHouse shortens the remaining duration (daysLeft) of both the bag and the camera (and indeed all the open auctions in the auction house) by one.

println(bag.daysLeft + ", " + camera.daysLeft)14, 3
house.nextDay()
house.nextDay()
println(bag.daysLeft + ", " + camera.daysLeft)12, 1

totalPrice and averagePrice return some basic statistics:

house.totalPriceres1: Int = 251
house.averagePriceres2: Double = 83.66666666666667

As prospective buyers bid on items, the prices go up. This shows up in the statistics:

bag.bid("Olivia", 200)res3: Boolean = true
bag.bid("Mehdi", 170)res4: Boolean = false
camera.bid("Olivia", 190)res5: Boolean = true
house.totalPriceres6: Int = 322

The bid method places a bid on an item. Competing bids can raise the price of an EnglishAuction. (The exact bidding procedure is irrelevant for present purposes; see class EnglishAuction for that. All you need to know here is that an item’s price can change when bid is called.)

An AuctionHouse should know how to compute and return the updated total price.

The bidding raised the bag’s price and it is now the item with with the highest current price:

house.priciestres7: Option[EnglishAuction] = Some(A glorious handbag)

All three auctions are still open but the camera has only one day left and will close the next time we call nextDay. This shows in how the AuctionHouse object responds when we ask it to count the open auctions:

house.numberOfOpenItemsres8: Int = 3
house.nextDay()house.numberOfOpenItemsres9: Int = 2

Finally, let’s see what items each of our two example buyers is about to receive:

house.purchasesOf("Olivia")res10: Vector[EnglishAuction] = Vector(A glorious handbag, Nikon COOLPIX)
house.purchasesOf("Mehdi")res11: Vector[EnglishAuction] = Vector()

purchasesOf returns a vector that contains these auctions that the person has already won (such as the camera, whose high bidder was Olivia when the item closed) as well as any open auctions where the person is currently the high bidder (such as Olivia’s bag).

What do we need?

What do the AuctionHouse methods have in common?

Each of the methods needs to work through all the items of the AuctionHouse, that is, all the elements in the items buffer.
Each of the methods should repeat a particular operation multiple times, once per item.

Performing an operation on each element in a collection is an extremely common thing for a program to do. Nearly all interesting computer programs repeat operations, one way or another.

In this chapter, you’ll learn to use a Scala command that enables you to do just that. We’ll use this command to implement the AuctionHouse methods one by one.

Implementing `nextDay`

Let’s sketch out nextDay:

def nextDay() = {
  For each of the elements in this auction house’s list of items in turn:
    - Call advanceOneDay on the item.
}

A refined pseudocode:

def nextDay() = {
  For each of the elements in this auction house’s list of items in turn:
    - Take that element (i.e., a reference to auction being processed)
       and store it in a local variable.
    - Call advanceOneDay on that element.
}

Refining further we get:

def nextDay() = {
  For each of the elements in this.items in turn:
    - Store the element in a most-recent holder named, say, current.
    - Execute current.advanceOneDay().
}

Even though this is just pseudocode, the animation illustrates how the same section of the program gets executed multiple times: a so-called loop (silmukka) forms within the method and repeats a particular operation. During each loop cycle, a new current variable with a new value is created as the loop iterates over the collection’s elements.

`for` Loops

From pseudocode to Scala

Here’s one way to implement nextDay. This implementation works exactly as illustrated in the animation above.

def nextDay() = {
  for (current <- this.items) {
    current.advanceOneDay()
  }
}

You can read this as “for each item current in this.items”.

We choose a name for our variable; here we’ve chosen to name it current. This name refers to a different element during each iteration of the loop. The elements are fetched from a collection that...

... we specify using a left-pointing arrow <-.

The loop body will be executed once per element in this.items.

The structure of a `for` loop

Here’s a more generic pseudocode for performing an operation on every element of a collection:

for (variable <- collectionOfElements) {
  Do something with the element stored in the variable.
}

A for loop contains a variable definition; the variable stores the element being currently processed, and therefore has the role of a most-recent holder.

You can loop over any collection, such as a buffer (as in our first example above), a vector, a string (Chapter 5.4), an array (Chapter 11.1), a stream (Chapter 7.1), or a map (Chapter 8.4).

When you apply a for loop to a numerically indexed collection such as a buffer or a vector, as we did above, the loop traverses the elements in order, from index zero upwards.

On the Roles of Variables

In Chapter 2.6, we noted that variables can be classified by the role they have in the program.

That earlier chapter featured examples of what we labeled most-recent holders. For example, we replaced the value of an employee’s instance variable name with a new one so that only the most recently assigned name remained in memory:

class Employee(var name: String, val yearOfBirth: Int, var monthlySalary: Double) {
  // etc.
}

In this chapter, we just used a local variable (current) that we also called a most-recent holder, despite this variable appearing in a completely different sort of context than name.

for (current <- this.items) {
  current.advanceOneDay()
}

Outwardly, these two variables have little in common, but their purpose is similar in one sense. In both cases, we use the variable to store the latest in a sequence of data items: in one case, it’s the latest name assigned to the object; in the other, it’s the latest auction object that we’ve picked out for processing. The main reason why the two examples look so different is that one of our variables is an instance variable and the other is a local variable within a method. Each example illustrates a typical scenario where a most-recent holder comes in useful:

A “settable property of an object” such as name is a typical way to use an instance variable as a most-recent holder. An instance variable makes sense when we need to store the variable’s value as part of the object even between method calls.
A “latest value to be processed in a loop” such as current is a typical way to use a local variable as a most-recent holder. A local variable makes sense when we need the most recent value only to make a particular method work right.

You’ve already seen a number of different roles for instance variables. The same roles will also turn out to be useful for local variables as we use loops to implement methods. You’re about see that for yourself as we implement the other methods of class AuctionHouse.

A Local Gatherer + A Loop

Implementing `totalPrice`

Here is a pseudocode sketch of totalPrice:

def totalPrice = {
  For each of the auctions in this.items in turn:
    - Determine the current price of the item and add it to the sum.
  Finally, return the sum.
}

What local variables do we need?

A most-recent holder (of type EnglishAuction) that stores the current element (auction), just like the one we used in nextDay.
A gatherer (of type Int) that tallies up the gradually increasing sum of prices.

Let’s refine our pseudocode.

def totalPrice = {
  Let totalSoFar be a gatherer whose value is initially zero.
  For each of the auctions in this.items in turn:
    - Determine the current price of the item and increment totalSoFar by that amount.
  Finally, return the value of the gatherer totalSoFar.
}

The same in Scala:

def totalPrice = {
  var totalSoFar = 0
  for (current <- this.items) {
    totalSoFar += current.price
  }
  totalSoFar
}

Umm

Was that strictly necessary? We wouldn’t have even needed a loop if we had done this instead:

class AuctionHouse(val name: String) {

  private val items = Buffer[EnglishAuction]()
  private var priceSoFar = 0

  def addItem(item: EnglishAuction) = {
    this.items += item
    this.priceSoFar += item.price
  }

  def removeItem(item: EnglishAuction) = {
    this.items -= item
    this.priceSoFar -= item.price
  }

  def totalPrice = this.priceSoFar

}

In this solution, our gatherer is an instance variable: the total price of items is stored as part of every AuctionHouse object.

We update the gatherer as we add an auction to the auction house or remove one.

totalPrice has a very simple implementation.

Does the above implementation work, too? Answer the question for yourself by considering the following code

val house = new AuctionHouse("BuyBuyBuyBuy.net")
val item = new EnglishAuction("TV", 5000, 10)
house.addItem(item)
println(house.totalPrice)
item.bid("Karen", 10000)
item.bid("Richard", 15000)
println(house.totalPrice)

If you can’t locate the problem, send a note through the end-of-chapter feedback form and we’ll discuss it in one of the weekly bulletins.

Implementing `averagePrice`

The averaging method is trivial to implement now that we have a summing method:

def averagePrice = this.totalPrice.toDouble / this.items.size

A Local Stepper + A Loop (feat. `if`)

Here is numberOfOpenItems in pseudocode:

def numberOfOpenItems = {
  For each of the auctions in this.items in turn:
    - If the auction is open, increment a counter by one.
  Finally, return the counter’s value.
}

This refined pseudocode uses a variable as a stepper:

def numberOfOpenItems = {
  Let openCount be a stepper that starts at 0 and increases by one at a time.
  For each of the auctions in this.items in turn:
    - Store the auction in a most-recent holder named current.
    - If isOpen returns true * on the auction, increment* openCount.
  Finally, return the value in openCount.
}

A Local Container + A Loop

We want purchasesOf to return a vector with the items that the given buyer has either already bought or is currently the high bidder for.

Here’s a sketch:

def purchasesOf(buyer: String) = {
  Create a new, empty buffer and a variable purchases that refers to it.
  For each of the itemin this.items in turn:
    - If the item’s been bought by the given buyer,
      add the item to purchases.
  Finally, return a vector that contains the elements collected in purchases.
}

Why just EnglishAuctions?

What if we want our AuctionHouse to contain not just EnglishAuctions but FixedPriceSales and DutchAuctions, too? We can’t put them in a Buffer[EnglishAuction], which is the type of items and purchases?

It would be nice to have a buffer that contains items put up for sale in all sorts of ways. We could then have the methods operate on this mix of items. Can we do that?

Yes, we can. We’ll need some tools from Chapter 7.2, though. In Chapter 7.4, you get to create a new, better AuctionHouse.

A Local Most-Wanted Holder + A Loop

Here is a pseudocode implementation for priciest:

def priciest = {
  Initially, the priciest auction we’ve found is the first element in this.items.
  For each of the auctions in this.items in turn:
    - Compare the auction with the priciest one we found so far and record which is the pricier of the two.
  Finally return the auction that we’ve recorded as being the priciest.
}

What local variables do we need?

A most-recent holder (of type EnglishAuction) that stores the current element (auction).
A most-wanted holder (also of type EnglishAuction) that stores the priciest auction that we’ve encountered so far.

This refined pseudocode uses those local variables:

def priciest = {
  Let priciestSoFar be a most-wanted holder with an initial value of this.items(0).
  For each of the auctions in this.items in turn:
    1. Store the auction in a most-recent holder named current.
    2. Determine whether current is more expensive than priciestSoFar. If it is:
        - Replace the old value of priciestSoFar with current.
  Finally, return the value that ended up in priciestSoFar.
}

And here’s the Scala equivalent:

def priciest = {
  var priciestSoFar = this.items(0)
  for (current <- this.items) {
    if (current.price > priciestSoFar.price) {
      priciestSoFar = current
    }
  }
  priciestSoFar
}

What did we just forget?

Earlier, we specified that this method should return an Option[EnglishAuction] and not fail even if the auction house contains zero items. Instead, what we have here is a return value of EnglishAuction and a method that crashes if items is empty (since there is no value at index zero). This is analogous to the problem we had in Chapter 4.1 when we first used a most-wanted holder: we wrote addExperience but failed to account for the scenario where the category did not yet have any previous favorite experience.

Let’s fix the method. One way to do that is to handle the problem case separately with an if.

def priciest = {
  if (this.items.isEmpty) {
    None
  } else {
    var priciestSoFar = this.items(0)
    for (current <- this.items) {
      if (current.price > priciestSoFar.price) {
        priciestSoFar = current
      }
    }
    Some(priciestSoFar)
  }
}

We return None if there’s nothing to loop over.

Otherwise, we can do what we did before, since we’re sure to have at least one element in the buffer.

We wrap the result in a Some.

Not quite satisfied?

In this implementation, priciestSoFar and current refer to the same object when the loop body is executed for the first time. There is no point in comparing the first item with itself. In practice, our solution works fine, but it does feel a bit unclean.

You may wish to keep this problem in mind as we move to later chapters. There are various ways of implementing this method, and some of them avoid the unnecessary first comparison.

What about our old `Category` class?

In Chapter 4.2, we wrote several implementations of Category. Like this one:

class Category(val name: String, val unit: String) {

  private val experiences = Buffer[Experience]()
  private var fave: Option[Experience] = None

  def favorite = this.fave

  def addExperience(newExperience: Experience) = {
    this.experiences += newExperience
    this.fave match {
      case None =>
        this.fave = Some(newExperience)
      case Some(oldFave) =>
        val newFave = newExperience.chooseBetter(oldFave)
        this.fave = Some(newFave)
    }
  }

}

We can apply the ideas that we just used in priciest to Category as well. Instead of a most-wanted-holding instance variable, we’ll use a local variable and a for loop:

class Category(val name: String, val unit: String) {

  private val experiences = Buffer[Experience]()

  def favorite = {
    if (this.experiences.isEmpty) {
      None
    } else {
      var fave = this.experiences(0)
      for (current <- this.experiences) {
        fave = current.chooseBetter(fave)
      }
      Some(fave)
    }
  }

  def addExperience(newExperience: Experience) = {
    this.experiences += newExperience
  }

}

This alternative solution works, too.

Comparing the solutions

Since both solutions work but have their own strengths and weaknesses, we have an opportunity to discuss some quality criteria for assessing programs.

Criterion	Solution with `fave` as instance `var`	Solution with local `fave` and a loop
Intuitiveness	It is natural to think of “favorite experience“ as a property of category objects.	It is also natural to think of favorites as something that is determined by a `favorite` method upon request.
Ease of implementation	`favorite` is trivial to implement. `addExperience` is more complex.	`addExperience` is trivial. `favorite` is more complex.
Speed (of execution by computer)	The program is, in principle, faster, at least if there are a lot of experiences and `favorite` is called frequently. (However, this has no practical significance whatsoever in this application.)	The computer goes through all the elements in the buffer whenever `favorite` is called, which may make this implementation slower, in principle.
Memory usage	Each category object takes up a small amount of additional memory to store a reference to the favorite object. (However, this has no practical significance whatsoever in this application.)	Only what is needed is stored in memory as part of the category objects. The favorite experience can be obtained by searching through the buffer.
Readability and modifiability of code	Code that deals with favorite experiences appears in several places: the instance variables, the `favorite` method, and `addExperience`. Each of these pieces depends on the others. This makes the program somewhat harder to read and modify.	All the code that deals with favorite experiences is within `favorite`. There are fewer dependencies between parts of the class. The code is somewhat easier to extend and modify.

As far as this program is concerned, there is little to choose between the alternative approaches, but the loop-based solution edges it. Readability and modifiability are important!

Practice on Loops

Loop-reading practice

Loop-writing practice

Open the ForLoops project and find the app object o1.looptest.Task1. Read the code and rewrite it so that the program produces precisely the same output as before but uses a for loop to do so. Your program should be substantially shorter than the given one.

A+ presents the exercise submission form here.

Abstraction, again

A loop is an abstraction, too. In the above task, you took the given, specific lines of code and generalized them into a more generic solution.

Summary of Key Points

You can use a for loop to repeat one or more commands on each element in a collection.
You can use a for loop and local variables in different combinations.
Links to the glossary: loop, for loop, iteration; collection; role.

Feedback

Please note that this section must be completed individually. Even if you worked on this chapter with a pair, each of you should submit the form separately.

Time spent: (*) Required

Please estimate the total number of minutes you spent on this chapter (reading, assignments, etc.). You don’t have to be exact, but if you can produce an estimate to within 15 minutes or half an hour, that would be great.

“I feel that I have understood the most important things in this chapter.” (*) Required

fully agree

somewhat agree

somewhat disagree

fully disagree

I’m unable to answer or don’t want to comment.

Written comment or question:

You aren’t required to give written feedback. Nevertheless, please do ask something, give feedback, or reflect on your learning! (However, the right place to ask urgent questions about programs that you’re currently working on isn’t this form but Piazza or the lab sessions. We can’t guarantee that anyone will even see anything you type here before the weekly deadline.)

Credits

Thousands of students have given feedback that has contributed to this ebook’s design. Thank you!

Weeks 1 to 13 of the ebook, including the assignments and weekly bulletins, have been written in Finnish and translated into English by Juha Sorva.

Weeks 14 to 20 are by Otto Seppälä. That part of the ebook isn’t available during the fall term, but we’ll publish it when it’s time.

The appendices (glossary, Scala reference, FAQ, etc.) are by Juha Sorva unless otherwise specified on the page.

The automatic assessment of the assignments has been programmed by Riku Autio, Jaakko Kantojärvi, Teemu Lehtinen, Timi Seppälä, Teemu Sirkiä, and Aleksi Vartiainen.

The illustrations at the top of each chapter, and the similar drawings elsewhere in the ebook, are the work of Christina Lassheikki.

The animations that detail the execution Scala programs have been designed by Juha Sorva and Teemu Sirkiä. Teemu Sirkiä and Riku Autio have done the technical implementation, relying on Teemu’s Jsvee and Kelmu toolkits.

The other diagrams and interactive presentations in the ebook are by Juha Sorva.

The O1Library software has been developed by Aleksi Lukkarinen and Juha Sorva. Several of its key components are built upon Aleksi’s SMCL library.

The pedagogy of using tools from O1Library (such as Pic) for simple graphical programming is inspired by the textbooks How to Design Programs by Flatt, Felleisen, Findler, and Krishnamurthi and Picturing Programs by Stephen Bloch.

The course platform A+ has been created by Aalto’s LeTech research group and is largely developed by students. The current lead developer is Jaakko Kantojärvi; many other students of computer science and information networks are also active on the project.

For O1’s current teaching staff, please see Chapter 1.1.

Additional credits appear at the ends of some chapters.