Add two numbers

code ↗ problem ↗

Given two numbers represented as linked lists (in reverse digit order), find the sum of the two numbers (also as a linked list in reverse digit order).

General set-up

Linked list type

The input and output are both supposed to be in the form of a linked list.

Now technically the base Gleam implementation for lists is a singly-linked list, so a purely list-based solution would be an answer to the problem. However, that's obviously not in the spirit of the problem, especially since the problem sample code shows us that they want the answer in a custom data type.

To build a linked list, we'll need two variants: A Node type to reresent a node with data in it, and an End type that marks the end of the list.

pub type LinkedList {
  Node(value: Int, next: LinkedList)
  End
}

Naive solution

I'll refer to this as the "naive" solution, since it won't take advantage of one of the biggest optimization wins we can get in Gleam. This is how you might write it if you just wanted to solve the problem quickly.

Five steps to solve the naive approach

The simplest possible input

The simplest possible input would be to try and add two empty linked lists (in this case, an empty linked list is just the End value with no nodes).

What should happen if we have two terminal lists? We should return End to stop further iterations and indicate that we've finished.

case addend, augend {
  End, End -> End
  _, _ -> todo
}

Create small examples

The simplest non-trivial input would be adding two one-digit numbers. The first case is just adding 1 and 1. We'll call one number the addend and the other the augend, so that they have more meaningful names.

let addend = Node(1, End)
let augend = Node(1, End)

Working it out:

1. Take the value from addend. Take the value from augend. Add the values together to get 2.
2. Insert 2 as a node, then move on to the rest of addend and the rest of augend.
3. Both lists are now End, and so we add End and stop.

The result is thus Node(2, End), exactly as expected.

Another small example is adding 4 and 8. In this case, we are confronted with the fact that we may have to deal with carry digits. These might introduce a final action even if the two linked lists are exhausted!

let addend = Node(4, End)
let augend = Node(8, End)

1. Take the value from addend. Take the value from augend. Add the values together to get 12.
2. We only want the terminal digit, so insert 12 % 10 or 2 as the node value. Our answer so far is Node(2, <something>).
3. We have a 1 we need to carry, so pass the rest of the addend, the rest of the augend, and the carry digit.
4. We still have the carry digit to account for, so we need to add it as a digit in the list. Our answer is now Node(2, Node(1, <something>)) and there is no more carry digit.
5. We evaluate again. The addend is End, the augend is End, and the carry is 0. We're done, so we assign End and the final answer is Node(2, Node(1, End)) as expected.

So, we have covered the simple cases: Two terminal lists, non-terminal lists without carry, and a simple carry.

The carry can also never be more than 1. Since we're adding at most 9 and 9 in digitswise addition, the carry is never going to be more than 1. Most importantly, the carry will never produce another carry, so we can always just insert it as the last node if needed.

So, now we can cover these cases as well:

case addend, augend, carry {
  End, End, 0 -> End
  End, End, n -> Node(n, End)
  Node(a_head, a_next), Node(b_head, b_next), _ -> {
    // Add the heads while respecting the carry
    // Advance to the next elements in the list
    todo
  }
}

Relate hard cases to easier cases

We can proceed based on the head of each list, and then use the rest of each list as the input for the next call.

So, each recursive solution has the pattern:

1. Iterate through the heads until you reach the end of both lists.
2. Resolve and return the nodes.

Generalize the pattern

Broadly:

/// pseudo
case addend, augend, carry {
  // Base cases
  End, End, 0 -> End
  End, End, n -> Node(n, End)
  // Recursive rule
  Node, Node, _ -> {
    // Calculate the current value from the heads of each list
    // Calculate the new carry
    Node(calculated_value, next: solve(next, next, new_carry))
  }
}

Write the code to combine the cases

The clearest thing we're missing is how to handle situation where one list is exhausted but the other still has elements; there is no guarantee that the lists will be of the same length. In this case, we can just treat the exhausted list as, essentially, an endless array of implicit leading 0's, and ignore its contributions to the calculations.

/// pseudo
case addend, augend, carry {
  // Base cases
  End, End, 0 -> End
  End, End, n ->Node(n, End)
  // Recursive rules
  Node(...), Node(...), _ ->
    Node(new_val(value, value), solve(next, next, new_carry))
  Node(...), End, _ | End, Node(...), _ ->
    Node(new_val(value), solve(next_or_end, next_or_end, new_carry))
}

Implementation for the naive solution

The two values we need to calculate for each step:

• The value to go in the node is { a_head + b_head + carry } % 10, since we want whatever the 1's place digit is.
• The new carry is 0 if the sum is less than 10 or 1 if the sum is greater than 10; that is, the new carry is simply the leading integer of the sum divided by 10. Thankfully, that's exactly how Gleam's integer division / works.

The complete naive solution:

