Mike Slinn
ScalaCourses.com

Higher-Order Functions

— Draft —

Published 2014-07-03. Last modified 2019-07-12.
Time to read: 1 minutes.

Scala provides some powerfully expressive and efficient iteration mechanisms. This lecture explores functional iteration and explains some foundational concepts.

Recall that an Option is a collection of zero or one elements. The None subclass of Option contains zero elements, and the Some subclass contains one element. If you are a bit fuzzy on how Option works, please review the lecture on Option, Some and None of the Introduction to Scala course before diving into this lecture. You also might want to review the Functions are First Class, Closures and More Fun With Functions lectures of the same course.

The sample code for this lecture can be found in courseNotes/src/main/scala/HigherFun.scala.

Higher-Order Functions

Let’s say we have an Option of Int that needs to have an operation performed upon it, such as squaring the element if present.

Scala REPL
scala> def square(num: Int): Int = num * num
square: (num: Int)Int

scala> scala> val maybeInt = Some(3)
maybeInt: Some[Int] = Some(3)

scala> scala> maybeInt.map(x => square(x))
res1: Some[Int] = Some(9)

The map method iterates over each element of the Option, and passes each element to the square method. Another Option is created from the result, and because squaring an Int always results in another Int, the type of the function passed into the map method is Int => Int. In other words, the function passed in receives an Int parameter and returns another Int. map is called a higher-order function because it receives a function as a parameter. A higher-order function is a function that takes one or more functions as an input parameter and/or outputs a function.

Here is another example, using the standard Scala toDouble method which converts an Int to a Double; this map operation therefore transforms an Option[Int] into an Option[Double].

Scala REPL
scala> maybeInt.map( x => x.toDouble )
res2: Some[Double] = Option(3.0)
map can convert a container of one type of element into a similar container of another type of element

The type of the function argument is Int => Double. Let’s try this same map operation with a different collection type. In this example, the input Array[Int] is transformed into the output Array[Double].

Scala REPL
scala> Array(1, 2, 3).map( x => x.toDouble )
res3: Array[Double] = Array(1.0, 2.0, 3.0)

Higher Order Function Shorthand

Scala allows us to write this same operation more succinctly. The collection item passed in by map to the anonymous function is only referenced once, so there is really no need to give it a name. The underscore (_) refers to the current list item as map iterates through the collection’s items.

Scala REPL
scala> maybeInt.map(_.toDouble)
res4: Some[Double] = Some(3.0)

Now let’s rewrite maybeInt.map(x => square(x)) using progressively terser shorthands. First we can elide the definition and single usage of the temporary variable to _.

Scala REPL
scala> maybeInt.map(square _)
res5: Some[Int] = Some(9)

If only one parameter is passed to a higher-order function, the underscore can also be omitted.

Scala REPL
scala> maybeInt.map(square)
res6: Some[Int] = Some(9)

Using infix notation we can even do away with the parentheses.

Scala REPL
scala> maybeInt map square
res7: Some[Int] = Some(9)

The Partially Applied Functions lecture has a more in-depth discussion of lifting methods to functions, also known as eta expansion.

Lambdas

The function passed into map could be formally defined, like square and toDouble, or it could be anonymous, as we shall now see. BTW, anonymous functions are often called lambdas. This lambda doubles whatever is passed into it.

Scala REPL
scala> maybeInt.map(_ * 2)
res8: Some[Int] = Some(6)

We are not able to use the underscore shorthand in higher order functions if the bound variable is referenced more than once in the anonymous function.

Scala REPL
scala> maybeInt.map(x => x * x)
res8: Some[Int] = Some(9)

Write Your Own Higher-Order Functions

Periodic Invocation

This higher-order function accepts an interval length in seconds, and a function value, then executes the function periodically according to the specified interval. Notice that the Java Timer and TimerTask classes are imported inside the TimedTask object, and that the run method specified by the Java TimerTask interface is implemented in Scala code. The higher-order function apply was written to accept two parameter lists; this was not required, however the usage of the higher-order function is cleaner when one function is provided per parameter list. 

object TimedTask {
import java.util.Timer
import java.util.TimerTask

def apply(intervalSeconds: Int=1)(op: => Unit) {
val task = new TimerTask {
def run = op
}
val timer = new Timer
timer.schedule(task, 0L, intervalSeconds*1000L)
}
}

The function value is shown in yellow twice in the above code; the second time it is shown the function is not invoked. Instead, this assignment connects the run method required by the Java TimerTask interface to the implementation passed via the apply method’s second parameter list.

If a lambda has more than one statement, the lambda must be surrounded with curly braces instead of parentheses

The code below uses the TimedTask object; you can find this code in TimedTask.scala, in the courseNotes directory. You can use curly braces to surround lambdas any time.

Shell
object TimedFun extends App {
var i = 0

TimedTask(1) {
  println(s"Tick #$i")
  i = i + 1
  }
}

You can run this program by typing.

