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 7.1: More Collections, More Programs

About This Page

Questions Answered: How about some more handy collection methods? How do I use these methods in combination with each other?

Topics: More methods on collections; more use cases for the previously introduced methods. We’ll also devote a few words to local functions and closures.

What Will I Do? Mostly program.

Rough Estimate of Workload:? Three or four hours.

Points Available: A95 + B30 + C40.

Related Modules: Election, FlappyBug, HigherOrder.

Computing a Result from Elements

The foldLeft method

Chapter 6.1 ended with you implementing turnElementsIntoResult, a function for computing a result (such as a sum) by processing each element of a given collection in turn and repeatedly applying a given function.

A similar very generic method is also available on Scala collections. It’s called foldLeft. Here is one way to sum up the numbers in a collection:

val numbers = Vector(10, 5, 4, 5, -20)numbers: Vector[Int] = Vector(10, 5, 4, 5, -20)
numbers.foldLeft(0)( (sumSoFar, next) => sumSoFar + next )res0: Int = 4

foldLeft has two parameter lists (like tabulate did in Chapter 6.1):

In the first list goes the initial value, which is also the end result in case the collection is empty.

And in the second list goes the function that combines each intermediate result with the next element. In this first example, we use a simple summing function.

Here is a re-run of the animation from Chapter 6.1, this time with an updated vocabulary.

There’s a simpler way to sum numbers with foldLeft; see below. An example of multiplying all the elements is also shown.

numbers.foldLeft(0)( _ + _ )res1: Int = 4
numbers.foldLeft(1)( _ * _ )res2: Int = -20000

In the following example, the function that we pass to foldLeft adds the square of its second parameter (the element) to the first parameter (the intermediate result). This yields the sum of the squares of all the elements:

numbers.foldLeft(0)( (sum, next) => sum + next * next )res3: Int = 566

Side note: an easier way to add and multiply elements

Because this chapter is supposed to teach you foldLeft, and because summing is a nice, simple first example, we just conveniently “forgot” something.

Summing the values in a collection is a common need, and there’s a bespoke method for it in the Scala API. You can just write numbers.sum. That method is available only on collections whose elements are numeric. There’s also a product method.

So that works for summing and multiplying, but not all specific needs have a ready-made solution in the form of a method. As you already saw, foldLeft can do either of those two things, and much more besides.

More folds: checking a collection’s elements

Above, foldLeft’s return value had the same type as the collection’s elements (Int, in this case). That doesn’t need to be the case. You can, for instance, fold over numbers but produce a Boolean.

The next examples of foldLeft search a collection for numbers that meet a criterion, much like the previously familiar exists method does.

This corresponds to numbers.exists( _ < 0 ):

numbers.foldLeft(false)( (foundYet, next) => foundYet || next < 0 )res4: Boolean: true

The initial value is false. This is what the fold will produce on an empty vector (in which a negative number does not exist).

The function literal’s first parameter is of type Boolean. This intermediate result indicates whether a negative element has been found so far.

The parameter function returns true if and only if a negative element had already been found or if the element at hand is negative.

Here’s a shorter version of the above as well as another example that fails to find a match:

numbers.foldLeft(false)( _ || _ < 0 )res5: Boolean = true
numbers.foldLeft(false)( _ || _ < -100 )res6: Boolean = false

More folds: combining pictures

The code below forms an image by combining multiple smaller images. What exactly does the code do and what kind of combined image does it produce? Read the code, make a prediction, and then try to see if you were right.

val base = triangle(50, 50, Yellow)base: Pic = triangle-shape
val circles = (1 to 255).map( n => circle(n, Color(n, 0, 255)) )circles: IndexedSeq[Pic] = Vector(circle-shape, circle-shape, circle-shape, circle-shape, circle-shape, [...])
val artwork1 = circles.foldLeft(base)( _.onto(_) )artwork1: Pic = combined pic

val artwork2 = (1 to 50).foldLeft(circle(50, Red))( (result, n) => result.leftOf(circle(n, Black)) )artwork2: Pic = combined pic

And perhaps you’ll recall the function placeStar that you wrote for the Stars app in Chapter 4.4? We didn’t discuss the matter then, but one of the given methods in the same program uses your placeStar function repeatedly in a fold. Here’s the code:

