Programmation appliquée en Scala

Higher-Order Functions

• In Scala, functions are values:

  val triple = (x: Int) => 3 * x

• The type of triple is Int => Int
• You can pass triple to another function/method:

  1.to(10).map(triple)
    // yields 3 6 9 12 ... 30

• map is a higher-order function—it consumes a function
• Another useful higher-order function is filter. It consumes a function T => Boolean

  1.to(10).filter((x: Int) => x % 2 == 0)
    // yields 2 4 6 8 10

• Note that there was no need to store the function in a variable
• We will soon see other higher-order functions that produce functions

Parameter Type Inference

• When you define a function, you normally need to specify the parameter types:

  val triple = (x : Int) => 3 * x

• The return type is inferred. The type is Int => Int
• The parameter type can often be inferred as well:

  1.to(10).map((x) => 3 * x)
  

• Since 1.to(10) is a Seq[Int], the type of x is inferred to be Int
• Bonus: You can drop the ()

  1.to(10).map(x => 3 * x)

• Super bonus: Since x occurs exactly once, can drop x => and use _:

  1.to(10).map(3 * _)

reduceLeft

• s.reduceLeft(f) computes f(...f(f(s(0), s(1)), s(2))..., s(n-1))
• Note that f is a function with two arguments
• 1.to(100).reduceLeft(_ + _) is 1 + 2 + 3 + 4 + ... + 100 = 5050
• s.reduceLeft((a, b) => if (a > b) a else b) computes the maximum

What is the Value Of ...

1.to(100).map(_.toString).reduceLeft(_ + _)

1. The string "5050"
2. The string "1 2 3 ... 98 99 100"
3. A string of length 192
4. Something else (syntax error, other value, etc.)

flatMap

s.map(x => (x, 0))
    // Vector((1, 0), (2, 0), (3, 0), (4, 0))

s.map(y => s.map(x => (x, y)))
  // Vector(Vector((1,1), (2,1), (3,1), (4,1)),
  //        Vector((1,2), (2,2), (3,2), (4,2)),
  //        Vector((1,3), (2,3), (3,3), (4,3)),
  //        Vector((1,4), (2,4), (3,4), (4,4)))

s.flatMap(y => s.map(x => (x, y)))
  // Vector((1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), ..., (4, 4)) 

Capturing the Enclosing Environment

• Consider this function:

  val n = 3
  val fun = (x : Int) => n * x
  // What is fun(2)?

• n is not defined in the scope of fun, but that is ok. In the body of a function, you can use any variable from the enclosing scope.
• Doesn't seem a big deal—n is immutable, so it will always be 3. But consider this:

  def mulBy(n : Int) = (x : Int) => n * x

• Huh? Let's call it:

  val quadruple = mulBy(4) // the function (x : Int) => 4 * x

• And let's call that:

  quadruple(5) // yields 20

• Each call to mulBy yields a different function.
• Each function has a different value of n
• Closure = function + binding of its free variables (i.e the variables that are not defined locally in the function)

Where Did We Already Use Closures?

1. In the reduceLeft slide
2. In the flatMap slide
3. In both
4. In neither

Lab

1. You work with a buddy
2. One of you (the coder) writes the code, the other (the scribe) types up answers
3. When you get stuck, ask your buddy first!
4. Switch coder/scribe roles each lab
5. The coder submits the worksheet. Include the scribe's name in the worksheet!
6. The scribe submits answers. Include the coder's name in the report!

Part 1: Life without Loops

1. Make a worksheet Day3. Type in

   val zones = java.util.TimeZone.getAvailableIDs

   . What do you get?
2. We want to get rid of the continents. Try this:

   zones.map(s => s.split("/"))
   

3. Ok, halfway there. Add a map that takes an array and yields a(1). What did you do? What happens?
4. Hmmm, that's weird. There seem to be arrays of length < 2. How can you find them?
5. Ok, now get rid of them and try again. What did you do?
6. That's a lot of values. Can we get every tenth of them? (Hint: grouped(10))

Part 2: Reductions

1. Evaluate

   1.to(10).reduceLeft(_ * _)

   What do you get?
2. Write a function that computes n! in this way.
3. Surely you have written a factorial function before. How did you used to do it? Which approach do you like better?
4. Now we'd like to compute 2ⁿ with the same trick. How can you get a sequence of n copies of the number 2? Hint: map.
5. What is your function that computes 2ⁿ?
6. Given a Seq[String], how can you use reduceLeft to concatenate them with spaces in between? Write a function catSpace that does this. For example, catSpace(Vector("Mary", "had", "a", "lamb")) should give a string "Mary had a lamb"
7. What happens when you try 1.to(10).reduceLeft(_ < _)? Why?

Part 3: Fun with flatMap and reduceLeft

Martin Odersky, the inventor of Scala (as well as the charming husband of one of your instructors) likes to show off the power of Scala with a solution of the “phone mnemonics” problem. Given a phone number, what word or word sequence spells it on a touch-tone pad? For example, given the phone number 435 569 6753, one should come up with the sequence HELLO WORLD (and maybe others).

We can do better than what he did in his presentations. Over the next three labs, we'll solve this problem with our very restricted subset of Scala.

1. What interesting word can you make from the number 72252?
2. Declare a map that maps '2' to "ABC", '3' to "DEF", and so on. How do you do that? Pay attention that the keys should be characters and the values should be strings.
3. Actually, we want '2' to map to a Vector with three elements, "A", "B", "C". But we don't want to type all that by hand. Transform your map by adding

   .map(e => (e._1, e._2.map(c => c.toString)))
   

   Call the result letters—we'll need it in the next step.
4. Now it's trivial to find out the words that one can make with one digit. It's just letters(d). Let's move on to two digits. Write a function that given two digits produces the set of all words (whether or not they make sense) that you can make with both.

   val wordsFor = (a: Char, b: Char) => ...

   For example, wordsFor('5', '9') contains "JW", "JX", "JY", "KW", "KX", "KY", "LW", "LX", "LY". Hint: flatMap