Scala REPL
$ scala> sbt "runMain TimedFun"

Here is some sample output. 

Tick #0
Tick #1
Tick #2
Tick #3
Tick #4
Tick #5
Tick #6
Tick #7

Timing a Task

Scala call by name parameters are recomputed EACH time they are executed.

This next higher-order function accepts a block of code and times how long it takes to execute. The method prints out the time it took and returns the result of the method execution.

The block parameter is lazily evaluated; it is a call by name parameter and is only evaluated if the body of the time method specifically invokes block. The block parameter could accept an expression or a block of code that does not accept parameters. It could also accept a variable or a constant value of any type, because all types are subclasses of Any.

The return type of the time method is Any, so it can return any type of result. We will rewrite this method in the Parametric Types lecture later in this course so that it returns a strongly typed result instead of Any. 

def time(block: => Any): Any = {
val t0 = System.nanoTime()
val result: Any = block
val elapsedMs = (System.nanoTime() - t0) / 1000000
println("Elapsed time: " + elapsedMs + "ms")
result
}

Let’s use the time method to see how long it takes to calculate Pi to 1,000,000 decimal places. Instead of writing a lambda, I have defined a method called calculatePiFor.

Scala REPL
scala> def calculatePiFor(decimalPlaces: Int): Double = {
     |   var acc = 0.0
     |   for (i <- 0 until decimalPlaces)
     |     acc += 4.0 * (1 - (i % 2) * 2) / (2 * i + 1)
     |   acc
     | }
calculatePiFor: (decimalPlaces: Int)Double

scala> scala> time(calculatePiFor(100000))
Elapsed time: 3ms
res24: Any = 3.1415826535897198

calculatePiFor is called with decimalPlaces set to 1,000,000. The entire invocation with the bound parameter is passed into the time method, not just the unbound calculatePiFor method like we saw earlier. A Function1[Int, Double] version of calculatePiFor is provided in multi/package.scala and could just as well be used here.

You can run this code using SBT by typing.

Scala REPL
$ scala> sbt "runMain TimedPi"

Exercise – Using the Predefined WrappedString Implicit Class

Write a one line program using the REPL that reverses every word in a text file – any file you have access to on your computer’s hard drive. /etc/passwd is fine.

Hints

  1. At the REPL prompt, type a string, then dot (.), then tab. Starting with Scala 2.11.8, the REPL reports implicit methods.
  2. Implicit methods that make the WrappedString class available for implicit conversions are predefined by predef.scala; does it has any useful methods?
  3. Since WrappedString is a predefined implicit class, will your final code actually need to mention that class?
  4. String.split(" ") is the dual of Array.mkString(" ").
  5. String.reverse reverses a String.

Solution

object StringReverser {
import scala.sys.process._
"cat /etc/passwd".!!.split(" ").map(_.reverse).mkString(" ")
}

Executing the above results in. 

TN-U:445:91:*:ecivreSlacoL
::81-5-1-S,:445:81:*:METSYS TN-U:445:02:*:ecivreSkrowteN
::91-5-1-S,ecivreSlacoL\YTIROHTUA TN-U:4927694924:4927694924:*:rellatsnIdetsurT
::445-23-5-1-S,:445:445:*:srotartsinimdA
::02-5-1-S,ecivreSkrowteN\YTIROHTUA ekiM
hsab/nib/:tseuG/emoh/:105-6299776593-9239486513-5407444803-12-5-1-S,tseuG\raeB-U:315:105:desunu:tseuG
hsab/nib/:rotartsinimdA/emoh/:005-6299776593-9239486513-5407444803-12-5-1-S,rotartsinimdA\raeB-U:315:005:desunu:rotartsinimdA
::4648741722-1362923581-4408301381-9462258143-588800659-08-5-1-S,rellatsnIdetsurT\ECIVRES ekiM\raeB-U:315:0001:desunu:nnilS
ekiM/emoh/:0001-6299776593-9239486513-5407444803-12-5-1-S,nnilS
hsab/nib/:resUsutadpU/emoh/:2001-6299776593-9239486513-5407444803-12-5-1-S,resUsutadpU\raeB-U,resUsutadpU:315:...

The solution can be found in the solution.StringReverser.sc Scala worksheet.

Reading Binary Files Using Higher-Order Functions

Now that we know how higher-order functions work, we can use them to read binary files.

io.Source.fromFile uses an implicit to provide the value of a codec that specifies the character set used. You can discover the default codec like this.

Scala REPL
scala> implicitly[io.Codec]
res0: scala.io.Codec = UTF-8

You can read a binary file into a byte array by explicitly specifying an 8-bit codec, such as ISO-8859-1. 

import sys.process._
io.Source.fromFile("which scalac".!!.trim, "ISO-8859-1").map(_.toByte).toArray