def create(skyData: StarMap, bgSize: Int) =
  val darkSky = rectangle(bgSize, bgSize, Black)
  skyData.stars.foldLeft(darkSky)(placeStar)

Levels of abstraction revisited

Getting to know foldLeft

These five questions aren’t crucial for success in O1, but they can be educational nonetheless.

Question 1

For this question and the next two, assume numbers is a variable of type Vector[Int] and refers to a vector that contains the integers 1, 2, and 3, in that order.

Consider the expression below. Notice that the strings contain space characters.

numbers.foldLeft("Numbers: ")( (result, next) => result + next + " " )

Which of the following does the expression evaluate to?

The options below have quotation marks around them in order to highlight the spaces. These quotation marks are not characters within the actual string.

"Numbers: 1 2 3 "

"Numbers:  1 2 3 "

"Numbers:  1 2 3"

none of the above

Question 2

What about this expression?

numbers.foldLeft("Numbers: ")( _ + _ + " " )

"Numbers: 1 2 3 "

"Numbers:  1 2 3 "

"Numbers:  1 2 3"

none of the above

Question 3

Here’s one more:

numbers.foldLeft("Numbers: ")( (result, next) => result + " " + next )

"Numbers: 1 2 3 "

"Numbers:  1 2 3 "

"Numbers:  1 2 3"

none of the above

Question 4

For this question, assume that data is a variable that refers to some collection of elements. Further assume that f is a function of type Int => Boolean.

For the sake of practice, let’s use foldLeft to implement an equivalent of a forall method call: does every element meet the given criterion? Here’s a start:

data.foldLeft(AAA)( (result, next) => result BBB f(next) )

What should we write instead of AAA and BBB so that the expression would return the same value as data.forall(f)?

false and &&

false and ||

true and &&

true and ||

none of the above

Question 5

Use an abbreviated function literal with anonymous parameters to rewrite the expression from the previous question. (Also replace AAA and BBB as appropriate.)

The reduceLeft method

The reduceLeft method is very similar to foldLeft. The differences are these:

• reduceLeft doesn’t need to be given an initial value. Instead, it uses the collection’s first element for that purpose.

• reduceLeft fails on an empty collection, causing a runtime error.

• reduceLeft’s return value has the same type as the collection’s elements (as do the intermediate results that lead up to the return value).

As an example, let’s use reduceLeft to find the smallest element:

val numbers = Vector(10, 5, 4, 5, -20)numbers: Vector[Int] = Vector(10, 5, 4, 5, -20)
numbers.reduceLeft( min(_, _) )res7: Int: -20

Or even more simply:

numbers.reduceLeft(min)res8: Int: -20

reduceLeft is convenient when 1) you can assume that there is at least one element in the collection; and 2) the first element is what you want as a result in case it is the only element.

This additional example uses images:

val pics = Vector(Pic("face.png"), Pic("horse.png"), Pic("obstacle.png"))pics: Vector[Pic] = Vector(face.png, horse.png, obstacle.png)
val columnOfPics = pics.reduceLeft( _.above(_) )columnOfPics: Pic = combined pic

Terminological note

The verb “fold” appears in the method name because, metaphorically, it “folds” a sequence of values together into a single result. The story behind the full name is a bit more involved, but one way to think about Scala’s foldLeft implementation in practice is that it starts from the collection’s “left” and advances “rightwards”.

As an optional activity, you may wish to look up the methods foldRight and reduceRight.

reduceLeft plus Option — and a new favorite

It was mentioned that reduceLeft relies on there being at least one element in the collection. Otherwise its result isn’t defined.

On the other hand, you’ve already learned to use the Option class to represent situations where a result may or may not exist.

We can combine the two: let the result be None if there are no elements; otherwise, we’ll call reduceLeft and wrap its return value in a Some.

Let’s return for a moment to GoodStuff’s Category class and its favorite method, which we’ve already implemented in different ways in Chapters 4.3 and 5.5. Here’s one more version:

def favorite =
  if this.experiences.isEmpty then None else Some(this.experiences.reduceLeft( _.chooseBetter(_) ))

If we didn’t check the collection with the if, reduceLeft would cause the program to crash with a runtime error (cf. the NullPointerException we got in Chapter 4.2).

