Copyright © Cay S. Horstmann 2015
This work is licensed under a Creative Commons Attribution 4.0 International License
Seq[Int]
fulfill a condition.val forall = (s: Seq[Int], p: Int => Boolean) => ...
p
is a function parameterforall(1.to(10), _ > 0)
should return true
forall(1.to(10), _ % 2 == 0)
should return false
... => s.map(p) ...is a sequence of
true
or false
....reduceLeft(_ && _)
val forall = (s: Seq[Int], p: Int => Boolean) => s.map(p).reduceLeft(_ && _)
val mystery = (s: Seq[Int], p: Int => Boolean) => s.map(p).filter(_ == false).length == 0
true
if all elements of s
fulfill the predicate p
true
if at least one element of s
fulfill the predicate p
true
if no elements of s
fulfill the predicate p
comp(s, t)
that returns true
if s
should come before t
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
val isVowel = (c: Char) => "aeiouAEUOU".contains(c) val vowels = (s: String) => s.filter(isVowel).length
words.sortWith((s, t) => vowels(s) < vowels(t))
val compareBy = (measure: String => Int) => ...
(s: String, t: String) => ...
measure(s) < measure(t)
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 functionmystery
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, _ < _))
mystery
yields a comparison function that uses comp2
to break ties if comp1
doesn't distinguish between s
and t
s
less than t
if both comp1
and comp2
dos
less than t
if either comp1
or comp2
dopartition
method of Seq
. You should implement an equivalent function that works for Seq[Int]
.val partition = (values: Seq[Int], p: Int => Boolean) => ...
partition(1.to(10), _ % 3 == 1)
?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
.words.sortWith(compareBy(vowels))yields
had, a, lamb, little, MarianneWhat you expect to get when calling
words.sortWith(rev(compareBy(vowels)))
words.sortWith(rev(compareBy(vowels)))
? In which order did the strings with one vowel appear? Why didn't their positions get reversed?We continue the “phone mnemonics” from Unit 3.
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.
cats(Vector("Hello", "World"), Vector("Mary", "had", "fun"))
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
.wordsForDigits("72252")
/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.
wordsForDigits("72252")
, what do you get? What do you get for wordsForDigits("72253")
?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"))?
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"))?
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.
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')
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')
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')
What is the result of
augment(augment(augment(Vector(Vector("1")), '2'), '3'), '4')
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.
Do this as individual work, not with your partner
When all done, email the signed zip files to Fatemeh.Borran@heig-vd.ch