Step-by-step connection between a Scala high-order function to provided examples

Question

I'm having difficulty figuring out how to make the jump from a Scala high-order function definition to the example provided. It was provided in this slide show on slide 81.

Here's the high-order function definition:

trait X[A] { def map[B](f: A => B): X[B] }

Here's the examples provided:

(1 to 10) map { x => x * 2 } // evaluates to Vector(2, 4, ..., 20)
(1 to 10) map { _ * 2 }      // shorthand!

Huh?! There just HAS to be some steps in here I am missing. I get that the examples may be leveraging both the function definition AND some Scala niceties. I just don't have enough experience reading Scala and making the connecting assumptions yet.

My background is as a Java OO. I am now learning Scala and functional programming. And this is not the first example like this I have not understood. It's just the first one where I felt I had the courage to post knowing I would look ignorant.

I did try to research this. First, I went to the Scala "bible", "Programming in Scala 2nd Edition", and attempted to make sense of if from there (pages 165-9). Then, I did a search here on StackOverflow. And I found several links that talk around the area. But, nothing actually shows me, STEP-BY-STEP, the connection between a Scala high-order function definition and the provided examples in a way that maps to the particular instance in this slide.

Here's what I found on StackOverflow:

1. Scala: Workshop Advice
2. More on generic Scala functions
3. Scala: How to define "generic" function parameters?

I'm just now realizing that I skipped Google and came straight to StackOverflow. Hmmm. If you google and find just the right link, I would love seeing it. I've run out of time to sift through all the Google links which use terms like monkey-monad, blastomorphisms, etc. while leaving me even more confused and less likely to try and figure this out.

Answer 1

A higher-order function (or method) is a function/method which either takes a function as its parameter or yields a function as its result or both.

In this case it is a method called map defined on things like lists, arrays as well as many other kinds of containers. When called on a 1 to 10 which is a range of numbers from 1 to 10, represented by Range[Int] in Scala it traverses them one by one and applies the function (the one which has been passed in as a parameter) to every number inside of the range. The results of this function are accumulated in a new container - Vector[Int] in this case, which gets returned as the result of the map method.

So (1 to 10) map { x => x * 2 } which is btw syntactic sugar for (1 to 10).map(x => x * 2) applies x => x * 2 to numbers from 1 to 10. You can think of it as a call-back function. You could also have written it like this:

(1 to 10).map( new Function1[Int, Int] {
   override def apply(x: Int) = x * 2
})

Answer 2

I think the following is just an example signature provided for the purpose of displaying some of Scala's collection properties. In particular it does not show any implementation so you cannot really connect all the dots. Also it's not actually consistent with the examples... So, may be this is confusing.

trait X[A] { def map[B](f: A => B): X[B] }

I would read that as: given a collection class X over elements of type A:

• it has a map function that is parameterized on a type B
• the map function takes a function f converting a single A to a single B
• map returns a collection of the same type X over elements of type B.

Then it jumps to the example to illustrates using:

(1 to 10) map { x => x * 2 }

So, connecting the dots:

• The collection X is the type of (1 to 10), here a Range
• f: A => B is x => x * 2 which is inferred as a function taking an Int and returning and Int.
• Given the signature you would think that would return a Range over Int, but this actually returns an IndexedSeq.

A better example may have been:

List(1, 2, 3).map(i => i + "!") // a List[Int]
// returns a List[String]: List("1!", "2!", "3!") 

Answer 3

Let's define a data type with a map method, a singly linked list.

sealed abstract class MyList[+A] {
  def map[B](f: A => B): MyList[B]  // higher order function declaration.
  def head: A
  def tail: MyList[A]
}
case class Cons[A](head: A, tail: MyList[A]) extends MyList[A] {
  def map[B](f: A => B): MyList[B] = Cons[B](f(head), tail.map(f))
}
case object Nil extends MyList[Nothing] {
  def map[B](f: Nothing => B): MyList[B] = this
  def head = sys.error("head on empty list")
  def tail = sys.error("tail on empty list")
}

A list is either empty, or it is a single value (the head) paired with the rest of the list (the tail). We represent the two cases, as a class hierarchy, extending from a sealed parent class MyList.

Note the implementation of Cons#map, we used the parameter f twice, firstly to execute the function with the head, and secondly to pass along to the recursive call to tail.map.

The syntax f(head) is shorthand for f.apply(head), the value f is an instance of the class Function1 that defined the apply method.

So far, so good. Let.s construct a list.

val list: MyList[Int] = Cons(1, Cons(2, Nil))

Now, we want to convert the list of Ints to a new list of Strings, by transforming each element. In Java, you would explicitly anonymously subclass Function1, as follows.

// longhand:
val stringList1: MyList[String] = list.map[String](new Function1[Int, String] {
  def apply(a: Int): String = a.toString
})

That's legal in Scala, but the signal to noise ratio isn't great. Let's use the anonymous function syntax instead.

val stringList2: MyList[String] = list.map[String]((a: Int) => a.toString)

We can go further and omit explicit type annotations, where the compiler has enough information to infer them.

First, let's infer the type of the parameter a, based on the element type of list.

val stringList3: MyList[String] = list.map[String](a => a.toString)

