Scala Saturday – The reduce Method

If you have a collection of numbers that you want to sum or multiply together, Scala’s collection classes all define both a sum operation and a product operation:

ScalaDocs for Scala Collection sum and product Methods
Array sum product
List sum product
Seq sum product
Set sum product

But what if, for some reason, you want to implement sum or product yourself? Well, it turns out that sum and product are both just special cases of a more general operation that the collection modules also define: reduce. The reduce operation takes all the elements in a collection and combines them in some way to produce a single value. It uses a binary operation to combine the first two values. Then it takes the result of that first combination and combines it with the next element in the collection, and then the next, and so on through the end of the collection.

Here’s an illustration of how to use reduce to implement a product operation:

Taking a list of [2,5,3,6], reduce multiplies 2 and 5 to produce 10, then 10 and 3 to produce 30, and finally 30 and 6 to get the final result of 180.
Using Reduce to Calculate the Product of All Numbers in a List

The code looks like this:

val product = List(2,5,3,6) reduce {
  (x,y) => x * y
}
// product: Int = 180

You can be even more succinct by employing the underscore, Scala’s shorthand for the lambda’s input arguments:

val product = List(2,5,3,6).reduce(_*_)
// product: Int = 180

Another special case of reduce is mkString, e.g., List.mkString—also known as a join operation—which allows you to concatenate a sequence of values together into a string with a separator between each value. Here’s how it works:

Taking a list of strings ["do","mi","sol","do"], reduce combines "do" and "mi" to produce "do-mi", and then combines "do-mi" and "sol" to produce "do-mi-sol", and finally "do-mi-sol" and "do" to produce the final result of "do-mi-sol-do"
Using Reduce to Join a List of Strings Together with a Separator

See how similar it is to the product operation above? If you should want to implement mkString yourself, you could use reduce like this:

val joined =
  List("do","mi","sol","do") reduce {
    (x,y) => x + "-" + y
  }
// joined: String = do-mi-sol-do

Or again, with the shorthand:

val joined =
  List("do","mi","sol","do").
    reduce(_ + "-" + _)
// joined: String = do-mi-sol-do

Here is the documentation on reduce in each of the collection classes:

Now a few of caveats about reduce:

  • You cannot use reduce on an empty collection. You will get an exception if you do, so make sure you check to make sure your collection is not empty before you pass it to reduce. (Scala provides an alternative, reduceOption, that does not throw an exception, but represents the result as an Option.)

  • The result of a reduce operation is always the same type as the elements in the collection. In other words, you can only reduce a collection of type A to a value of type A. You cannot reduce a collection of type A to a value of type B.

  • Finally, order matters if the order of your binary operation matters. In other words, with addition and multiplication, order does not matter. That is, a + b is the same as b + a. (Mathematicians say that such a function is commutative.) But with something like subtraction, order does matter. In other words, a − b does not necessarily produce the same result as b − a. So make sure that your binary operation applies the reduction to its operands in the correct order.

Having noted these caveats, next week, we will cover the fold operation. It operates almost the same way as reduce in that it walks a collection, applying a binary operation to each element. The fold operation cannot help us with that last point—order still matters—but it can handle an empty collection and, if necessary, produce a result that is of a type different from the type of the source collection’s elements.

F# Friday – The reduce Function

If you have a sequence of numbers that you want to sum, F# defines the sum operation in all of the sequential collection modules:

But what if you want to multiply all those numbers together? Well, it turns out that sum is just a special case of a more general function that the sequential collection modules also define: reduce. The reduce operation takes all the elements in a collection and combines them in some way to produce a single value. It uses a binary operation to combine the first two values. Then it takes the result of that first combination and combines it with the next element in the collection, and then the next, and so on through the end of the collection.

Here’s an illustration of how to use reduce to implement a product operation:

Using Reduce to Calculate the Product of All Numbers in a List
Using Reduce to Calculate the Product of All Numbers in a List

The code looks like this:

let product =
  [2;5;3;6]
  |> Seq.reduce (fun x y -> x * y)
// val product : int = 180

Another special case of reduce is String.concat—also known as a join operation—which allows you to concatenate a sequence of strings together with a separator in between each. Here’s how it works:

Using Reduce to Join a List of Strings Together with a Separator
Using Reduce to Join a List of Strings Together with a Separator