Notice that I ran a bash command, "which scalac", using the Scala Process facility. I trimmed off the trailing newline returned from the process before passing the resulting fully qualified name to io.Source.fromFile. fromFile returns an Iterator of Character. The map method I just showed converts each Character to a Byte. In other words, map converts the Iterator[Character] into an Iterator[Byte]. The resulting Iterator[Byte] is converted to an Array[Byte] by the toArray method.

Since we want to always ensure that the source file is closed, this incantation is preferred. 

val source = scala.io.Source.fromFile("which scalac".!!.trim, "ISO-8859-1")
val byteArray = source.map(_.toByte).toArray
source.close()

Even better, try/catch/finally should be used to guarantee source is closed after it is read. 

val source = scala.io.Source.fromFile("which scalac".!!.trim, "ISO-8859-1")
try { source.map(_.toByte).toArray } finally { source.close() }

This code fragment does a lot of character conversions, which is inefficient. A more efficient mechanism is shown in the Immutable Collections lecture.

Exercise – What does this program do?

Shell
import java.io.File
import java.sql.Date

object HigherFun extends App {
def uploadForm(saec: SignedAndEncodedComplete)(selectBucketUrl: PublisherConfig => String): String = {
s"""<form action="${selectBucketUrl(saec.pubConf)}" method="post" enctype="multipart/form-data">
<input type="hidden" name="key" value="${saec.fileName}">
<input type="hidden" name="AWSAccessKeyId" value="${saec.accessKey}">
<input type="hidden" name="acl" value="${saec.acl}">
<input type="hidden" name="policy" value="${saec.encodedPolicy}">
<input type="hidden" name="signature" value="${saec.signedPolicy}">
<input type="hidden" name="Content-Type" value="${saec.contentType}">
Select <code>${saec.fileName}</code> for uploading to S3:
<input name="file" type="file">
<br>
<input type="submit" value="Upload">
</form>""".stripMargin
}

val file = new File("/etc/passwd")
val pubConf = PublisherConfig(
name="blah",
awsAccountName="blah",
awsSecretKey="blah",
awsAccessKey="blah",
bucketName="bucket1")
val saec = SignedAndEncodedComplete(
fileName=file.getAbsolutePath,
contentLength=file.length,
accessKey="blahBlah",
secretKey="blah Blah",
acl="private",
pubConf=pubConf,
encodedPolicy="blah blah",
signedPolicy="blah blah",
contentType="blah blah")

val uf1 = uploadForm(saec)(_.homeworkBucketUrl(file.getName))
val uf2 = uploadForm(saec)(_.uploadBucketUrl(file.getName))
println(uf1)
println(uf2)

case class PublisherConfig(
name: String,
awsAccountName: String,
awsSecretKey: String,
awsAccessKey: String,
bucketName: String,
created: Date = new Date(System.currentTimeMillis),
active: Boolean = false,
id: Option[Long] = None
) {
def uploadBucketUrl(file: String): String = s"https://upload.$bucketName/$file"
def homeworkBucketUrl(file: String): String = s"https://homework.$bucketName/$file"
}

case class SignedAndEncodedComplete(
fileName: String,
contentLength: Long,
accessKey: String,
secretKey: String,
acl: String,
encodedPolicy: String,
signedPolicy: String,
pubConf: PublisherConfig,
contentType: String
)
}

Solution

Output is. 

<form action="https://homework.bucket1/passwd" method="post" enctype="multipart/form-data">
<input type="hidden" name="key" value="/etc/passwd">
<input type="hidden" name="AWSAccessKeyId" value="blahBlah">
<input type="hidden" name="acl" value="private">
<input type="hidden" name="policy" value="blah blah">
<input type="hidden" name="signature" value="blah blah">
<input type="hidden" name="Content-Type" value="blah blah">
Select <code>/etc/passwd</code> for uploading to S3:
<input name="file" type="file">
<br>
<input type="submit" value="Upload">
</form>
<form action="https://upload.bucket1/passwd" method="post" enctype="multipart/form-data">
<input type="hidden" name="key" value="/etc/passwd">
<input type="hidden" name="AWSAccessKeyId" value="blahBlah">
<input type="hidden" name="acl" value="private">
<input type="hidden" name="policy" value="blah blah">
<input type="hidden" name="signature" value="blah blah">
<input type="hidden" name="Content-Type" value="blah blah">
Select <code>/etc/passwd</code> for uploading to S3:
<input name="file" type="file">
<br>
<input type="submit" value="Upload">
</form>

You can play with this program in courseNotes/solutions; it is called HigherFun.scala. Run it like this.

Scala REPL
$ scala> sbt "runMain solutions.HigherFun"
Previous lecture:

Next lecture:
* indicates a required field.

Please select the following to receive Mike Slinn’s newsletter:

You can unsubscribe at any time by clicking the link in the footer of emails.

Mike Slinn uses Mailchimp as his marketing platform. By clicking below to subscribe, you acknowledge that your information will be transferred to Mailchimp for processing. Learn more about Mailchimp’s privacy practices.