Leetcode in Gleam

repo ↗

This project is a collection of solutions to Leetcode problems.

Wait! Give me a chance to explain!

Unlike many Leetcode problem sets, this one isn't just focused on solving (and explaining) the problems. Instead, the goal of this project is to solve Leetcode problems using recursive, immutable, and functional paradigms.

All of these solutions are solved with recursion and simple data structures, are type-safe, and do not rely on mutation. Most are solved entirely without relying on hashmaps!

Problems index

  1. Two sum

  2. Add two numbers

Recursive problem-solving

My background is in mathematics before I moved over to programming, so I have always had a soft spot for recursion and type-safety. These concepts map very cleanly onto how I was taught to understand logic and problem-solving, so I wanted to model out how these problems be solved in a way that aligns with my brain.

How to solve any recursive problem

As outlined in this video ↗, you can approach almost any recursive problem with five steps:

  1. Define the simplest possible inputs. These will become the base cases.
  2. Create small examples. This step builds your intuition for how the problem steps relate to each other.
  3. Relate hard cases to simpler cases. This is the seed of the recursive step, but still in concrete terms.
  4. Generalize the pattern. Take the recursive seed and create the full recursive rule, defining the n+1 case from the n case.
  5. Write the code to combine the recursive rule with the base case(s). The last step is to put it all together.

All of the problems solved in this repo include a write-up mapping my actual, real examples and reasoning with these steps and culminating in the solution.

Tail-call optimization

When executing a recursive function, the computer must allocate some call frames to make space for the function's calculations and results. Each simultaneous resolving function call adds more stack frames, which can quickly eat up the system's available resources.

To avoid this, Gleam and many other functional programming languages make use of tail-call optimization. Briefly: If the last action of a function's branches is either to return a value or call the recursion, then a tail-call optimized runtime can reuse a single current stack frame for all the calculations, which means the system can operate both much quicker and much more efficiently.

Tail-call optimization of a single variable

The factorial function is probably the most canonical example for tail-call optimization, so let's just step through it. The factorial n! is defined as the product of all non-zero positive integers up to n:

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

This function is completely sufficient, but if we step through the resolution, we can see that resolving the nth factorial will require allocating n stack frames:

factorial(5)
↑ 5 * factorial(4)
↑↑ 5 * 4 * factorial(3)
↑↑↑ 5 * 4 * 3 * factorial(2)
↑↑↑↑ 5 * 4 * 3 * 2 * factorial(1)
↑↑↑↑↑ 5 * 4 * 3 * 2 * 1

These deep frames are a result of how we define the function. Since our last action is not a function call but rather the product of a value and a function call, we can't return the value of any of the functions until we've completed the call stack.

By contrast, consider a tail-call optimized version:

def factorial_tail_call(n, accumulator=1):
    if n == 1:
        return accumulator
    return factorial_tail_call(n - 1, n * accumulator)

In this case, because our last action is a recursive function call, we can use only a single stack frame to store our result:

factorial_tail_call(5, 1)
factorial_tail_call(4, 5)
factorial_tail_call(3, 20)
factorial_tail_call(2, 60)
factorial_tail_call(1, 120)
120

Tail-call optimization of multiple variables

Tail-call optimization of multiple variables is more complicated; see this article for more info.

How to tail-call optimize any function

This is my own rules for tail-call optimizing a single-variable recursion, in the vein of the instructions on how to solve any recursive problem.

  1. Identify the accumulator and the default state. Tail-call recursion uses an accumulator value to "carry over" values from one step to the next, instead of handling the values directly. The accumulator must be of the same type as the answer we desire, and starts with whatever the base case or base assumption of the problem is. Often, this is the natural default for that type (for example, 0 for an Int, or "" for a String, etc.) Some problems may have an "initial condition," in which case the accumulator will probably account for that as well.
  2. Update the function signature and call site to include the accumulator. Often, you will want to "conceal" the tail-call optimization details inside a so-called "loop" function, in order to make the outer call as simple as possible. A concrete example: You want to call factorial(n), but you need factorial_loop(n, 0) to account for the tail-call optimization. In this case, you will add the accumulator to the loop function, and leave the original as a sugary wrapper for the public.
  3. Rewrite the base cases to return the accumulator. Instead of the base case returning a 'final' value, you must update the base case to return the accumulator, along with (potentially) any final transformation you might need.
  4. Rewrite the recursive cases to update the accumulator in a function call. Here, you need to do two things: Call the function recursively to get the next iteration, and pass the updated value for the accumulator as the new accumulator value.

Worked example of tail-call optimizing a recursion

Here's a base implementation of the factorial function from earlier in Gleam; we'll go through the tail-call optimization step-by-step. For the sake of this example, just imagine that we have a type Natural which strictly represents natural numbers {0, 1, 2, 3, 4, ...}.

pub fn factorial(n: Natural) -> Natural {
  case n {
    // Base cases
    0 -> 1
    1 -> 1
    // Recursive step
    _ -> n * factorial(n - 1)
  }
}

Identify the accumulator and the default value

The accumulator must be a Natural integer, since this is just a math problem.

The natural default for an integer is usually either 0 or 1; in terms of operations, these are the additive identity and the multiplicative identity, which already tells you about where we're heading with this.

Since the factorial is a multiplication definition, 1 is the reasonable default.

Update the function signature and call site to include the accumulator

We want to conceal the implementation details of the tail-call recursion, so we will make the new version a private function, and call it from our public wrapper.

 pub fn factorial(n: Natural) -> Natural {
-  case n {
-    // Base cases
-    0 -> 1
-    1 -> 1
-    // Recursive step
-    _ -> n * factorial(n - 1)
-  }
+  factorial_loop(n, 1)
 }

+fn factorial_loop(n: Natural, _accumulator: Natural) -> Natural {
+  case n {
+    todo
+  }
+}

Rewrite the base cases to return the accumulator

 pub fn factorial(n: Natural) -> Natural {
   case n {
     // Base cases
     0 -> 1
     1 -> 1
     // Recursive step
     _ -> n * factorial(n - 1)
   }
   factorial_loop(n, 1)
 }

 fn factorial_loop(n: Natural, accumulator: Natural) -> Natural {
   case n {
-    todo
+    // Base cases
+    0 -> accumulator
+    1 -> accumulator
+    // Recursive step
+    _ -> todo
   }
 }

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

The goal here is to move the operation inside of a function call.

Pause and consider the factorial function; at each step, it multiplies the current value by the value of the current step. That is straightforward to implement in the recursive call; we just need to multiply the current value by the step!

 pub fn factorial(n: Natural) -> Natural {
   case n {
     // Base cases
     0 -> 1
     1 -> 1
     // Recursive step
     _ -> n * factorial(n - 1)
   }
   factorial_loop(n, 1)
 }

 fn factorial_loop(n: Natural, accumulator: Natural) -> Natural {
   case n {
     todo
     // Base cases
     0 -> accumulator
     1 -> accumulator
     // Recursive step
-    _ -> todo
+    _ -> factorial_loop(n - 1, n * accumulator)
   }
 }

Conclusion

All put together:

pub fn factorial(n: Natural) -> Natural {
  case n {
    // Base cases
    0 -> 1
    1 -> 1
    // Recursive step
    _ -> n * factorial(n - 1)
  }
  factorial_loop(n, 1)
}

fn factorial_loop(n: Natural, accumulator: Natural) -> Natural {
  case n {
    todo
    // Base cases
    0 -> accumulator
    1 -> accumulator
    // Recursive step
    _ -> todo
    _ -> factorial_loop(n - 1, n * accumulator)
  }
}