Last Updated: December 31, 2020
·
1.862K
· brianhsu

[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:

  1. factorial(n: Int): Int will be buildingList(n: Set[Int]): List[Int]
  2. The stopping condition of factorial is n == 1, but the stopping condition in buildingList should be n is an empty set.

Then we asked ourself the following question:

  1. When we hit stopping condition (n == 1) in factorial, we return the value 1. What should we return if we hit stopping condition in buildlingList?
  2. We use * operator to connect all integer values, what operator / function or construct shall we use to connect all integer values in buildingList?

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.