Higher-order methods of collections

When working with collections, such as arrays or lists, we often use for-loops to perform some operation on all the elements of the collection:

scala> val C = List("Introduction to Programming",
     |              "Programming Practice",
     |              "Data Structures",
     |              "Programming Principles",
     |              "Algorithms",
     |              "Programming Languages")
C: List[String] = List(Introduction to Programming, Programming
Practice, Data Structures, Programming Principles, Algorithms, 
Programming Languages)

scala> for (e <- C) 
     |   println(e)
Introduction to Programming
Programming Practice
Data Structures
Programming Principles
Algorithms
Programming Languages

The interesting part of this loop is the print statement. Modern programming languages like Scala make it possible to write code that concentrates on this part, not on the loop.

Instead of writing a for-loop, we can use the foreach method of the collection. This is a higher-order method, that is, it takes a function object as its argument.

The loop above is changed to this:

scala> C.foreach((x: String) => println(x))
Introduction to Programming
Programming Practice
Data Structures
Programming Principles
Algorithms
Programming Languages

As we learnt in the previous section, this can be simplified a bit, because the Scala compiler knows that the argument of foreach has to be a function object of type String => Unit. Therefore we are allowed to omit the type of the argument:

 
scala> C.foreach(x => println(x))
Introduction to Programming
Programming Practice
Data Structures
Programming Principles
Algorithms
Programming Languages

In our example, the function object has only one single argument and this argument is used only once in the result expression. Under these exact circumstances we are allowed to omit the x => part completely and to replace the parameter in the function literal by an underscore:

scala> C.foreach(println(_))
Introduction to Programming
Programming Practice
Data Structures
Programming Principles
Algorithms
Programming Languages

Actually, in this case the function literal consists of a single function call only, so in this case we simply write the name of that function:

scala> C.foreach(println)
Introduction to Programming
Programming Practice
Data Structures
Programming Principles
Algorithms
Programming Languages

Here is another example where we use foreach to compute the sum of the elements of a collection:

scala> val l = List(15, 39, 22, 98, 37, 19, 5)
l: List[Int] = List(15, 39, 22, 98, 37, 19, 5)
scala> var sum = 0
sum: Int = 0
scala> l.foreach(sum += _)
scala> sum
res1: Int = 235

Note the shortcut syntax we used for the function object (x: Int) => sum += x.

Exists, forall, and count

Often one goes through the elements of a collection to determine one of the following properties:

• Does the collection contain an element with a certain property?
• Do all the elements have the property?
• How many of the elements have the property?

This can be done nicely using the higher-order methods exists, forall, and count. They all require a function object that maps the elements to Boolean.

Here are some examples:

scala> val C = List("Introduction to Programming",
     |              "Programming Practice",
     |              "Data Structures",
     |              "Programming Principles",
     |              "Algorithms",
     |              "Programming Languages")
C: List[String] = List(Introduction to Programming, Programming
Practice, Data Structures, Programming Principles, Algorithms, 
Programming Languages)

scala> C.count(_ contains "Programming")
res2: Int = 4

scala> C.count(x => !(x contains "Programming"))
res5: Int = 2

scala> C.forall(_ contains " ")
res6: Boolean = false

scala> C.exists(x => !(x contains " "))
res7: Boolean = true

scala> C.exists(_ contains "Algo")
res8: Boolean = true

scala> C.forall(_.toUpperCase contains "A")
res9: Boolean = true

Filtering a collection

Often we want to pick a subset of a collection consisting of all the elements that satisfy a certain condition. The higher-order methods filter and filterNot can do this. Again, they take as argument a function object that maps an element to a Boolean.

Here are some basic examples, using the list from above:

scala> C.filter(_ contains " ")
res0: List[String] = List(Introduction to Programming, Programming
Practice, Data Structures, Programming Principles, Programming
Languages) 

scala> C.filterNot(_ contains " ")
res1: List[String] = List(Algorithms)

Note that filterNot does the same as filter, but reverses the sense of the condition.

Here are some interesting filters using our file of 113809 English words:

scala> words filter (_ contains "issis")
res2: List[String] = List(missis, missises, narcissism, narcissisms, narcissist, narcissists)