See how similar it is to the product operation above? If you should want to implement String.concat yourself, you could use reduce like this:

let joined =
  ["do";"mi";"sol";"do"]
  |> Seq.reduce (fun x y -> x + "-" + y)
// val joined : string = "do-mi-sol-do"

Here is the documentation on reduce in each of the sequential collection modules:

Now a few of caveats about reduce:

  • You cannot use reduce on an empty collection. You will get an exception if you do, so make sure you check to make sure your collection is not empty before you pass it to reduce.

  • The result of a reduce operation is always the same type as the elements in the collection. In other words, you can only reduce a collection of type A to a value of type A. You cannot reduce a collection of type A to a value of type B.

  • Finally, order matters if the order of your binary operation matters. In other words, with addition and multiplication, order does not matter. That is, a + b is the same as b + a. (Mathematicians say that such a function is commutative.) But with something like subtraction, order does matter. In other words, a − b does not necessarily produce the same result as b − a. So make sure that your binary operation applies the reduction to its operands in the correct order.

Having noted these caveats, next week, we will cover the fold operation. It operates almost the same way as reduce in that it walks a collection, applying a binary operation to each element. The fold operation cannot help us with that last point—order still matters—but it can handle an empty collection and, if necessary, produce a result that is of a type different from the type of the source collection’s elements.

Scala Saturday – The Set.intersect Method

Last week we looked at Set.union. This week we look at Set.intersect. When dealing with sets (which, remember, by definition, cannot contain duplicate elements), sometimes you have two sets, and you want to know what elements they have in common. That is called the intersection of two sets.

Maybe you have some crazy password policy:

  • Passwords must be at least 12 characters;
  • Each character must be unique; and
  • New passwords may have no more than four characters in common.

You can use a set intersection to determine whether an old password and a new password have too many characters in common:

val oldPwd = "aU*E3)vn'2-="

val newPwd1 = "Uv0&*n2'EI~5"
val common1 = oldPwd.toSet intersect newPwd1.toSet
// common1: scala.collection.immutable.Set[Char] =
//   Set(E, *, n, U, v, ', 2)
// Too many characters in common!

val newPwd2 = "Uv0&6;2'ZI~/"
val common2 = oldPwd.toSet intersect newPwd2.toSet
// common2: scala.collection.immutable.Set[Char] =
//   Set(U, v, ', 2)
// Just right!

F# Friday – The Set.intersect Function

Last week we looked at Set.union. This week we look at Set.intersect. When dealing with sets (which, remember, by definition, cannot contain duplicate elements), sometimes you have two sets, and you want to know what elements they have in common. That is called the intersection of two sets.

From Genesis to Revelation

The band Genesis, like many bands that have been around as long as they have, has undergone several lineup changes. When they recorded their first album, From Genesis to Revelation, Genesis consisted of Peter Gabriel, Tony Banks, Anthony Phillips, Mike Rutherford, and John Silver. You can put their names in a set:

let on1stAlbum =
  set ["Gabriel"; "Banks"; "Phillips";
       "Rutherford"; "Silver"]

Calling All Stations

Almost thirty years later, Genesis recorded their last studio album (to date), Calling All Stations. They had had several lineup changes through the years, and by this time, the members of Genesis were Ray Wilson, Tony Banks, and Mike Rutherford. Put their names into a set:

let onLastAlbum =
  set ["Wilson"; "Banks"; "Rutherford"]

Were there any members—keepers of the flame, as it were—who stayed with the band the entire time? Perform a set intersection to find out:

let keepersOfTheFlame =
  Set.intersect on1stAlbum onLastAlbum
// val keepersOfTheFlame : Set<string> =
//   set ["Banks"; "Rutherford"]

Scala Saturday – The Set.union Method

A defining property of mathematical set is that it contain no duplicates. Sometimes you need to combine two sets. But what if those sets contain some of the same elements, so that the combination would contain duplicates? No worries! That’s where Set.union comes in.

Journey from Mariabronn

The classic lineup of progressive rock band Kansas in the 1970s consisted of Steve Walsh, Kerry Livgren, Rich Williams, Robby Steinhardt, Dave Hope, and Phil Ehart. However, over the years, the lineup changed several times. Currently Kansas are Ronnie Platt, David Manion, Rich Williams, David Ragsdale, Billy Greer, and Phil Ehart.