Really simple functions like these can also be expressed with the placeholder syntax. Rather than declaring the parameters, just write the code and use _ for any unknown quantity. Doing this, and also allowing the type of stringList4 to be inferred:

val stringList4 = list.map(_.toString)

Answer 4

Let's just concentrate on the map method as defined as defined on your trait X

def map[B](f: A => B): X[B]

Ok, so this is a method with one parameter, f. The type of f (the bit after the colon) is A => B. This is a function type; it's shorthand for the trait Function1[A, B] but I prefer not to think of these traits at all and just as something which can produce a B for a given value of A.

So: a functionA => B is something which takes a single instance of type A and produces a single instance of type B. Here are some examples of declaring them

val f = (i: Int) => i.toString //Int => String
val g = (_ : String).length    //String => Int, using placeholder syntax

So now think about what X[A] is; it could be a collection type, such as a List. If you are in possession of a List[String] and the String => Int function g above, then you obviously can get hold of a List[Int] in by applying the function to each element in the list, constructing a new list with the results.

So now, you could say:

strings map g //strings is a List[String]

But Scala allows you to declare the function anonymously. What does that mean? Well, it means you can declare it at the point of usage inline, rather than having to declare it as a val or var. Often these are called "lambdas". The syntax you are puzzled by are two options for such functions.

strings map { (x: String) => x.length }
strings map { x => x.length }
strings map { _.length }
strings map ( _.length )

These are all basically the same thing. The first clearly declares the function being passed to map. Because scala has type inference, you can in this use-case omit the type of the function input. The placeholder syntax _ is used instead of the identifier x and is a nice bit of sugar in the event you only need to refer to the input once. And you can use parens instead of braces in many cases, except for multi-statement functions.

Answer 5

Your example refer to the Scala Collection Framework, which itself has some sophisticated usage of the type system to yield the most specific type when transforming a collection. Now, the mechanism that allows this is hard to grasp and is not really relevant to the example. Higher-order function is simply a function or method that takes as argument (or returns) other functions. The example is somewhat obscured by adding in type parameters and not mentioning the Scala Collection Frameworks usage of implicits.

Answer 6

Not sure exactly what you don't get, but to explain the examples:

trait X[A] { def map[B](f: A => B): X[B] }

A trait is like a Java interface, that can also have concrete methods.

X is the trait name and [A] is a type parameter - think Java generics <A>. (Often A, B etc are used for element types in collections and T elsewhere, but that's just a convention.)

The trait specifies a member called map, which is a method with another type parameter [B], and taking a function argument of type A => B, with a return type of X[B]. It's abstract here because there's no method body.

The bit you may be missing is that A => B is short for Function1[A, B]. Function1 is the type of function objects taking 1 argument. (A, B) => C is short for Function2[A, B, C] etc. You can make your own Function types in Java - it's a fun exercise. A function object is essentially just one that has an apply method, producing a result from some arguments.

(1 to 10) map { x => x * 2 }    

These include point-free notation, where a.method(b) is written as a method b. So to is a method on RichInt taking an Int and producing a Range. map is a method on Range taking a Function1 argument (remember, a function is just an object of type Function1).

=> is also used for writing the functions themselves (in addition to at the type level, as described above). So the following are the same, all objects of type Int => Int:

(x: Int) => x + 1
new Function1[Int, Int] { def apply(x: Int) = x + 1 }
  // note Function1 is a trait, not a class, 
  // so this the same as `new Object with Function[Int, Int]`
new (Int => Int) { def apply(x: Int) = x + 1 }

Scala uses type inference so that you don't need to add all the types yourself if there is a particular function type (or any other parameterized type) expected from context, e.g.

val f : Int => Int  =  x => x + 1
val f : Int => Int  =  _ + 1

Hopefully you can see what this underscore notation means. The underscore is useful since otherwise there will always be some repetition, as the RHS of a function definition has to use the parameters from the LHS. Another example could be a function mapping a String to its length:

val f: String => Int = _.length

Since types of vals are normally inferred, you can provide only the necessary type annotation with

val f = (_: String).length

It's probably a bit confusing because the syntactic sugar and type inference means there are several ways to write the same thing, but once you get it you'll find it's there to make your life easier and cut down on the noise. Have a good play with these in the REPL if you aren't already.

Answer 7

     Scala: (1 to 10) map { x => x * 2 }
     English: Take the values, 1 to 10, and multiply each one by 2.

Some things to note:

• (1 to 10), Scala recognizes this is a collection of integers, specifically Range[Int]. It can be converted into another collection type, eg. (1 to 10).toList

• map, is lower-case. Think verb, to map from thing to another.

• {x => x * 2}, is surrounded by curly-braces. This means it is a function with out a name, an anonymous function.

• Underbar (_) can can be substituted for x => x

---

     Scala: trait X[A] { def map[B](f: A => B): X[B] }
     English:
       We define a trait that we can add to a class of X, type A.
       It has a method that takes a value and maps it into another value for a new class of X.

Note:

• X[A] and X[B] are of the same collection type but can have elements of differing type, eg. `(1 to 10).toList map { _.toSTring } will map List[Int] to List[String].

• f: A => B, this means map takes a function as an argument and it has one parameter of type A and returns type B.

• map is defined in all of the Scala collection types. You would not normally define this yourself.