fn solve(addend: LinkedList, augend: LinkedList, carry: Int) -> LinkedList {
  case addend, augend, carry {
    // Base cases
    End, End, 0 -> End
    End, End, n -> Node(n, End)
    // Recursive rules
    Node(value: head, next: tail), End, _ ->
      Node({ head + carry } % 10, solve(tail, End, { head + carry } / 10))
    End, Node(value: head, next: tail), _ ->
      Node({ head + carry } % 10, solve(End, tail, { head + carry } / 10))
    Node(value: a_head, next: a_tail), Node(value: b_head, next: b_tail), _ ->
      Node(
        { a_head + b_head + carry } % 10,
        solve(a_tail, b_tail, { a_head + b_head + carry } / 10),
      )
  }
}

Optimizing the solution

The above solution is enough, but it is not a tail-call optimized approach. For our final answer, let's walk through the process of rewriting the function into the tail-call optimized version.

Rewrite the function to be tail-call optimized

Identify the accumulator and the default state

The accumulator must be the same type as our answer, so it must be a LinkedList.

The default or terminal value for LinkedList is End, so we'll use that as our initial state for the accumulator.

That also tells us that we're going to essentially do this "in reverse" compared to the naive solution. Our naive solution builds the list "outside-in", starting with the outermost node and then working "in" toward the final step. In our tail-call optimized version, we'll start with the End node and wrap each step with the next step.

That also means that, at the end of the problem, we'll need to reverse the list to get our final answer.

Update the function signature and call site to include the accumulator

This part is always easy:

fn solve(
  addend: LinkedList,
  augend: LinkedList,
  carry: Int,
  accumulator: LinkedList,
) -> LinkedList {
  case addend, augend, carry {
    (... etc. ...)
  }
}

Rewrite the base cases to return the accumulator

Instead of returning a terminal value, our base cases should instead return the accumulator itself.

 fn solve(
   addend: LinkedList,
   augend: LinkedList,
   carry: Int,
   accumulator: LinkedList,
 ) -> LinkedList {
   case addend, augend, carry {
-    End, End, 0 -> End
+    End, End, 0 -> accumulator
-    End, End, n -> Node(n, End)
+    End, End, n -> Node(n, accumulator)
   }
 }

Rewrite the recursive cases to update the accumulator in a function call

Lastly, we want to update the accumulator with each call; instead of returning a node directly, we want to return the next step.

 fn solve(
   addend: LinkedList,
   augend: LinkedList,
   carry: Int,
   accumulator: LinkedList,
 ) -> LinkedList {
   case addend, augend, carry {
     // Base cases
     End, End, 0 -> accumulator
     End, End, n -> Node(n, accumulator)
     // Recursive steps
     Node(value: head, next: tail), End, _ ->
-      Node({ head + carry } % 10, solve(tail, End, { head + carry } / 10))
+      solve(
+        tail,
+        End,
+        { head + carry } / 10,
+        Node({ head + carry } % 10, accumulator),
+      )
     End, Node(value: head, next: tail), _ ->
-      Node({ head + carry } % 10, solve(End, tail, { head + carry } / 10))
+      solve(
+        End,
+        tail,
+        { head + carry } / 10,
+        Node({ head + carry } % 10, accumulator),
+      )
     Node(value: a_head, next: a_tail), Node(value: b_head, next: b_tail), _ ->
-      Node(
-        { a_head + b_head + carry } % 10,
-        solve(a_tail, b_tail, { a_head + b_head + carry } / 10),
-      )
+      solve(
+        a_tail,
+        b_tail,
+        { a_head + b_head + carry } / 10,
+        Node({ a_head + b_head + carry } % 10, accumulator),
+      )
   }
 }

Implementation of the tail-call optimized version

As mentioned before, this new version is an "inside-out" accumulator instead of the "outside-in" result from the naive case. So, our final solution has to include a step to reverse the list and get us our final result.

pub type LinkedList {
  Node(value: Int, next: LinkedList)
  End
}

pub fn solution(l1, l2) {
  solve(l1, l2, 0, End)
  |> reverse(terminus: End)
}

fn solve(
  addend: LinkedList,
  augend: LinkedList,
  carry: Int,
  accumulator: LinkedList,
) -> LinkedList {
  case addend, augend, carry {
    End, End, 0 -> accumulator
    End, End, n -> Node(n, accumulator)
    Node(value: head, next: tail), End, _ ->
      solve(
        tail,
        End,
        { head + carry } / 10,
        Node({ head + carry } % 10, accumulator),
      )
    End, Node(value: head, next: tail), _ ->
      solve(
        End,
        tail,
        { head + carry } / 10,
        Node({ head + carry } % 10, accumulator),
      )
    Node(value: a_head, next: a_tail), Node(value: b_head, next: b_tail), _ ->
      solve(
        a_tail,
        b_tail,
        { a_head + b_head + carry } / 10,
        Node({ a_head + b_head + carry } % 10, accumulator),
      )
  }
}

fn reverse(
  linked_list: LinkedList,
  terminus accumulator: LinkedList,
) -> LinkedList {
  case linked_list {
    End -> accumulator
    Node(value: value, next: next) -> reverse(next, Node(value, accumulator))
  }
}