You can represent these two lineups as sets:

val classicKansas = Set(
  "Walsh", "Livgren", "Williams",
  "Steinhardt", "Hope", "Ehart")
val currentKansas = Set(
  "Platt", "Manion", "Williams",
  "Ragsdale", "Greer", "Ehart")

Magnum Opus

What if the classic Kansas lineup got together with the current Kansas lineup for a reunion tour? How would the omnibus lineup look? Call the first set’s union method, and pass it the second set:

val totalKansas = classicKansas union currentKansas
// totalKansas: scala.collection.immutable.Set[String] =
//   Set(Ehart, Walsh, Steinhardt, Platt, Ragsdale,
//     Manion, Greer, Livgren, Hope, Williams)

Notice how the union of the two sets does not contain duplicates even though Ehart and Williams were in both lineups.

F# Friday – The Set.union Function

A defining property of mathematical set is that it contain no duplicates. Sometimes you need to combine two sets. But what if those sets contain some of the same elements, so that the combination would contain duplicates? No worries! That’s where Set.union comes in.

Shock to the System

The classic lineup of progressive rock band Yes in the 1970s consisted of Jon Anderson, Steve Howe, Chris Squire, Rick Wakeman, and Bill Bruford. However, over the years, the lineup changed so that the most stable incarnation of Yes in the 1980s was Jon Anderson, Chris Squire, Trevor Rabin, Tony Kaye, and Alan White.

You can represent these two lineups as sets:

let yes70s = 
  ["Anderson"; "Howe"; "Squire"; "Wakeman"; "Bruford"]
  |> Set.ofList
let yes80s =
  ["Anderson"; "Rabin"; "Squire"; "Kaye"; "White"]
  |> Set.ofList

Union

In 1990, the record company was ready for a new Yes album. Someone had the bright idea of recording an album called Union: It would unite the classic 70s Yes lineup with the 80s lineup all on one album.

How would the lineup look on the Union album? Just pass both sets to Set.union:

let yesUnion = Set.union yes70s yes80s
// val yesUnion : Set<string> =
//   set
//     ["Anderson"; "Bruford"; "Howe"; "Kaye";
//      "Rabin"; "Squire"; "Wakeman"; "White"]

Notice how the union of the two sets does not contain duplicates even though Anderson and Squire were in both lineups.

Scala Saturday – The flatMap Method

In a previous Scala Saturday post, we looked at the map method. As a quick review, map lets you take a collection of elements, calculate a new value from each source element, and create a new collection containing those new values. The mapping function has the following signature:

A => B

In other words, the function takes a single value of type A and returns a single value of type B.

But what if you have a mapping function with this signature?

A => List[B]

In other words, this function does not take one value and produce one value. Rather it takes one value and produces multiple values. What if you’re OK with that, but you just need to take those many values returned from each mapping and smash them all together into one list?

From Side to Side

Most of the guys in legendary progressive rock band Yes didn’t have just one job on their Close to the Edge album. They performed multiple duties. So let’s create a Musician case class to represent a musician and the list of instruments he plays on the album:

case class Musician(
  name: String,
  instruments: List[String])

Now you can create a list of musicians:

val yes = List(
  Musician("Jon Anderson", List("vocals")),
  Musician(
    "Steve Howe",
    List("electric guitars", "acoustic guitars",
      "vocals")
  ),
  Musician(
    "Chris Squire",
    List("bass guitar", "acoustic guitars",
      "vocals")
  ),
  Musician(
    "Rick Wakeman",
    List("Hammond organ", "Minimoog",
      "Mellotron", "grand piano",
      "RMI 368 Electra-Piano and Harpsichord",
      "pipe organ at St. Giles, Cripplegate church")
  ),
  Musician(
    "Bill Bruford",
    List("drums", "percussion")
  )
)

Maybe you want one long list of every instrument the fellows in Yes used on the album. You just have to map each musician to his list of instruments, and then concatenate those lists together:

Illustrates mapping a list of musicians (jon, steve, chris, rick, nill) to a list of lists of the instruments that each musician plays ((vocals), (electric guitars, acoustic guitars), (bass guitar, vocals), (Hammond organ, Minimoog, ...), (drums, percussion)) and then a flattening of those nested lists into one long list
Collecting Musicians’ Instruments into One Long List

