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.
Kieli vaihtuu A+:n sivujen yläreunan painikkeesta. Tai tästä: Vaihda suomeksi.
Chapter 6.1: Functions as Parameters
About This Page
Questions Answered: Could a function operate on other functions? How do I pass a function as a parameter to another function? Why is it great that I can do that?
Topics: The main topic is higher-order functions, especially ones that take in functions as parameters. We’ll touch on a number of other topics as well, including multiple parameter lists, generating collections, and nesting collections within another. Several examples and practice problems involve image processing.
What Will I Do? Read and program. There are small assignments spread throughout.
Rough Estimate of Workload:? Three or four hours.
Points Available: A50 + B25 + C20.
Related Modules: HigherOrder (new). In one example, we’ll briefly revisit AuctionHouse1, too.
Introduction
We have established that programs feature:
data — such as numbers, text, and various other objects — which we can store in memory and which we process with:
operations — functions — that do something with data and may be attached to the data that they operate on (like methods are attached to objects in OOP).
However, this distinction isn’t as clear-cut as it may have seemed so far. It turns out that functions are data, too: we can store a function in a variable, pass a function as a parameter to another function, or have a function return a function.
We’ll soon get to why it is really useful to do that. But first, let’s look at some concrete examples of code.
Assigning a Function to a Variable
Let’s start by writing a couple of perfectly mundane functions. Here’s one:
def next(number: Int) = number + 1next(number: Int): Int next(100)res0: Int = 101
The REPL confirms that next is now a function that takes in an
Int...
... and also returns an Int. In other words, next is a
function of type Int => Int, where the Int to the left of
the arrow is the parameter type and the Int on the right is
the return type.
doubled is also a function of type Int => Int:
def doubled(original: Int) = 2 * originaldoubled(original: Int): Int doubled(100)res1: Int = 200
That sort of definitions are familiar to us by now. But here’s something new. Let’s define a variable and make it refer to one of our functions:
var testFunc = doubledtestFunc: Int => Int = Lambda$1338/0x00000008010c5400@65d90b7f testFunc(10)res2: Double = 20
What we assign to the testFunc variable is the value of the
expression doubled. Pay attention: we don’t actually call
doubled here; we don’t give it a number as a parameter! The
name testFunc now refers to a function that returns a number
twice as big as the one it received.
The REPL states that our variable has the type Int => Int,
meaning a function that both takes in and returns a number.
The REPL’s explanation of the variable’s value — the function that is stored in the variable — looks awful. But never mind that...
... the code works fine! The expression testFunc(10) calls
the function that testFunc refers to.
Now, testFunc is a variable like any other. Since this variable of ours happens to be
a var, we can change its value if it pleases us. For example’s sake, let’s make it
refer to our other function, next, instead:
testFunc = nexttestFunc: Int => Int = Lambda$1508/0x0000000801120600@260f05ee testFunc(10)res3: Int = 11
Lessons learned: Functions are data. You can assign a function to a variable. You can then use the variable’s name to invoke the function.
And since a function can be manipulated just like other data can, you can pass a function as a parameter to another function, as you’re just about to see.
Passing a Function as a Parameter
Here’s our short-term plan
We already have these two simple functions as examples of operations that take in a single integer and also return an integer.
def next(number: Int) = number + 1
def doubled(original: Int) = 2 * original
Now we’ll define a function named twice, which lets us apply any such Int-to-Int
function two times. So that twice knows what it should do two times, we pass that other
function as a parameter to twice. We’d like to be able to call twice like this:
twice(next, 1000)res4: Int = 1002
Notice: the first parameter of twice is a function! That’s how we indicate which
function we want to apply twice. The second parameter is the target of the function
applications; it’s a garden-variety integer.
Applying next twice produced a number that’s two greater than the input. Doubling
a number twice yields a quadruple:
twice(doubled, 1000)res5: Int = 4000
Defining twice
def twice(operation: Int => Int, target: Int) = operation(operation(target))twice(operation: Int => Int, target: Int): Int
The first parameter has the type annotation Int => Int. That
means that we can (and must) pass in a function that takes in
a single integer and returns an integer. That is, we pass in a
function such as next or doubled.
twice first calls the given function on the given integer.
Then it calls the same function another time on the return
value of the first function call.
Key point: We haven’t used def to define any function named
operation. operation is a regular parameter variable. The
only remarkable thing about it is that it stores a reference
to a function. The command operation(...) therefore calls
whichever function was passed to twice this time.
It may take a while to get used to how the types are written
out. This printout, for instance, tells us that twice refers
to a function, which...
1) takes as its first parameter a function, which in turn takes
a single Int parameter and returns an Int;
2) takes as its second parameter an integer; and
3) returns an integer.
A snack for thought
Compare:
You can pass a function as a parameter to another function.
A computer program can take another computer program as input. A compiler, for example, takes in a program and produces a different representation of it. A virtual machine takes in a program and runs it.
In mathematics, differentiation means taking in a function as “input” and producing a derivative function as “output”.
Higher-Order Functions as High-Level Abstractions
Any function with one or more parameters is an abstraction — a generalization —
of all the concrete cases that result from calling the function on different parameter
values. Our function doubled, for example, is an abstraction of all possible doublings
of an Int.
A function that takes another function as a parameter is an abstraction of abstractions.
Our function twice, for example, is an abstraction of all possible scenarios where we
twice perform an Int-to-Int operation such as doubled or next.
Functions that receive functions as parameters and/or return functions are known as higher-order functions (korkeamman asteen funktio). In contrast, the ordinary functions you already know can be referred to as first-order functions (ensimmäisen asteen funktio).
Some programming languages support only first-order functions but there are many languages that let us work with higher-order functions, too. Scala is one of the latter, as you’ve already seen.
Additional terms
You may hear programmers speak about “functions as first-class citizens” or “first-class functions”. This refers to precisely the idea that we’ve just introduced: you can store functions in variables and use functions as parameters and return functions from other functions just like you can do the same with, say, numbers. In other words, functions being first-class citizens means that there’s more than just first-order functions available in a language.
Uses for Higher-Order Functions
The twice function we just wrote isn’t too amazing. Higher-order functions may seem
like a gimmick with little practical significance. That impression is badly mistaken,
however. As we proceed with this and later chapters, you’ll find higher-order functions
to be tremendously useful. The short list of example scenarios below should give a some
idea of what’s coming.
Scenario 1
Problem: We want to be able to edit the pixels in an image in various ways, only some of which we know in advance. For instance, we want to be able to transform each pixel in a color photo into grayscale, or soften or brighten an image, or what not. We need a convenient way to say “Perform this particular operation on every pixel in the image.”
Solution: We call a higher-order method that takes in the pixel-transforming operation as a parameter and performs it on each pixel.
Scenario 2
Problem: We have an object that represents a button in a GUI. We want to be able to say “When that button is pressed, perform this operation.”
Solution: We call a higher-order method and pass in a function that will be invoked whenever the button is clicked.
Scenario 3
Problem: We need a method that sorts a list of objects — let’s say they are Person
objects. As part of the sorting algorithm, the method needs to compare two objects (at
a time) so as to determine their correct order. We want to have manifold criteria for
sorting; we could sort people by their name or by their year of birth, for example.
Therefore, we want a convenient way to write “Sort these objects; here’s how you should
compare the objects this time.”
Solution: We call a higher-order sorting method and pass in a function that 1) takes two objects; 2) requests a particular piece of information from each one (e.g., their names); and 3) uses that information to compare the objects.
Scenario 4
Problem: We have a collection of elements — let’s say each element is a measurement for a scientific study. We want to perform diverse operations on this collection, not all of which we know in advance.
Solution: We use a collection that has a flexible selection of higher-order methods. For instance, we can tell the collection to apply a particular function to each of its elements.
Later in O1, you’ll see scenarios just like the ones outlined above.
Example: Comparing Strings
Our twice function takes in a function of type Int => Int. You can also write
higher-order functions that operate on other kinds of functions, of course. As an
example, consider string comparison.
You can compare strings in different ways. For instance, the three functions below compare two strings by their lengths, by value of the contained numerical characters, and by the strings’ position according to the Unicode “alphabet”, respectively.
def compareLengths(string1: String, string2: String) = string1.length - string2.length
def compareIntContent(string1: String, string2: String) = string1.toInt - string2.toInt
def compareChars(string1: String, string2: String) = string1.compareToIgnoreCase(string2)
Let’s write a function areSorted that takes in three strings and reports whether or not
they are in the right order. What “right order” means is left for areSorted’s caller to
decide: as a fourth parameter, the caller passes in a function that compares a pair of
strings according to some criterion.
areSorted should work like this:
areSorted("Java", "Scala", "Haskell", compareLengths)res6: Boolean = true
areSorted("Haskell", "Java", "Scala", compareLengths)res7: Boolean = false
areSorted("Java", "Scala", "Haskell", compareChars)res8: Boolean = false
areSorted("Haskell", "Java", "Scala", compareChars)res9: Boolean = true
areSorted("200", "123", "1000", compareIntContent)res10: Boolean = false
areSorted("200", "123", "1000", compareLengths)res11: Boolean = true
And here is an implementation for the function:
def areSorted(first: String, second: String, third: String, compare: (String, String) => Int) =
compare(first, second) <= 0 && compare(second, third) <= 0
The type of the compare parameter is “a function that takes two
strings and returns an integer”.
We need to write round brackets around the parameter list now that
our function type has more than one parameter. (In twice, we could
have written (Int) => Int as the parameter type, but did not need to.)
areSorted uses the compare parameter twice to check whether the
values are in order.
Example: Searching a Collection
Let’s return for a moment to class AuctionHouse from Chapter 5.5 and set ourselves
these goals:
AuctionHouseobjects should have a method that we can use to get a list of all the open auctions, that is, all the items that haven’t expired or been sold already.AuctionHouseobjects should have a method that we can use to get a list of all the items whose description contains a given word.We should be able to similarly request other lists of items that match a criterion. We should be able to select any criterion we choose.
One option would be to write separate methods in AuctionHouse for each specific need:
findAllOpenItems, findAllMatchingKeyword, and so on. But that would mean that we
should correctly anticipate all the ways in which someone might wish to use our class.
A much more flexible solution is to write a generic method findAll that takes in a
criterion as a parameter and returns a list of all the items that match the given criterion.
We can represent the criterion as a function:
class AuctionHouse(val name: String):
private val items = Buffer[EnglishAuction]()
// ... other methods here ...
def findAll(checkCriterion: EnglishAuction => Boolean) =
val found = Buffer[EnglishAuction]()
for currentItem <- this.items do
if checkCriterion(currentItem) then
found += currentItem
end if
end for
found.toVector
end AuctionHouse
findAll takes a function as a parameter. That function
1) takes an auction as a parameter; 2) works out whether that
auction meets a particular criterion; and 3) returns a Boolean
to indicate whether or not the criterion was met.
The gist of the algorithm is familiar from Chapter 5.5: we start with an empty result buffer, loop through all the auctions, and check the criterion on each one. Any matching auctions we add to the result buffer.
To check the criterion, we use an if in combination with the
function we got as a parameter.
Now we can use our method:
def checkIfOpen(candidate: EnglishAuction) = candidate.isOpen
def checkIfHandbag(candidate: EnglishAuction) = candidate.description.toLowerCase.contains("handbag")
@main def findAllTest() =
val house = AuctionHouse("ReBay")
house.addItem(EnglishAuction("A glorious handbag", 100, 14))
house.addItem(EnglishAuction("Collectible Easter Bunny China Thimble", 1, 10))
println(house.findAll(checkIfOpen)) // finds both auctions
println(house.findAll(checkIfHandbag)) // finds only the first auction
In Chapter 6.3, you’ll see that Scala’s collection classes (such as Vector) have a
variety of handy higher-order methods that you can use for things like findAll, and much
more.
Example: Transforming Pixel Colors
The notion of transforming an image by applying an operation to each of its pixels already came up. Here’s an example of such an operation:
def swapGreenAndBlue(original: Color) = Color(original.red, original.blue, original.green)
Recap from Chapter 5.4: you can create a new color from RGB components: the first is red, the second is green, and the third is blue.
This function takes in a color (of a pixel) and returns another color. As the name of the function suggests...
... the resulting color has an amount of blue equal to the amount of green in the original, and vice versa.
The Pic class has a higher-order method named transformColors. With this method, we can
easily apply this operation to every pixel of an image:
val originalPic = Pic("defense.png")originalPic: Pic = defense.png
val manipulatedPic = originalPic.transformColors(swapGreenAndBlue)manipulatedPic: Pic = defense.png (transformed)
originalPic.leftOf(manipulatedPic).show()
transformColors takes in a function of type Color => Color;
here we pass in swapGreenAndBlue. transformColors applies
that function to each pixel and returns a new image with
the resulting colors.
The output of the example code.
Assignment: Color Filters
A realistic grayscale filter
An operation that is applied to the pixels of an image is often called a filter (suodin). The above program, for instance, implements a filter that swaps blue with green.
Another example is a filter that turns a color image into a grayscale one. You can
find the code for such a filter in task1.scala within the HigherOrder module.
Open that file. Read the code, which resembles the other filter that we just wrote. You’ll also find a short task description; do what it asks you to.
A+ presents the exercise submission form here.
Creating Pictures with a Higher-Order Function
Just like we transformed existing images by applying a function to each pixel, we can apply a function to generate a new image from scratch. There’s a tool for that:
val size = 256size: Int = 256 def blueGradient(x: Int, y: Int) = Color(0, 0, x.toDouble / (size - 1) * Color.Max)blueGradient(x: Int, y: Int): Color val pic1 = Pic.generate(size, size, blueGradient)pic1: Pic = generated pic pic1.show()
We first define a function that receives an x coordinate and a y coordinate and that returns the color of the pixel we want at those coordinates.
Our example function returns a color that contains no red and no green but does contain...
... an amount of blue proportional to the x coordinate. (The
constant Color.Max equals the number of different values for
each of the RGB components, which is 256 since the values are
between 0 and 255.)
We call Pic.generate (a method in Pic’s companion object;
Chapter 5.3) to produce a new image. We pass in the desired
image’s width and height and a function that will be invoked
on each pixel of the new image to determine its color.
The show method displays the image shown on the right.
Here’s another example of Pic.generate. In this example, the formula for selecting
pixel colors is a bit more involved.
def artwork(x: Int, y: Int) = if x * x > y * 100 then Red else if x + y < 200 then Black else if y % 10 < 5 then Blue else Whiteartwork(x: Int, y: Int): Color Pic.generate(size, size * 2, artwork).show()
Try it. Open task4.scala and do the mini-assignment therein.
A+ presents the exercise submission form here.
Go ahead and try generating other images as well.
Interlude: Functions with Multiple Parameter Lists
Before we move on to the rest of the chapter, you should acquaint yourself with a particular feature of the Scala language.
So far, we’ve written all the parameters of a function in a comma-separated list within a single pair of round brackets. In other words, these functions have had a single parameter list (parametriluettelo). Many functions do.
You can also define a Scala function with multiple parameter lists:
def myFunc(first: Int, second: Int)(third: Int, fourth: Int) = first * second + third * fourthmyFunc(first: Int, second: Int)(third: Int, fourth: Int): Int
Two pairs of brackets give myFunc two parameter lists.
In effect, we’ve grouped the function’s four parameters
in two separate lists.
Two pairs of brackets are also needed when we calling that function:
myFunc(1, 2)(3, 4)res12: Int = 14 myFunc(1, 2, 3, 4)-- Error: |myFunc(1, 2, 3, 4) | ^ |too many arguments for method myFunc: (first: Int, second: Int)(third: Int, fourth: Int): Int
It’s occasionally convenient to use multiple parameter lists. We won’t really go into that here, though, and in O1 you won’t need to define functions with multiple parameter lists. However, you will at times need to call some of Scala’s library functions that require you to pass in parameters in multiple lists. Our next example features such a function.
Further reading
If you want to find out more about why multiple parameter lists make sense, you can start by reading up on currying on the internet. Warning: the sources you find may not be readily understandable based on what we’ve covered in O1 (because they use either a different programming language or features of Scala that we haven’t discussed).
You may also wish to look into how multiple parameter lists interact with Scala’s type inference.
Creating Collections with a Higher-Order Function
The tabulate method
Just like we could use Pic.generate to create pictures, we can use a function to
generate collections of elements. To that end, Scala provides a method named tabulate.
Recall the two simple functions from the top of the chapter:
def next(number: Int) = number + 1next(number: Int): Int def doubled(original: Int) = 2 * originaldoubled(original: Int): Int
Let’s create a vector of integers where each element equals twice its index:
Vector.tabulate(10)(doubled)res13: Vector[Int] = Vector(0, 2, 4, 6, 8, 10, 12, 14, 16, 18)
tabulate takes two parameter lists. The first specifies the
number of elements we want and the second supplies a function
that is called on each index to generate the element for that
index.
tabulate repeatedly calls the function it receives, passing
in each index in turn. Here, doubled has been called on each
of the numbers from 0 to 9.
Here’s a similar example with next:
Buffer.tabulate(5)(next)res14: Buffer[Int] = ArrayBuffer(1, 2, 3, 4, 5)
As you see, tabulate also works for creating buffers.
More examples of tabulate
tabulate uses its parameter function on the collection’s indices, which means that the
parameter function must take in Ints. The function does not, however, have to return
an Int:
def parity(index: Int) = index % 2 == 0parity(index: Int): Boolean val parities = Vector.tabulate(5)(parity)parities: Vector[Boolean] = Vector(true, false, true, false, true) println(parities.mkString("\t"))true false true false true
parity checks whether a given integer is even and returns a
Boolean.
We can use it to produce a vector of Booleans.
Side note: the mkString method is often useful for formatting
output. Here, by way of example, we’ve used the tabulator
character \t to separate the elements in the resulting string.
And here is a vectorful of more-or-less ascending random numbers:
import scala.util.Randomdef randomElement(upperLimit: Int) = Random.nextInt(upperLimit + 1)randomElement(upperLimit: Int): Int
println(Vector.tabulate(30)(randomElement).mkString(","))0,0,1,3,4,3,2,1,4,1,0,11,2,13,12,7,6,8,16,4,7,16,14,4,10,24,19,26,15,24
You should be able to tell why the vector tends to contain bigger numbers at the tail end.
Practice on tabulate
You’ll find a very similar program in task5.scala. Read the instructions in the
comments and finish up the program.
A+ presents the exercise submission form here.
“Multidimensional” Collections
Speaking of tabulate, it sounds like it makes “tables” of things. Whence the name?
Presumably, the reason is that tabulate is a nice way to create “multidimensional”
collections. For instance, say we wish to represent this table of numbers in our program:
3 |
4 |
5 |
13 |
14 |
15 |
(Readers who have studied mathematics may see this table as a matrix.)
How could we represent this in Scala? Do we need a “two-dimensional vector” with indices for rows and columns separately, or what?
To answer that, let’s first decide how we wish to determine the value in each cell of the table. For this toy example, we’ll use this rather arbitrary function:
def dataAt(row: Int, column: Int) = row * 10 + column + 3dataAt(row: Int, column: Int): Int
Assuming we number rows and columns from zero upwards, this function returns exactly the numbers in our example table. Calling it on Column 2 in Row 1, for instance, produces 1*10+2+3 or 15.
“Multidimensionality” is just nesting
val table = Vector.tabulate(2, 3)(dataAt)table: Vector[Vector[Int]] = Vector(Vector(3, 4, 5), Vector(13, 14, 15))
We now write two numbers in tabulate’s first parameter list:
the height and width of the collection.
The function in the second parameter list takes in as many integers as there are dimensions (here: two). As before, it returns an element for the collection (here: an integer).
We get a vector of “rows”, each of which is a vector.
As the type says: this is a vector whose elements are vectors whose elements are numbers. What we have chosen to perceive as two-dimensionality is actually just the nesting of collections within an outer collection.
We don’t actually need tabulate for constructing a two-dimensional collection. We can
also construct one manually:
val twoColumnsFourRows = Vector(Vector(1, 2), Vector(3, 4), Vector(5, 6), Vector(7, 8))twoColumnsFourRows: Vector[Vector[Int]] = Vector(Vector(1, 2), Vector(3, 4), Vector(5, 6), Vector(7, 8))
Frequently asked question: Which index is the row and which is the column?
Answer: That depends entirely on how the programmer has nested the collections in the particular program. You can write a program where each inner vector represents a row and lists the elements in each column of that row; you can just as well write a program where each inner vector represents a column and lists the elements of each row in that column. In this chapter, we have happened to use the former style, but there is no hard-and-fast rule for this.
In fact, it’s not necessary in the first place to use two separate indices and nested collections. We could represent a two-by-three table of numbers with just one single-dimensional vector of six elements, deciding that, say, the indices from 0 to 2 represent the first row and the indices from 3 to 5 the second row. Usually, it’s more convenient to nest collections, though.
Depending on circumstances, how you choose to index a collection can have an impact on efficiency. O1’s follow-on courses will say more about that aspect.
Looping over nested collections
Since a “multidimensional” collection is just a bunch of single-dimensional collections
nested inside an outer collection, there is nothing fundamentally new about using such
a collection. You can process a nested collection just like you’ve processed other
collections. A for loop works, for instance.
Our next example first uses tabulate to produce a multiplication table:
def multiply(row: Int, column: Int) = (row + 1) * (column + 1)multiply(row: Int, column: Int): Int val vectorOfRows = Vector.tabulate(10, 10)(multiply)vectorOfRows: Vector[Vector[Int]] = Vector(Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), Vector(2, 4, 6, ..., 20), , ..., Vector(10, 20, 30, ..., 100))
Suppose we now wish to print out this multiplication table row by row. To do that, we can loop over the outer vector. Each of the inner vectors that it contains represents a row in the table.
for numbersOnRow <- vectorOfRows do println(numbersOnRow.mkString("\t"))1 2 3 4 5 6 7 8 9 10 2 4 6 8 10 12 14 16 18 20 3 6 9 12 15 18 21 24 27 30 4 8 12 16 20 24 28 32 36 40 5 10 15 20 25 30 35 40 45 50 6 12 18 24 30 36 42 48 54 60 7 14 21 28 35 42 49 56 63 70 8 16 24 32 40 48 56 64 72 80 9 18 27 36 45 54 63 72 81 90 10 20 30 40 50 60 70 80 90 100
Since vectorOfRows is a Vector[Vector[Int]], whose elements
are vectors, too, ...
... each time we pick out an element from the outer vector,
we get one of the inner vectors. The variable numbersOnRow
has the type Vector[Int].
Each inner vector is an ordinary vector of integers. Here, what we do with it is format its contents as a string and print that string.
Merging Pictures with combine
This optional section continues with our image-processing theme and presents additional examples of higher-order methods.
Averaging two images
Suppose we want to combine these two pictures:
val pic1 = Pic("lostgarden/tree-tall.png")pic1: Pic = lostgarden/tree-tall.png
val pic2 = Pic("lostgarden/girl-horn.png")pic2: Pic = lostgarden/girl-horn.png
One way to combine images is to compute a pixel-by-pixel average of their color values at each position. That is, at each pair of coordinates, we get the color of both images and apply the following function to get the output color at that position:
def naiveAverage(color1: Color, color2: Color) =
Color((color1.red + color2.red) / 2,
(color1.green + color2.green) / 2,
(color1.blue + color2.blue) / 2)
We also need a way to apply this operation to the target image. That’s easily done
with the combine method that is available on Pic objects. This method combines
two images using whichever function we pass to it:
val combinedPic = pic1.combine(pic2, naiveAverage)combinedPic: Pic = combined pic combinedPic.show()
Try the program for yourself; you can find it as Example7.scala. Try running it
on other inputs as well, if you feel like it.
An image as a stencil for another
Another way to combine two images is to use one of them as a “stencil” or “silhouette” that “selects” a shape in the other image.
Two source images.
A combination of the two.
The optional assignment in task6.scala lets you do that.
A+ presents the exercise submission form here.
More combinations of images
If you enjoyed the previous exercise, you may also want to experiment with this code:
val photo = Pic("kid.png").scaleBy(1.3)
val drawing = Pic("bird.png")
def isBright(color: Color) = color.intensity > 60
def selectColor(c1: Color, c2: Color) = if isBright(c2) then Black else c1
photo.combine(drawing, selectColor).show()
The intensity method essentially tells you how
bright the color is. Pure White has an intensity
of 255, for example, and pure Black an intensity
of zero.
What does the resulting image look like and why?
What happens if you give intensity a threshold more or less than 60? Try 20 and 200, for instance.
What happens if you swap c1 and c2 in the body of selectColor?
Practice Writing Higher-Order Functions
In each of the three programming assignments that conclude this chapter, you’ll use higher-order functions to work on collections. These assignments differ from earlier ones in that now, you won’t just call higher-order functions but also implement them yourself.
These programs, too, are in module HigherOrder.
Assignment: repeatForEachElement
In this assignment, you’ll implement a higher-order function that takes in a function
and calls that function on each element in a vector of integers. In task7.scala, you can
find the beginnings of a function definition and a couple of use cases, but the function
body is missing.
Implement the function so that it works as described. Once you do that, the use cases at
the end of task7.scala will also work and produce the specified output.
Instructions and hints:
The second parameter of
repeatForEachElementis a function of typeInt => Unit. Which is why you can pass in functions likeprintCubeandprintIfPositivewhen you callrepeatForEachElement.You’ll probably want to use a
forloop.
A+ presents the exercise submission form here.
Assignment: transformEachElement
In this assignment, you’ll write an entire higher-order function. The function should take two parameters: a buffer and a transformation function. It should call the transformation function on each element in the buffer and replace that element with the transformation function’s return value.
(This idea is similar to what transformColor did for images, above, except that you’ll
now modify the existing buffer “in place” instead of generating a new collection.)
For a detailed task description, see task8.scala.
You may find the hints below helpful in case updating the buffer’s contents gives you trouble either at compile-time or at run-time.
If replacing a value in the buffer gives you a build error
Perhaps you got the error reassignment to val or something similar? If so, it’s good to review this invalid code from Chapter 5.5:
def incrementElements(elements: Buffer[Int]) =
for number <- elements do
number = number + 1
To begin with, there’s a problem in principle with what the code tries
to do. We have a variable number that receives an element from the
buffer, but this is otherwise just a regular Int variable. The
variable stores just a single number, not a reference to the buffer.
Therefore, it’s not possible use number to access the buffer where
the number came from or to change the contents of that buffer.
Moreover, that code has the problem that the loop variable (here:
number) is a val, not a var. So you cannot assign anything to
it, which is the direct cause of the compiler’s complaint.
To replace a particular element within a buffer, mention the buffer and the index:
myBuffer(index) = newElement
But how to iterate over the indices? Either of the following does the trick:
for index <- myCollection.indices do
...
for index <- 0 until myCollection.size do
...
If replacing a value in the buffer crashes your code at runtime
Perhaps your code looks something like this and produces
a ConcurrentModificationException error when run?
var index = 0
for stringElem <- buffer do
buffer(index) = newElement
index += 1
There’s a constraint that we have to be mindful of here:
Whichever collection on the right of the <- arrow must
not be modified within the loop body; otherwise, you’ll
get that runtime error. Here, the collection is a buffer;
the loop body must not modify the contents of that buffer.
That constraint isn’t nearly as awkward as it may initially sound. In fact, attending to it will produce a slightly simpler solution for this problem.
Instead of iterating over the buffer itself, iterate over the buffer’s indices. Either of the following does the trick:
for index <- buffer.indices do
buffer(index) = ...
for index <- 0 until buffer.size do
buffer(index) = ...
This way, the loop iterates over a Range rather than
the buffer. The problem with the original solution goes
away. You also don’t need to update a separate var in
order to track the index.
(Side note: The constraint that came up has to do with how loops are implemented using iterators; Chapter 11.3. Iterators are useful for iterating over various kinds of data structures. However, their correct behavior cannot be guaranteed if modifications to the structure are allowed to happen concurrently with iteration.)
A+ presents the exercise submission form here.
Assignment: turnElementsIntoResult
In this assignment, you’ll implement one more higher-order function as well as a couple of use cases for it.
You can tackle this assignment in two phases. In Phase 1, define turnElementsIntoResult
as instructed in task9.scala and illustrated in the animation below. (In this example,
the addToSum function is passed as a parameter to turnElementsIntoResult, just like
in the first phase of this exercise.)
Additional hint for Phase 1
Keep the intermediate result stored in the gatherer variable. Loop over the elements in the collection and, at each elements, apply the given operation to the intermediate result and the current element. This gives you a new intermediate result.
Make sure that turnElementsIntoResult correctly produces the sums (which is the use case
in the given code). Then proceed to Phase 2. Follow the instructions to define addAbsolute,
positiveCount, and productOfNonZeros. Use those functions as parameters to
turnElementsIntoResult.
Hint for Phase 2: summing absolute values
addAbsolute should do basically the same as addToSum,
except that you don’t add the second number but its
absolute value. (myNumber.abs works.)
Hint for Phase 2: counting positive numbers
Here’s one way to count the positive elements: We start with a count of zero positive elements found. At each element, we check whether it’s positive, which gives us a new count: if the element was positive, the count is greater than the previous result; if not, the count is unchanged.
turnElementsIntoResult, which you defined earlier, takes
care of iterating over the elements. The function positiveCount
should take care of just the small subtask identified above: it
takes in an intermediate result (count) and a single element and
produces a new count that is either equal to or greater by one
than the given count.
Hint for Phase 2: product of non-zeros
You can compute the product of non-zero elements much like you counted positive numbers.
This time, the intermediate result does not go up by one or zero at each element. Instead, you should multiply the result by the element (unless the element is zero, in which case it is ignored).
A+ presents the exercise submission form here.
On Collections and Higher-Order Functions
The three tasks above featured very generic higher-order functions that enable you to do a great many things with a collection: you can repeat any operation on each element, transform each element to another, or use the elements to compute a result. With higher-order functions such as these, you can operate on collections without having to write loops: you just pass in a function that says what do with each element, and the higher-order function takes care of repetition.
Since functions such as these are so practical, they are also available as part of the Scala API. Soon in Chapter 6.3, you’ll see that Scala’s collections have an assortment of flexible higher-order methods that you’ll find extremely useful. Some of those methods bear a great resemblance to the three functions that you just wrote.
But I don’t want to def all those function names!
Perhaps you find it hard to believe that it could be more practical
to use higher-order functions than loops to work with collections.
Perhaps you find it irritating to define all those parameter
functions separately and to come up with contrived names for each
one (such as printIfPositive).
It’s true that it’s sometimes a pain to have to name each tiny parameter function. But we’ll salve that pain in the next chapter with anonymous functions.
Summary of Key Points
Functions are data, too. You can store them in variables, pass them as parameters to other functions, and so forth.
A higher-order function is a function that operates on one or more other functions. Such functions can implement very generic and useful services: you can call a highly abstract higher-order function and pass in another function that specifies precisely what the higher-order function should do.
You can nest collections within another collection. This is one way of representing two-dimensional or multidimensional information.
Links to the glossary: higher-order function; parameter list; filter.
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 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 for this page
The grayscale assignment draws inspiration from a similarly themed assignment by Jessen Havill.
The hidden-pics assignments are adaptations of a programming assignment published by Nick Parlante and originally conceived by David J. Malan.
The two pictures in the image-averaging example are by Daniel Cook, who has published them under the Creative Commons Attribution 3.0 license.
The painting from the color-swapping example is The Defense of the Sampo by Akseli Gallén-Kallela.
nextsimply adds one to its parameter and returns the result.