Producing uniform lists in Scala

Question

When writing an answer to another question here, I came across the problem of producing lists of integers having a certain total and only consisting of a certain number and an optional rest. So for total 21 and number 5 you would get List(5, 5, 5, 5, 1).

Solving the problem is obviously not hard. However, I have the feeling that it can be written more concisely than this:

def uniformList(sum: Int, num: Int): List[Int] = {
 val rest = sum % num
 List.fill(sum / num)(num) ::: (if (rest == 0) Nil else List(rest))
}

Of course I could inline the rest but I don't think it makes it more readable. I'm not looking for a performant solution but a more concise one. My feeling is that there should be a solution that is as easy to grasp as the concrete example I gave in the first paragraph.

Answer 1

Here are few more ways to produce your uniform lists:

def f0(a: Int, b: Int) = {
 val c = a % b
 val d = a / b
 val n = if (c == 0) d else d + 1
 (1 to n).toList map (i => if (i * b <= a) b else c)
}
def f1(a: Int, b: Int) = {
 val c = a % b
 val d = a / b
 val xs = List.fill(d)(b)
 if (c == 0) xs
 else xs ::: c :: Nil
}
def f2(a: Int, b: Int) = {
 val r = a % b
 val n = a / b
 if (r == 0) List.fill(n)(b) 
 else List.tabulate(n + 1)(i => if ((i + 1) * b <= a) b else r)
}

• f0 is a different/interesting way to derive your lists but to my mind is harder to parse that f1

• f1 is very similar to what you have already but instead of redundantly concatenating Nil when rest == 0 we simply return the list as is

• f2 is quite ugly but utilizes tabulate so I thought I'd include it

You'll notice that in each of the four functions considered so far we calculate rest = sum % nums and then branch based on the result of this calculation. While I can think of other ways to derive a value for rest they aren't as intuitive as the % operator and in the end I think we would still have a conditional statement which decided the final element of the list.

Other than adopting the small change suggested by function f1 I think your code is as concise / understandable as it can be.

• 200_success: OK, so you've produced a few alternate solutions, but haven't said anything about the original code to make this a Code Review answer. Are you suggesting that you think the code should be left alone because you can think of no simpler formulation?
• lex82: Thanks for your alternative versions! I'd prefer f1 if I had to pick one of the three. However, I would definitely change the variable names to something more meaningful. I tried again and just posted an answer myself.

Answer 2

Three short lines of code for something that requires two full lines of natural language explanation is already quite short. Further shortening it would not serve purposes outside code-golf. Vertere's more verbose suggestions are actually better quality code, IMHO.

• lex82: I know what you mean. Short cryptic pieces of code that could be improved with explicit intermediate steps. But more often I see unnecessarily verbose code. Functional programming often helps to extract recurring patterns into functions (like map, filter, etc.) so simple problems don't have to be solved over and over again. I had the feeling I missed something like this when writing the function. I thought about the problem again and just posted an answer myself.

Answer 3

Since I posted the question, I have thought about the problem again. I tried to use recursion to solve it more elegantly:

def uniformList(total: Int, el: Int): List[Int] =
 if (total <= el) List(total)
 else el :: uniformList(total-el, el)

This is pretty close to what I had in mind. What I like about it is that there are no expression being used in several places, so we don't need any variables to capture and reuse them.

I also found another solution:

def uniformSum(total: Int, el: Int): List[Int] =
 List.fill(total/el)(el) ::: List(total % el).filter(_ > 0)

This is my favorite so far. The call to filter feels a little bit like a hack. However, in my opinion the main advantage is that you can actually see how the list is structured. without having to introduce new variables. Maybe the code would be clearer with extra variables such as mainPart and optionalRest. It looks clear now, but maybe not if I saw the function for the first time.