You could do this with two functions you’ve read about already on Scala Saturdays: map and concat:

val instruments = yes.map(_.instruments).flatten
// instruments: List[String] =
//   List(vocals, electric guitars, acoustic guitars,
//     vocals, bass guitar, ...)

The Total Mass

What if there were a function that could do both of those things—perform the transformation and the concatenation all in one? Turns out that there is: flatMap!

val instruments = yes flatMap (_.instruments)
// instruments: List[String] =
//   List(vocals, electric guitars, acoustic guitars,
//     vocals, bass guitar, ...)

How ’bout that? The very same results all in one function!

So then, flatMap performs a map and a flatten all in one function call.

You’ve seen flatMap examples here only in terms of lists, but the Scala’s other collections define the flatMap method, too:

F# Friday – The collect Function

In a previous F# Friday post, we looked at the map function. As a quick review, map lets you take a collection of elements, calculate a new value from each source element, and create a new collection containing those new values. The mapping function has the following signature:

'T -> 'U

In other words, the function takes a single value of type 'T and returns a single value of type 'U.

But what if you have a mapping function with this signature?

'T -> 'U list

In other words, this function does not take one value and produce one value. Rather it takes one value and produces multiple values. What if you’re OK with that, but you just need to take those many values returned from each mapping and smash them all together into one list?

The Universe Divided

The guys in Canadian power trio Rush didn’t just stick to one instrument on their Hemispheres album. Each of them played a collection of instruments. So let’s create a Musician record type to represent a musician and the list of instruments he plays on the album:

type Musician = {
  Name : string
  Instruments : string list
}

Now you can create a list of musicians:

let rush = [
  {
    Name = "Geddy Lee";
    Instruments = 
    [
      "vocals"; "bass guitar"; 
      "Oberheim polyphonic"; 
      "Minimoog"; "Moog Taurus pedals"
    ]
  };
  {
    Name = "Alex Lifeson";
    Instruments = 
    [
      "electric and acoustic guitars";
      "classical guitar"; "guitar synthesizer"; 
      "Moog Taurus pedals"
    ]
  };
  {
    Name = "Neil Peart";
    Instruments =
    [
      "drums"; "orchestra bells"; "bell tree";
      "timpani"; "gong"; "cowbells";
      "temple blocks"; "wind chimes"; "crotales"
    ]
  }
]

Maybe you want one long list of every instrument the fellows in Rush used on the album. You just have to map each musician to his list of instruments, and then concatenate those lists together:

Illustrates mapping a list of musicians (geddy, alex, neil) to a list of lists of the instruments that each musician plays ((vocals, bass guitar, ...), (electric guitars, acoustic guitars, ...), (drums, orchestra bells, ...)) and then a flattening of those nested lists into one long list
Collecting Musicians’ Instruments into One Long List

You could do this with two functions you’ve read about already on F# Fridays: map and concat:

let instruments =
  rush
  |> List.map (fun m -> m.Instruments)
  |> List.concat
// val instruments : string list =
//   ["vocals"; "bass guitar"; "Oberheim polyphonic";
//    "Minimoog"; "Moog Taurus pedals"; ...]

Heart and Mind United

What if there were a function that could do both of those things—perform the transformation and the concatenation all in one? Turns out that there is: collect!

let instruments =
  rush |> List.collect (fun m -> m.Instruments)
// val instruments : string list =
//   ["vocals"; "bass guitar"; "Oberheim polyphonic";
//    "Minimoog"; "Moog Taurus pedals"; ...]

How ’bout that? The very same results all in one function!

So then, collect performs a map and a concatenation, or a flatten, all in one function call. In fact, some languages name this operation flatMap or flat_map.

You’ve seen collect examples here only in terms of lists, but the F#’s Array and Seq modules define the collect operation, too:

Scala Saturday – The filter Method

Another frequently used operation in functional programming is filter. The filter method allows you to pare down a collection by specifying a criterion. Any element in the collection that does not meet that criterion is dropped, and you get a new collection consisting only of the elements that meet the criterion.

Sequential Collections

Suppose you have a list of numbers, and you want to filter out the even numbers, leaving only the odds. Define a predicate—a function that takes an input and returns true or false—that determines whether an integer is odd, returning true for odd numbers and false for even. Pass that predicate to your list’s filter method, and List.filter returns a new list containing only the odd numbers:

Illustrates filtering evens out of a list of integers (4, 5, 6, 7) with a predicate that returns true for odd numbers and false for even numbers. This yields the list (5, 7).
Filtering Out the Even Numbers from a List of Numbers

Here is the code:

val f = (n: Int) => n % 2 == 1
// odds: List[Int] = List(5, 7)

Notice that filter preserves the order of the original collection because a list is a sequential collection. The same goes for arrays and sequences.

Sets

While filter works essentially the same for sets as it does for the sequential collections, it does not guarantee to preserve the order. Such is the nature of sets: they are not sequential collections.

If you have a set of words, and you want to retain only the words that do not start with “w,” you take the same approach as with a list. Define a predicate that determines whether a string starts with a letter other than "w". Then pass your predicate to your set’s filter method:

Illustrates filtering a set of words { "weary", "world", "young", "struggle" } to retain only the words that do not begin with "w": { "young", "struggle" }
Retaining Only Words that Don’t Start with “w”

The code ought to look pretty familiar:

val f = (s: String) => !s.startsWith("w")
val nonWWords = Set(
  "weary","world","young","struggle"
) filter f
// nonWWords: scala.collection.immutable.Set[String] =
//   Set(young, struggle)

Again, while the order of the elements happens to have been preserved in this simple example with a small set, Set.filter is not required to do so.

Maps

There is also Map.filter. Instead of taking a single-input predicate, Map.filter takes a two-input predicate: the first input is the map’s key type, and the second is the value type. That means you can filter a map on the key, the value, or both.

Maybe you have a map of Spock’s Beard albums to the members of the band who played on that album. (Spock’s Beard has had some changes in personnel over the years.) You want to know on which albums Ted Leonard was on vocals:

val albums = Map(
  "The Light" -> Set("N. Morse","A. Morse","Meros","D'Virgillio"),
  "Beware of Darkness" -> Set("N. Morse","A. Morse","Okumoto","Meros","D'Virgillio"),
  "The Kindness of Strangers" -> Set("N. Morse","A. Morse","Okumoto","Meros","D'Virgillio"),
  "Day for Night" -> Set("N. Morse","A. Morse","Okumoto","Meros","D'Virgillio"),
  "V" -> Set("N. Morse","A. Morse","Okumoto","Meros","D'Virgillio"),
  "Snow" -> Set("N. Morse","A. Morse","Okumoto","Meros","D'Virgillio"),
  "Feel Euphoria" -> Set("A. Morse","Okumoto","Meros","D'Virgillio"),
  "Octane" -> Set("A. Morse","Okumoto","Meros","D'Virgillio"),
  "Spock's Beard" -> Set("A. Morse","Okumoto","Meros","D'Virgillio"),
  "X" -> Set("A. Morse","Okumoto","Meros","D'Virgillio"),
  "Brief Nocturnes and Dreamless Sleep" -> Set("Leonard","A. Morse","Okumoto","Meros","Keegan")
)
val withLeonard = albums filter { case (_,v) =>
  v contains "Leonard"
}
// withLeonard: scala.collection.immutable.Map[String,scala.collection.immutable.Set[String]] =
//   Map(
//     Brief Nocturnes and Dreamless Sleep ->
//     Set(A. Morse, Leonard, Okumoto, Keegan, Meros))

That’s a big chunk there, but the long and the short is that our filter function is ignoring the key (hence the underscore) and examining only the value, searching the set in each entry for Leonard’s name.

The Map trait also defines a filterKeys method for filtering by key. filterKeys takes a single-input predicate like Set.filter.

Filter … NOT!

In addition to filter, Scala collections also define the filterNot method. It simply takes the filtering function and inverts it so that you get results opposite those of filter.

It’s a matter of style, I suppose, as to whether you prefer to use filterNot or to use filter with a filtering function that you invert yourself. There is an argument to be made that filterNot is more readable: it is sometimes easy to overlook that little ! in a larger expression. Still, it seems like an unnecessary expansion of the API. Furthermore, if you’re going to have both filter and filterNot, why do the collections not provide, e.g., findNot, dropWhileNot, and takeWhileNot—the inverted counterparts of find, dropWhile, and takeWhile?