Combining reduceLeft with an Option wrapper is common enough that there’s a separate method for it. This method, reduceLeftOption gives us a succinct implementation for favorite:

def favorite = this.experiences.reduceLeftOption( _.chooseBetter(_) )

This is essentially shorthand for the slightly longer version above.

Further reading: MapReduce

This chapter and the previous one have introduced you to methods called map and reduce. Those methods, like the other ones we’ve discussed hereabouts, are typical of the functional programming paradigm (which we’ll discuss in Chapter 11.2).

Do an internet search and find out the basic principles of MapReduce, a way of structuring programs that Google, for instance, has used for processing vast amounts of data. How is MapReduce similar to the collection methods that we’ve discussed?

Assignment: Reimplementing Election (Part 2 of 2)

In the previous chapter you reimplemented a couple of methods from class District. Reimplement two more: the two totalVotes methods.

Instead of loops, use either foldLeft or combine map with sum. Or perhaps you’ll find it instructive to see if you can come up with both implementations.

If you did as Chapter 5.6 suggested and wrote a countVotes method as an auxiliary for the two totalVotes methods, you need to change only that method.

Reimplementing those methods is enough for now. We’ll return to add more methods to District in Chapter 10.1.

A+ presents the exercise submission form here.

Assignment: FlappyBug (Part 17 of 17: Prettier Code)

Let’s also revisit the methods you wrote for FlappyBug in Chapter 5.6 and see how we can use our higher-order equipment there.

Reimplement the following methods. They should do what they did before, but you should replace any loops with higher-order method calls. You work from either your own earlier implementation or the example solution.

1. timePasses in class Game. Use foreach (Chapter 6.3).

2. isLost in the same class. The implementation will be much simpler if you use a method from Chapter 6.3 to directly check whether there is an obstacle that’s fatally close.

3. makePic in the GUI. Replace the loop with a foldLeft call that places each obstacle where it should be.

A+ presents the exercise submission form here.

Afterword #1: levels of abstraction

In the Snake assignment of Chapter 6.3 you could use the placeCopies method since all the snake’s segments looked alike. You had this fairly specific method for doing just what was needed, highly abstracted away from implementation details.

In the preceding assignment, on the other hand, you hopefully used foldLeft to implement makePic, as requested. placeCopies wouldn’t have served you here, since the obstacles aren’t identical. Lacking a specific tool, you resorted to a more generic tool at a lower level of abstraction.

If the o1 package hadn’t happened to provide placeCopies, you could have used foldLeft in Snake, too. (Try it.)

As a matter of fact, the placeCopies method has been implemented with foldLeft, so you actually used it indirectly in any case.

Afterword #2: efficiency

You hopefully used exists (or perhaps forall) to implement isLost.

In an optional section of Chapter 5.6, we raised a question about efficiency. Did our earlier implementation do extra work (in principle) by traversing the whole vector even though a matching obstacle had already been found?

exists and forall stop traversing as soon as the return value is apparent, so using them is one way to avoid this issue (which is of course entirely negligible in this application anyway).

There won’t be any further official FlappyBug assignments in O1, but feel free to make your own additions and modifications.

Using the Methods in Combination

You will often find it useful to combine the collection methods that we’ve discussed.

Here’s one toy example of using a combination of methods to process a vector of numbers. The following command counts positive elements whose square is an even number.

val numbers = Vector(10, 5, 4, 5, -20)numbers: Vector[Int] = Vector(10, 5, 4, 5, -20)
numbers.filter( _ > 0 ).map( n => n * n ).count( _ % 2 == 0 )res9: Int = 2

This mini-assignment looks at combining methods on a more general level:

Suppose we have a variable data that refers to a collection. The code given below uses a loop, a couple of ifs and some variables to process the collection and compute a result. The code uses three functions p, q, and r; these can be any effect-free functions of a compatible type.

var result = false
for element <- data do
  if p(element) then
    val temp = q(element)
    if r(temp) then
      result = true
    end if
  end if
end for
println(result)

The snippet below is instead written in functional style. It’s missing a few key components, however:

println(data.AAA(p).BBB(q).CCC(r))

Which methods should we call where it now says AAA, BBB, and CCC so that this (much simpler!) program would do the same thing as the longer program above? Bonus question: can you think up a more practical scenario where you might use this combination of higher-order methods?