scala> words filter (_.length > 20)
res3: List[String] = List(counterdemonstrations,
hyperaggressivenesses, microminiaturizations) 

scala> words.filterNot(x => (x contains "e") || (x contains "a") || 
       (x contains "o") || (x contains "i") || (x contains "u")) 
res4: List[String] = List(by, byrl, byrls, bys, crwth, crwths, cry,
crypt, crypts, cwm, cwms, cyst, cysts, dry, dryly, drys, fly, flyby,
flybys, flysch, fry, ghyll, ghylls, glycyl, glycyls, glyph, glyphs,
gym, gyms, gyp, gyps, gypsy, hymn, hymns, hyp, hyps, lymph, lymphs,
lynch, lynx, my, myrrh, myrrhs, myth, myths, nth, nymph, nymphs,
phpht, pht, ply, pry, psst, psych, psychs, pygmy, pyx, rhythm,
rhythms, rynd, rynds, sh, shh, shy, shyly, sky, sly, slyly, spry,
spryly, spy, sty, stymy, sylph, sylphs, sylphy, syn, sync, synch,
synchs, syncs, syzygy, thy, thymy, try, tryst, trysts, tsk, tsks,
tsktsk, tsktsks, typp, typps, typy, why, whys, wry, wryly, wych, wynd,
wynds, wynn, wynns, xylyl, xylyls, xyst, xysts) 

Filtering is the essence of the Sieve of Erathosthenes, so it is natural that we can write it concisely using filter:

val n = args(0).toInt
val sqrtn = math.sqrt(n).toInt

var s = (2 to n).toList

while (s.head < sqrtn) {
  print(s.head + " ")
  s = s.tail filter (_ % s.head != 0)
}
println(s mkString " ")

Transforming a collection

Another common operation is to create a new collection by somehow transforming every element of the existing collection.

This can be done using the higher-order function map. Its argument is a function object that maps the elements of the collection to its transformed value. The new collection can have the same or a different type:

scala> C
res4: List[String] = List(Introduction to Programming, Programming
Practice, Data Structures, Programming Principles, Algorithms,
Programming Languages) 

scala> C map (_.length)
res5: List[Int] = List(27, 20, 15, 22, 10, 21)

scala> C map (_.toUpperCase)
res6: List[String] = List(INTRODUCTION TO PROGRAMMING, PROGRAMMING
PRACTICE, DATA STRUCTURES, PROGRAMMING PRINCIPLES, ALGORITHMS,
PROGRAMMING LANGUAGES) 

scala> C map (x => x + " " + x)
res7: List[String] = List(Introduction to Programming Introduction to
Programming, Programming Practice Programming Practice, Data
Structures Data Structures, Programming Principles Programming
Principles, Algorithms Algorithms, Programming Languages Programming
Languages) 

Sorting a collection

We have already seen that we can sort an array or another sequence by using its sorted method. This always sorts the elements using the natural ordering of the element type.

If we want to sort with a different ordering, we should use the higher-order method sortWith. It takes as an argument a function object that maps two elements \(a\) and \(b\) to a Boolean. The function should return true iff element \(a\) should appear before element \(b\) in the desired sorted order. (In other words, the function object must implement the \(\leq\)-relationship.)

Here is an example:

scala> words sortWith ((a, b) => a.length > b.length)
res9: List[String] = List(counterdemonstrations,
hyperaggressivenesses, microminiaturizations, counterdemonstration,
counterdemonstrators, hypersensitivenesses, microminiaturization,
representativenesses, anticonservationist, comprehensivenesses,
counterdemonstrator, counterinflationary, counterpropagations,
counterretaliations, disinterestednesses, electrocardiographs,
extraconstitutional, hyperaggressiveness, inappropriatenesses,
inconsideratenesses, interdenominational, irreconcilabilities,
miscellaneousnesses, multidenominational, absentmindednesses,
adventitiousnesses, antiadministration, antidiscrimination,
apprehensivenesses, biodegradabilities, bloodthirstinesses,
cantankerousnesses, characteristically, chemotherapeutical,
counteraccusations, counteraggressions, counterpropagati... 

It sorts the elements of the words list in order of decreasing length.