Programmation appliquée en Scala

Copyright © Cay S. Horstmann 2015 Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License

Writing a Higher-Order Function

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

Returning 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

Scary looking lab

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].
  2. val partition = (values: Seq[Int], p: Int => Boolean) => ...
    
  3. What result do you get for partition(1.to(10), _ % 3 == 1)?
  4. 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.
  5. Recall that
    words.sortWith(compareBy(vowels))
    yields
    had, a, lamb, little, Marianne
    What you expect to get when calling
    words.sortWith(rev(compareBy(vowels)))
  6. 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:

    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