Question 1

Where it says AAA we should use:

exists

filter

flatMap

forall

foreach

map

Question 2

Where it says BBB we should use:

exists

filter

flatMap

forall

foreach

map

Question 3

Where it says CCC we should use:

exists

filter

flatMap

forall

foreach

map

That assignment where we have turn imperative code into a functional form clearly showed how a mixture of conditionals [in the original loop-based code] messes with your head.

Assignment: Rain

Introduction

Imagine we have a device that generates reports of rainfall measurements in Vector[Int] form. More specifically:

• Each zero and positive number in the vector represents a measured amount of rainfall.

• The vector contains one or more series of measurements. Each such series ends with the special value 999999, which is not a measurement but simply marks the end of the series.

• The vector may also contain negative numbers. Such additional data does not indicate rainfall and is superfluous to our purposes.

Task description

In rainfall.scala of module HigherOrder, write averageRainfall, a function that receives a single Vector[Int] parameter as described above. The function should return the average rainfall computed from the first data series in the vector. Here are some examples of the expected behavior:

averageRainfall(Vector(40, 0, 50, 999999))res10: Option[Int] = Some(30)
averageRainfall(Vector(0, 0, 0, 0, 999999))res11: Option[Int] = Some(0)
averageRainfall(Vector(999999))res12: Option[Int] = None

The average is an Int and comes in an Option wrapper.

The number 999999 just terminates a data series and isn’t included in the average. The average is that of the preceding numbers.

If there are no measurements, there’s no average either.

In case the vector contains multiple data series, only the first one matters:

averageRainfall(Vector(50, 150, 100, 100, 999999, 20, 30, 90, 999999, 0, 0, 999999))res13: Option[Int] = Some(100)
averageRainfall(Vector(999999, 50, 100, 999999))res14: Option[Int] = None

The return value reflects the first data series only.

Any numbers beyond the first 999999 are irrelevant.

If the first series has no data, there’s no result.

Negative values must not impact on the return value at all:

averageRainfall(Vector(-10, 50, -100, 150, -1, -5, 100, 100, 999999, 20, 30, 90, 999999, 0, 0, 999999))res15: Option[Int] = Some(100)
averageRainfall(Vector(-100, -5, -10, 999999, 50, 100, 999999))res16: Option[Int] = None

Instructions and hints

• Just divide the Ints like Scala divides Ints (Chapter 1.3). Don’t round the result to the nearest whole number or anything like that.

• Use higher-order methods on collections. There are many ways you can combine them to solve this problem. Can you come up with multiple solutions?

  • For comparison’s sake, you could sketch out a solution based on a loop. Which solution captures the programmer’s intent better?

• You may assume that the input vector always contains the number 999999 at the end.

A+ presents the exercise submission form here.

A small follow-on assignment

The averageRainfall function received a vector of integers. What if we had to process a collection of strings instead, with some of the data valid and some of it invalid? (You can imagine receiving such data from user inputs, say, or some data file.)

In the same file, write another function averageRainfallFromStrings, which takes in a Vector[String]. It interprets each string as an integer, simply discarding every element that don’t correspond to valid Ints. The function computes and returns the average of the valid elements just like averageRainfall did.

Examples:

averageRainfallFromStrings(Vector("cat", "50", "-100", "dog", "10", "999999", "20", "ten", "999999"))res17: Option[Int] = Some(30)
averageRainfallFromStrings(Vector("cat", "dog", "999999"))res18: Option[Int] = None
averageRainfallFromStrings(Vector("cat", "-1", "dog", "999999"))res19: Option[Int] = None

Instructions and hints:

• Do not make a copy of your averageRainfall function! Use the String vector to produce an Int vector and call averageRainfall on the integers.

• You may assume that the string "999999" appears at least once among the inputs.

• There are methods that compose to an extremely simple solution. If you want additional hints about which methods to pick, you may want to look at Chapter 6.3 and the REPL session below.

  "123".toIntOptionres20: Option[Int] = Some(123)
  "sata".toIntOptionres21: Option[Int] = None
  val possibleNumbers = Vector(Some(10), None, Some(15), None, None, Some(-5))possibleNumbers: Vector[Option[Int]] = Vector(Some(10), None, Some(15), None, None, Some(-5))
  possibleNumbers.flattenres22: Vector[Int] = Vector(10, 15, -5)
  val words = Vector("one", "2", "3", "four")words: Vector[String] = Vector(one, 2, 3, four)
  words.map( _.toIntOption )words: Vector[Option[String]] = Vector(None, Some(2), Some(3), None)
  

