Sum Lists function in Scala

Question

Sum Lists: You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1 's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE

Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is,617 + 295

Output: 2 -> 1 -> 9. That is, 912

Is there any way to improve the code?

def sumList(list1:List[Int], list2:List[Int], curry: Int):List[Int]= (list1.size,list2.size) match {
 case (0,0)=>List.empty
 case (0, b) =>sumList(List.empty, list2.tail, if(list2.head+curry>10)(list2.head+curry)/10 else 0):::List((list2.head+curry)%10)
 case (a,0) =>sumList(list1.tail,List.empty , if(list1.head+curry>10)(list1.head+curry)/10 else 0):::List((list1.head+curry)%10)
 case (a,b) =>sumList(list1.tail,list2.tail, if(list1.head+list2.head+curry>10)(list1.head+list2.head+curry)/10 else 0):::List((list1.head+list2.head+curry)%10)
 }

Answer 1

• Naming
  • Use something shorter and more generic, like a and b, instead of list1 and list2
  • curry is mispelled -- should be carry
• You are repeating yourself a lot. For example, except in the case where both lists are empty:
  • In each case, you have three adds that are exactly the same.
  • All three cases have a very similar structure -- the only difference is basically which numbers are being added
• Consider defining a class to represent numbers. That way, you can easily change the representation in the future.
• I don't think your implementation is tail-recursive. This will lead to stack-overflows for large lists. This might or might not be a problem, depending on your application.

• Use "word-at-a-time" thinking only as a last resort. In this case, you are directly recursing over the lists -- one element ("word") at a time. Try to find a higher-level abstraction, such as map, that you can use.

  In this particular case, in order to handle the carries, you really need some sort of "map plus accumulator" abstraction. To my knowledge, there is no such function built-in to Scala. So you might have to write your own. Still, I would suggest implementing a generic, higher-order function to do this. That way, you can reuse that function later for other things.

• Try to decompose your problem. In this case, the problem is already fairly simple. Still, you might (or might not -- I'm not sure) benefit from drawing inspiration from hardware adders.

• sweetyBaby: Hi I am not sure the problem is, can you help to give a solution so that I can compare with mine and to see where is problem, thanks
• sweetyBaby: May I know why you think mine is not tail-recursive ?
• Nathan Davis: @sweetyBaby, it's not tail-recursive because the last thing the function does (in the recursive cases) is invoke the ::: operator. Thus, the recursive call to sumList is not in tail position. As I mentioned, I think you should use a higher-level abstraction rather than using recursion directly in this particular situation. But if you'd like to learn more about tail-recursion see oldfashionedsoftware.com/2008/09/27/…

Answer 2

• I would do it in multiple steps: convert to int(or Biginteger) -> calculate -> convert to linked list

• you can use the commutivity of addition for

  case (a,0) => sumList(list2,list1, 0)

• 200_success: I suppose that converting to an Int or BigInteger would defeat the intended purpose of this exercise.

Answer 3

Your solution is wrong: for your given example, it produces the list 9 → 1 → 2, which is backwards. Furthermore, it takes a curry (which should be "carry"?) parameter that is not in my interpretation of the spec.

Your solution tries to handle too many cases all at once. As @NathanDavis says, a more functional approach would be useful. To start, I would recommend naïvely adding the digits without carrying. Then, write a carry function that traverses the list and carries the excess values towards the end of the list.

def sumList(aList: List[Int], bList: List[Int]): List[Int] = {
 def carry(list: List[Int]): List[Int] = list match {
 ...
 }
 carry(aList.zipAll(bList, 0, 0).map((pair) => pair._1 + pair._2))
}