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.

Kieli vaihtuu A+:n sivujen yläreunan painikkeesta. Tai tästä: Vaihda suomeksi.

Chapter 5.5: 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:? A bit over an hour.

Points Available: A30.

Related Modules: AuctionHouse1, ForLoops (new).

Background for Example: Items Whose Price Changes

In Chapter 5.1, 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 EnglishAuction assignment from Chapter 5.1 now or look at its solution below.

An implementation of EnglishAuction

Show the codeHide the code

class EnglishAuction(val description: String, val startingPrice: Int, duration: Int):

  private var highest = Bid(None, startingPrice)
  private var secondHighest = Bid(None, startingPrice)
  private var remainingDays = duration

  def daysLeft = this.remainingDays

  def advanceOneDay() =
    if this.isOpen then
      this.remainingDays -= 1

  def isOpen = this.remainingDays > 0

  def hasNoBids = this.highest.isInitialBid

  def isExpired = !this.isOpen && this.hasNoBids

  def buyer = this.highest.bidder

  def price =
    if this.secondHighest.isInitialBid
      this.startingPrice
    else
      min(this.secondHighest.limit + 1, this.highest.limit)

  def requiredBid = if this.hasNoBids then this.startingPrice else this.price + 1

  def bid(bidder: String, amount: Int) =
    val newBid = Bid(Some(bidder), amount)
    if this.isOpen && amount >= this.requiredBid then
      this.secondHighest = if newBid.beats(this.highest) then this.highest
                           else newBid.winner(this.secondHighest)
      this.highest = newBid.winner(this.highest)
    end if
    this.highest == newBid

  override def toString = this.description

end EnglishAuction

For this chapter, the relevant bit is that an item’s price isn’t fixed but determined by the bids that have been placed on the item.

There’s a bid method for placing a bid. It affects the item’s current price.

The auxiliary class Bid comes in the AuctionHouse1 module. It’s used internally by EnglishAuction and isn’t important for this chapter.

Chapter Goal: An AuctionHouse Class

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.

end AuctionHouse

Each AuctionHouse object has its own buffer that we can access through the items variable. We may add items to the buffer, and we may 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 create a new AuctionHouse instance like this:

val house = 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 = EnglishAuction("A glorious handbag", 100, 14)bag: EnglishAuction = A glorious handbag
house.addItem(bag)val camera = EnglishAuction("Nikon COOLPIX", 150, 3)camera: EnglishAuction = Nikon COOLPIX
house.addItem(camera)house.addItem(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?

1. Each of the methods needs to work through all the items of the AuctionHouse, that is, all the elements in the items buffer.

2. 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, do this:
    - 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, do this:
    - 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, do this:
    - 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 do
    current.advanceOneDay()
   

The keywords for and do define a loop like this.

You can read the beginning as “for each item current in this.items, do”.

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 body is indented further right in the usual fashion.

You may write an end marker on the loop. In most cases, people prefer to leave them out, but when a method is a bit complicated, an end marker may clarify it. Feel free to write end for on every loop if you prefer.

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
  Do something with the element stored in the variable.
end for    // This last line is optional.

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.

Side note

You’ll see many examples of for loops in this chapter and the ones that follow. Nevertheless, O1 won’t cover all the clever things you can do with Scala’s for keyword.

You can loop over any collection, such as a buffer (as in our first example above), a vector, a string (Chapter 5.6), an array (Chapter 12.1), a lazy-list (Chapter 7.2), or a map (Chapter 9.2).

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):
  // ...
end Employee

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 do
  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, do this:
    - 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, do this:
    - 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 do
    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

end AuctionHouse

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 = AuctionHouse("BuyBuyBuyBuy.net")
val item = 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, do this:
    - 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, do this:
    - 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+ presents the exercise submission form here.

A Local Container + A Loop

We want purchasesOf to return a vector containing the given buyer’s purchases, by which we mean the items that the given buyer either has 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, do this:
    - 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.

A+ presents the exercise submission form here.

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.3, though, after which 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, do this:
    - 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.head.
  For each of the auctions in this.items in turn, do this:
    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.head
  for current <- this.items do
    if current.price > priciestSoFar.price then
      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.2 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 then
    None
  else
    var priciestSoFar = this.items.head
    for current <- this.items do
      if current.price > priciestSoFar.price then
        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.3, 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)

end Category

We can apply the ideas that we just used in priciest to Category as well. We’ll still use a most-wanted-holder, but instead of it being an instance variable, we’ll make it a local variable and add a for loop:

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

  private val experiences = Buffer[Experience]()

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

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

end Category

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

Question 1

Study the code below. The first line creates a vector. What does the rest of the code do?

val words = Vector("function", "method", "subprogram", "procedure", "routine")
var result = 0
for word <- words do
  if word.length > result then
    result = word.length
println(result)

Here we don’t loop through a buffer but a vector. The principle is just the same, though.

Please list all the different numbers that result stores during a run of the above program. Enter each number on a separate line, in order. Don’t repeat the same number. Remember to include the variable’s initial value.

Loop-writing practice

Open the ForLoops module and its o1.looptest package. You’ll find task1.scala. 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.

More code: loops and variables

Question 1

def incrementElements(elements: Buffer[Int]) =
  for number <- elements do
    number = number + 1

Is that function definition valid? (Assume that Buffer has been imported.) Think about it, try it, or take an educated guess.

Yes, it’s valid. The function increments each element of the buffer by one.

Yes, it’s valid Scala code in principle, but the function doesn’t actually do anything, since it assigns a new value only to the local variable number.

No. You can’t assign a new value to the loop variable defined on the left of the arrow (here: number).

Question 2

Consider this little class:

class Adder(val elements: Buffer[Int]):

  var sum = 0

  // The method computes the sum of the buffer’s current elements,
  // then appends that sum as a new element at the end of the buffer.
  def addSum(): Unit =
    for number <- this.elements do
      sum += number
    this.elements += sum

end Adder

Which of the following claims about the addSum method are correct? Select all that apply.

The method definition is invalid. The method cannot be called.

The method works as described in the comment, when called the first time. Subsequent method calls can fail to work.

The method works as described in the comment whenever it is called.

The method would work as described in the comment if you moved the line var sum = 0 to the start of the method body, as the first indented line therein.

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 the lab sessions or Piazza. We can’t guarantee that anyone will even see anything you type here before the weekly deadline.)

Credits

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

The ebook’s chapters, programming assignments, and weekly bulletins have been written in Finnish and translated into English by Juha Sorva.

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 developed by: (in alphabetical order) Riku Autio, Nikolas Drosdek, Joonatan Honkamaa, Antti Immonen, Jaakko Kantojärvi, Niklas Kröger, Kalle Laitinen, Teemu Lehtinen, Jaakko Nakaza, Strasdosky Otewa, Timi Seppälä, Teemu Sirkiä, Anna Valldeoriola Cardó, 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 did 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 O1Library for simple graphical programming (such as Pic) 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+ was originally created at Aalto’s LeTech research group as a student project. The open-source project is now shepherded by the Computer Science department’s edu-tech team and hosted by the department’s IT services. Markku Riekkinen is the current lead developer; dozens of Aalto students and others have also contributed.

The A+ Courses plugin, which supports A+ and O1 in IntelliJ IDEA, is another open-source project. It has been designed and implemented by various students in collaboration with O1’s teachers.

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

Additional credits appear at the ends of some chapters.

Posting submission...

×

Identical submission

This submission is identical to the previous submission . Are you sure you want to submit it?

Cancel Submit