A+ presents the exercise submission form here.

Assignment: Lack of Rain

Task description

In the same file, write a function drySpell that:

• takes in a Vector[Int] of rainfall data just like averageRainfall;

• takes as its second parameter a positive integer length that indicates the minimum length of the “dry spell” that the function should look for in the data;

• searches the vector for the first subsequence of consecutive numbers that are between 0 and 5, inclusive;

• returns the first index of the dry spell (if found) or a negative number (if not found); and

• considers all the numbers in the vector, not just the ones before 999999. However, a sequence of numbers split by the series-terminating 999999 doesn’t count as a dry spell, nor does a sequence split by a negative number.

An example:

val exampleData = Vector(10, 0, 3, 999999, 2, -10, 2, 0, 2, 1, 20, 1, 0, 1, 999999)exampleData: Vector[Int] = Vector(10, 0, 3, 999999, 2, -10, 2, 0, 2, 1, 20, 1, 0, 1, 999999)
drySpell(exampleData, 3)res23: Int = 6

We’re looking for the first uninterrupted dry spell that is at least three measurements long...

... and find the first such sequence at index six.

Instructions, hints, and some new tools: indexWhere, sliding

You can assume that there isn’t a massive amount of data to process and there’s no need to optimize the program’s efficiency.

Use the higher-order methods you already know. In addition, learn the two new ones introduced below and use them.

indexWhere looks for the first element that matches a criterion:

val myVector = Vector(10, 5, 0, 3, 0, 100, 50)myVector: Vector[Int] = Vector(10, 5, 0, 3, 0, 100, 50)
myVector.indexWhere( _ <= 0 )res24: Int = 2
myVector.indexWhere( _ < 0 )res25: Int = -1

sliding generates “slices” of the original collection. The method takes a length as a parameter, which determines the length of each such “slice”.

val myVector = Vector(10, 5, 0, 3, 0, 100, 50)myVector: Vector[Int] = Vector(10, 5, 0, 3, 0, 100, 50)
myVector.sliding(4).foreach(println)Vector(10, 5, 0, 3)
Vector(5, 0, 3, 0)
Vector(0, 3, 0, 100)
Vector(3, 0, 100, 50)
myVector.sliding(5).foreach(println)Vector(10, 5, 0, 3, 0)
Vector(5, 0, 3, 0, 100)
Vector(0, 3, 0, 100, 50)
myVector.sliding(5).toVectorres26: Vector[Vector[Int]] = Vector(Vector(10, 5, 0, 3, 0), Vector(5, 0, 3, 0, 100), Vector(0, 3, 0, 100, 50))

To be more specific, sliding returns a so-called iterator that provides access to a “list of slices”. This does not change the original vector.

You can use the iterator to access each “slice” once (and only once!). Many of the familiar collection methods are available on the iterator object, including foreach, toVector, and indexWhere. If you wish to apply multiple methods to each slice, you can first copy the slices from the iterator to a vector. (That isn’t actually necessary in this assignment though.)

In the example above, note that the slices overlap. For instance, the number 3, which is the fourth element of the original vector, appears as the fourth element of the first slice, the third element of the second slice, the second element of the third slice, and the first element of the fourth slice.

A+ presents the exercise submission form here.

drySpell and computational efficiency

The task description noted that you don’t need to optimize drySpell’s efficiency. If such an optimization was needed for some reason, the solution that the above REPL example hinted at might come in for criticism, despite being rather elegant.

A solution that relies on the hinted methods does some extra work: It constructs many “slices” that are partially identical to each other. Then it operates on each such slice separately in turn, even though some of the same numbers have already been checked while processing an earlier slice.

It’s possible to make the program more efficient; in fact, there are many ways to do that. In Scala, one of those ways is to use the indexOfSlice method. If you wish, you can look up the method online and consider how you might apply it here. You can also try to come up with still more efficient solutions.

Reflecting on Functions

