Programmation appliquée en Scala

Writing a Higher-Order Function

• Let's write a function that checks whether all elements of a Seq[Int] fulfill a condition.

• val forall = (s: Seq[Int], p: Int => Boolean) => ...

• p is a function parameter
• forall(1.to(10), _ > 0) should return true
• forall(1.to(10), _ % 2 == 0) should return false
• We don't yet know how to do this efficiently, but we'll soldier on anyway:

  ... => s.map(p) ...

  is a sequence of true or false
• We want all of them to be true:

  ....reduceLeft(_ && _)

• All together:

  val forall = (s: Seq[Int], p: Int => Boolean) =>
    s.map(p).reduceLeft(_ && _)

What Does This Function Do?

val mystery = (s: Seq[Int], p: Int => Boolean) =>
  s.map(p).filter(_ == false).length == 0

1. It returns true if all elements of s fulfill the predicate p
2. It returns true if at least one element of s fulfill the predicate p
3. It returns true if no elements of s fulfill the predicate p
4. Something else (none of the above, syntax error, etc.)

Background: Comparison Functions

• To sort by a general criterion, specify how to compare elements
• In Scala, use a function comp(s, t) that returns true if s should come before t
• Different from C/Java (where a comparison function returns a value < 0, 0, > 0)

• val words = "Marianne had a little lamb".split(" ")
  words.sortWith(_ < _) // Marianne, a, had, lamb, little
  words.sortWith((s, t) => s.length < t.length) // a, had, lamb, little, Marianne
  

• What if we want to sort by the number of vowels?

  val isVowel = (c: Char) => "aeiouAEUOU".contains(c)
  val vowels = (s: String) => s.filter(isVowel).length

• No problem:

  words.sortWith((s, t) => vowels(s) < vowels(t))

• That looks so similar to sorting by length. Can one avoid the repetition?

Returning a Function

• Define a function that generates a comparator from a measurement (length, number of vowels, ...)

  val compareBy = (measure: String => Int) => ...

• Need to return a function (s: String, t: String) => ...
• ...that checks that measure(s) < measure(t)
• All together:

  val compareBy = (measure: String => Int) =>
    (s: String, t: String) => measure(s) < measure(t)
  

• words.sortWith(compareBy(vowels))
    // had, a, lamb, little, Marianne

• words.sortWith(compareBy(_.length))

• compareBy consumes a function and produces a function

What Does mystery Do?

val mystery = (
    comp1: (String, String) => Boolean,
    comp2: (String, String) => Boolean) =>
  (s: String, t: String) =>
    comp1(s, t) || !comp1(t, s) && comp2(s, t)

Sample usage:

words.sortWith(mystery((s, t) => s.length < t.length, _ < _))

1. mystery yields a comparison function that uses comp2 to break ties if comp1 doesn't distinguish between s and t
2. It yields a comparison function that considers s less than t if both comp1 and comp2 do
3. It yields a comparison function that considers s less than t if either comp1 or comp2 do
4. Something else (none of the above, syntax error, etc.)

Lab

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

Part 1: Defining Higher-Order Functions

1. Look up the Scaladoc for the partition method of Seq. You should implement an equivalent function that works for Seq[Int].

val partition = (values: Seq[Int], p: Int => Boolean) => ...

2. What result do you get for partition(1.to(10), _ % 3 == 1)?
3. Write a function rev that reverses a comparator , so that, for example,

   words.sortWith(rev(compareBy(vowels))) 

   yields the words with the most vowels first: Marianne, little, ....

   val rev = (comp: (String, String) => Boolean) => (s: String, t: String) => ...

   Hint: This is completely trivial, but it takes some practice to think about it. You can't write t < s for ... since that only works if comp happens to be _ < _. You need to express it in terms of comp.
4. Recall that

   words.sortWith(compareBy(vowels))

   yields

   had, a, lamb, little, Marianne

   What you expect to get when calling

   words.sortWith(rev(compareBy(vowels)))

5. What did you actually get for words.sortWith(rev(compareBy(vowels)))? In which order did the strings with one vowel appear? Why didn't their positions get reversed?

Part 2: Moving On with the Phone Mnemonics

We continue the “phone mnemonics” from Unit 3.

1. Have a closer look at the implementation of wordsFor. Inside it, you should have code that solves a more general problem where you have two vectors of strings and get a sequence of all concatenations from both of them. Write a function

   val cats = (s: Seq[String], t: Seq[String]) => ...

   that does this in general.
   Test case:

   cats(Vector("Hello", "World"), Vector("Mary", "had", "fun"))

