The latest instance of the course can be found at: O1: 2024
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 ohjelmien 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.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 EnglishAuction
s.
(Still, if you have the time and inclination, go ahead and do the optional assignment from
Chapter 5.1 now or look at its solution below.
An implementation for EnglishAuction
class EnglishAuction(val description: String, val startingPrice: Int, duration: Int) { private var highest = new Bid(None, startingPrice) private var secondHighest = new Bid(None, startingPrice) private var remainingDays = duration def daysLeft = this.remainingDays def advanceOneDay() = { if (this.isOpen) { 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) this.startingPrice else this.price + 1 def bid(bidder: String, amount: Int) = { val newBid = new Bid(Some(bidder), amount) if (this.isOpen && amount >= this.requiredBid) { this.secondHighest = if (newBid.beats(this.highest)) this.highest else newBid.winner(this.secondHighest) this.highest = newBid.winner(this.highest) } this.highest == newBid } override def toString = this.description }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 abid
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 byEnglishAuction
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 EnglishAuction
s.
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.
}
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 everyEnglishAuction
object stored in theitems
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 = 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
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.)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 theitems
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()
}
}
current
in this.items
”.current
. This name refers to a different element during
each iteration of the loop. The elements are fetched from a
collection that...<-
.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.
Side note
You’ll see many examples of for
loops in this chapter and the
ones that follow. Nevertheless, we won’t cover all the clever
things you can do with Scala’s for
-loops.
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 11.1), a lazy-list (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 innextDay
. - 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
}
AuctionHouse
object.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+ presents the exercise submission form here.
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. }
A+ presents the exercise submission form here.
Why just EnglishAuction
s?
What if we want our AuctionHouse
to contain not just EnglishAuction
s
but FixedPriceSale
s and DutchAuction
s, 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.5, 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.head. 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.head
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.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) {
None
} else {
var priciestSoFar = this.items.head
for (current <- this.items) {
if (current.price > priciestSoFar.price) {
priciestSoFar = current
}
}
Some(priciestSoFar)
}
}
None
if there’s nothing to loop over.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)
}
}
}
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 module 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.
More code: loops and variables
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.
Credits
Thousands of students have given feedback that has 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, Jaakko Kantojärvi, Niklas Kröger, Teemu Lehtinen, Strasdosky Otewa, 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 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 was created by Nikolai Denissov, Olli Kiljunen, and Nikolas Drosdek with input from Juha Sorva, Otto Seppälä, Arto Hellas, and others.
For O1’s current teaching staff, please see Chapter 1.1.
Additional credits appear at the ends of some chapters.