We’ll round off this chapter with a few questions that challenge you to study the given snippets of Scala code and reflect on how they work (if indeed they do). These programs will also introduce new programming techniques that will be increasingly useful as we go on.

What we have covered so far in O1 is probably not enough to impart ironclad answers to the questions below. This is deliberate. On the other hand, the answers are rather intuitive. Remember to read the feedback you receive whether or not you answered correctly!

Topic #1: a function within a function

Question 1

Here are a couple of example functions. They don’t do anything too meaningful but study them anyway.

def findBig(vector: Vector[Int]) =
  def countsAsBig(number: Int) = number > 1000
  vector.filter(countsAsBig)

def chat() =
  import scala.io.StdIn.*

  def promptForName() =
    readLine("Enter a name: ")

  def greeting(recipient: String) = "Ave, " + recipient

  val first = promptForName()
  val second = promptForName()
  println(greeting(first + " and " + second))
end chat

Within these two functions...

... there are further function definitions.

Which of the following claims accurately describes these function definitions?

The code is valid. The functions countsAsBig, promptForName, and greeting are local helper functions for the outer functions. This is similar to local variables.

Only one of the two programs is valid.

The function definitions are invalid. The idea of nesting a function within another is fundamentally flawed. If you want to nest a def somewhere, it should be nested directly within a class or singleton object, not inside another function.

The function definitions are invalid. The idea is good in principle, but Scala’s rules prevent such nesting.

Question 2

Here is some more code for you to assess. Each of the two snippets below attempts to use the functions defined above.

// Attempt 1:
println(countsAsBig(5000))

// Attempt 2:
val bigOnes = findBig(Vector(2000, 300, 5000))
println(countsAsBig(5000))

Which of the following describes these two examples?

Neither of the attempts is successful, because there is a problem in the function(s) from the previous question.

None of the attempts is successful, because countsAsBig is local to findBig and can be invoked only within findBig. The principle is the same as that for accessing local variables.

Both attempts are successful. Even though countsAsBig is defined within findBig, we may call it from external code.

Only the second attempt is successful. Since countsAsBig has been defined inside findBig, it cannot be called unless findBig has been called first.

Topic #2: local variables

Question 1

Here’s a variant of findBig.

def findBig(vector: Vector[Int], limit: Int) =
  def countsAsBig(number: Int) = number > limit
  vector.filter(countsAsBig)

This function takes a limit parameter that specifies how big a number should be to count as big and be included in the output vector.

In the local function countsAsBig, we use not only its own variable number...

... but also the variable limit from the surrounding function.

The question is, can we do that? Can a local variable use names defined in the surrounding environment, such as limit?

Yes. limit is available to the entire findBig function and countsAsBig is included.

No. It would be nice if it did, but it doesn’t seem to work.

No, and it’s a good thing. If that was allowed, it would lead to serious conflicts when naming variables.

Question 2

How about this other aspect of our function?

def findBig(vector: Vector[Int], limit: Int) =
  def countsAsBig(number: Int) = number > limit
  vector.filter(countsAsBig)

Our function calls the filter method on a vector. The Vector class and its methods have been defined elsewhere, as part of the standard Scala API. During a program run, filter runs in its own frame within the call stack.

As we call filter, we pass in a function that uses limit, which is defined as a local variable in the surrounding context. However, filter isn’t local to findBig.

Does that work?

No. countsAsBig cannot use a local variable of findBig. (See the previous question.)

No. The definition of filter isn’t nested within findBig, so it has no access to limit.

Yes. countsAsBig has been defined within findBig and therefore has access to limit. As we call filter, we pass in countsAsBig, which lets filter access limit indirectly.

A few words about closures

def findBig(vector: Vector[Int], limit: Int) =
  def countsAsBig(number: Int) = number > limit
  vector.filter(countsAsBig)

Our example code is easy to understand: filter the vector for numbers whose value exceeds that of a particular variable. It’s “natural” that the code works.

That the code works is not self-evident, though. After all, filter runs in its own frame on the call stack; findBig has a separate frame below and, generally speaking, functions don’t have access to local variables in other frames (Chapter 1.8).

What we did there doesn’t work in all programming languages, but it works in others, including Scala. Why?