2. Now write a function wordsForDigits that takes a string of digits between '2' and '9' and produces all strings that they can encode.

   val wordsForDigits = (digits: String) => ...

   Hint: First map to a vector of strings for each digit. Then use reduceLeft.
   Test case: wordsForDigits("72252")
3. Read in all words from /usr/share/dict/words, as we did before. For efficiency, let's put them into a set though. And remove those that start with an uppercase letter (which include a bunch of junk) as well as those of length 1. And let's make them all uppercase. And let's add in "SCALA" which is weirdly missing.

   val words = io.Source.fromFile("/usr/share/dict/words").getLines.filter(w => Character.isLowerCase(w(0)) && w.length > 1).map(_.toUpperCase).toSet + "SCALA"

   Then improve the wordsForDigits function from the preceding step by filtering against the set.
4. Now when you run wordsForDigits("72252"), what do you get? What do you get for wordsForDigits("72253")?

Part 3: Multiple Words

1. We've made a lot of progress, but we aren't quite there. The problem is a little harder. Given an arbitrary number like 7225247386, one is supposed to find the words "SCALA", "IS", "FUN" (and whatever other words there might be hidden).

   Let's assume we have a particular way of breaking up the numbers, say into Vector("72252", "47", "386"). Using wordsForDigits, we get all the words for "72252", "47", and "386". Now we want to concatenate them into a sentence.

   We've almost solved that problem before, when wordsForDigits reduced with cats to glue together words. Give it a try:

   val wordsForDigitsSequence = (seq: Vector[String]) =>
     seq.map(e => wordsForDigits(e)).reduceLeft(cats)

   What do you get for wordsForDigitsSequence(Vector("72252", "47", "386"))?

2. It would be easier to read the result if the words were separated by spaces. Make a copy of cats, call it catsSpaces, and make it separate the concatenated words by spaces. Then call catsSpaces instead of cats in wordsForDigitsSequence. What do you now get for wordsForDigitsSequence(Vector("72252", "47", "386"))?

3. We are doing good. If we know how to break up a number (such as 7225247386) into all corresponding sequences (such as 72252 47 386), then we can find the corresponding words for each sequence.

Part 4: Breaking Up Is Hard to Do

1. Let's find all ways that digits can be broken up into (non-empty) sequences. For example, the digits 1234 have 8 such decompositions: 1234, 12 34, 1 234, 1 2 34, 123 4, 12 3 4, 1 23 4, 1 2 3 4.

   That looks pretty random, but it's not so bad. Suppose you knew how to break up 123 (into 123, 12 3, 1 23, 1 2 3). Now you augment that with 4. There are two things you can do:

   • Add 4 all by itself: 123 4, 12 3 4, 1 23 4, 1 2 3 4
   • Add 4 to the last element: 1234, 12 34, 1 234, 1 2 34

   Let's do the first part.

   val augment1 = (a: Vector[Vector[String]], t: Char) => ...

   For each sequence s in a, you concatenate (with ++) the sequence Vector(t.toString).

   Test case:

   augment1(Vector(Vector("123"),
     Vector("12", "3"),
     Vector("1", "23"),
     Vector("1", "2", "3")),
     '4')

2. On to augment2. There are two inputs: a Vector[Vector[String]] such as Vector(Vector("123"), Vector("12", "3"), Vector("1", "23"), Vector("1", "2", "3")), and a character such as '4' to glue to the last element of each sequence.

   val augment2 = (a: Vector[Vector[String]], t: Char) => ...

   For each sequence s in a, you concatenate (with ++) all but the last element, followed by a Vector(s.last + t)

   Test case:

   augment2(Vector(Vector("123"),
     Vector("12", "3"),
     Vector("1", "23"),
     Vector("1", "2", "3")),
     '4')

3. Now define

   val augment = (a: Vector[Vector[String]], t: Char) => ...

   to concatenate augment1(a, t) and augment2(a, t) (with ++).

   Test case:

   augment(Vector(Vector("123"),
     Vector("12", "3"),
     Vector("1", "23"),
     Vector("1", "2", "3")),
       '4')

4. What is the result of

   augment(augment(augment(Vector(Vector("1")), '2'), '3'), '4')

5. This looks so promising. But why can't you use augment with reduceLeft?

Breaking up is hard to do. You'll have to wait until the next lecture to complete this puzzle.

Homework

Do this as individual work, not with your partner

When all done, email the signed zip files to Fatemeh.Borran@heig-vd.ch

• Problem 1
• Problem 2
• Problem 3
• Problem 4
• Problem 5