Incrementing a binary number

Before we jump into list implementation, let's look at the related binary operations.

Here is how we would increment a binary number represented by a list of 0 and 1:

scala> def increment(numList: List[Int]): List[Int] = numList match { 
     |   case Nil => List(1) 
     |   case 0 :: xs => 1 :: xs 
     |   case 1 :: xs => 0 :: increment(xs) 
     |   case _ => sys.error("Not a binary number")  
     | } 
 
scala> increment(List(1,0,1)) 
res3: List[Int] = List(0, 1, 1) 
 
scala> increment(List(0, 1)) 
res4: List[Int] = List(1, 1) 
 
scala> increment(List(0, 0, 1)) 
res5: List[Int] = List(1, 0, 1) 

Note

Note that we need to write the numbers such that the least significant bit is on the left-hand side.

When we wrote the binary number algorithms, we saw the reason for it. We wanted the LSB to appear at the head of the list. Operating at the head of the list is an...