Since the code works, it’s clear that, behind the scenes, filter somehow receives not only a reference to the function countsAsBig but some construct that has access to limit. Such a combination of a function and one or more external variables is known as a closure (sulkeuma). (The function “closes over” variables defined outside of itself.)

The Scala compiler constructs closures automatically when, within a function, you use a variable from the surrounding context. As a consequence, using closures is intuitive; we are often barely aware that we do it.

Benefiting from closures is one reason for nesting a function within another. For example, countsAsBig can use limit precisely because it is nested within findBig; we need that in order to pass in the corresponding closure to filter.

In our example, we defined a named function countsAsBig, but you can also construct closures from function literals. Here’s another way to put our example code:

def findBig(vector: Vector[Int], limit: Int) =
  vector.filter( _ > limit )

We pass filter a comparison function defined by a literal

To be more precise: we pass filter a closure whose code is _ > limit and which has access to the limit variable that it needs.

Function literals like the above, which use a variable from the surrounding context (and automatically produce closures), are perfectly common in Scala programs.

You can learn more about closures in O1’s follow-on courses or by looking up the topic online. For O1, it’s enough to know that code such as the above simply works. Just go ahead and use the variables from the surrounding context where you need them. In later chapters, we’ll do that often and unceremoniously.

More nesting

You have seen that Scala lets you nest functions in functions. In fact, you can nest classes, objects, and functions within each other pretty much freely. For instance, you can define a class within a class, or a singleton object within a method.

Bonus: A function that returns a function

Chapter 6.1 mentioned that a higher-order function is a “function that operates on functions”: it takes a function as a parameter or returns a function. All the higher-order functions you’ve seen in the ebook so far have been of the first sort: they take functions as parameters.

In O1, we won’t really be writing functions that return functions, but here’s a simple example:

def makeAnAdderFunction(amountToAdd: Int): Int => Int =
  def adder(n: Int) = n + amountToAdd
  addermakeAnAdderFunction(amountToAdd: Int): Int => Int
val addTen = makeAnAdderFunction(10)addTen: Int => Int = $$Lambda$5328/648803586@1347ef1b
addTen(5)res27: Int = 15
addTen(6)res28: Int = 16
makeAnAdderFunction(100)(5)res29: Int = 105

You may also use a literal to define the function that gets returned:

def makeAnAddingFunction(amountToAdd: Int): Int => Int =
  _ + amountToAddmakeAnAddingFunction(amountToAdd: Int): Int => Int

Optional Practice: Blurring an Image

Implement a blur function

You may want to do the assignment in task10.scala, which provides additional practice on the topics of this chapter and the previous one. The assignment asks you to program a picture-blurring filter.

Hints:

• Pic objects have methods that are handy here. Check out the class documentation for transformXY and pixelsNear, in particular.

• Maybe you’d like to define a named helper function inside the blur function? For instance, you could define a helper named blurPixel to determine the blurred color for a given pair of coordinates. (Cf. the nested function within findBig in the example above.)

• And how about another helper function for computing the average?

A+ presents the exercise submission form here.

Summary of Key Points

• In addition to the convenient methods introduced in the preceding chapter, collections have two highly generic methods named foldLeft and reduceLeft. You can use them to compute an overall result by processing each element of the collection in turn.

• It’s often unnecessary to detail the execution of a method with a loop that manages ifs and updates vars and juggles many things at once. You can instead express what you want as a chain of higher-order method calls so that each method operates on the collection returned by the previous step.

• You can define a local function much as you can define a local variable.

• As you define a function, you can use variables from the surrounding environment in the function body. Such a construct is called a closure.

• Links to the glossary: higher-order function; collection; level of abstraction; local function, scope; closure.

Palaute

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, Kaisa Ek, Joonatan Honkamaa, Antti Immonen, Jaakko Kantojärvi, Onni Komulainen, Niklas Kröger, Kalle Laitinen, Teemu Lehtinen, Mikael Lenander, Ilona Ma, Jaakko Nakaza, Strasdosky Otewa, Timi Seppälä, Teemu Sirkiä, Joel Toppinen, 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, Juha Sorva, and Jaakko Nakaza. 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; 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 for this page

The rainfall assignment is a version of a classic programming problem by Elliot Soloway.

Posting submission...

×

Identical submission

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

Cancel Submit