[Scala] Building List From Current Max Value.
Original Problem
=================
I've take a course called Function Programming Principles in Scala in Coursera. In the assigment of week 3 (TweetSet), we are asked to I
mplement a method that could building a descending List using a function that return the current
max value in the set.
Since I do using recursive function to build List in Scala very often, so I come out some Scala code looks like the following:
var mySet = Set(3, 4, 1, 6, 5)
def buildingList(resetSet: Set[Int]): List[Int] = {
def building(resetSet: Set[Int], accumulator: List[Int]): List[Int] = {
if (resetSet.isEmpty) {
accumulator
} else {
var max = resetSet.max
building(resetSet - max, max :: accumulator)
}
}
building(resetSet, Nil)
}
assert(buildingList(mySet) == List(6, 5, 4, 3, 1)) // Ooops!
Of course, this is not quite what we want. Since the List in the assigment only support prepend operation to add element to List, if we use this pattern, we also get an ascending list.
Converted Problem
===================
It seems a little bit silly now, but I really have no idea how to write this function at first.
But sunddenly I found that this EXACTLLY the same problem as described below, if you could solve the following problem (which is quite often the first recursive function you will seen in any programming course), you should able to build a List has the same order as the order of input.
Define a recursive function (without inner function / helper function or accumulator), which returns the factorial of n.
def factorial(n: Int): Int = { .... }
In other words, `factorial(6)` should return `6 * 5 * 4 * 3 * 2 * 1`, where the most important thing is that `2 * 1` should be the first expression that really reduce to an integer value except of integer literal.
The solution of the problem should be in the first few lecture videos, if we really understand this problem, then we will find they are same problem. Just doing the following substitution:
-
factorial(n: Int): Int
will bebuildingList(n: Set[Int]): List[Int]
- The stopping condition of
factorial
isn == 1
, but the stopping condition in buildingList should ben
is an empty set.
Then we asked ourself the following question:
- When we hit stopping condition
(n == 1)
infactorial
, we return the value1
. What should we return if we hit stopping condition inbuildlingList
? - We use
*
operator to connect all integer values, what operator / function or construct shall we use to connect all integer values inbuildingList
?
Due to the honor code of this class, I can't paste the full Scala code. But I think this hint is quite clear that how we should solve this problem.