Zelenya

Posted on Apr 6, 2023

Understanding FP: Overcoming Intuition and Ease Hurdles (loops vs. recursion)

#functional #scala #rust #javascript

📹 Hate reading articles? Check out the complementary video, which covers the same content.

Some people state that the FP way of doing things is easier, while others say it’s more complicated and isn’t even worth it. Let’s explore this.

To not go too abstract, let’s anchor around iterating over data structures: loops, recursion, and other alternatives.

And at the end, I’ll walk through solving a little interview task to tie it all together.

Loop and recursion

I assume you know what a loop is. Loops are a fundamental concept in imperative programming.

Here is a typical for-loop in JavaScript (note that we’ll keep switching languages).

for (let i = 0; i < 5; i++) {
  console.log(i)
}

This code prints numbers from 0 up to 5.

Then there is recursion, which is less popular among programmers, but nevertheless fundamental: in math, computer science, and everywhere else.

function print(n) {
  if (n < 5) {
    console.log(n)
    print(n + 1)
  } 
}

print(0)

Both can be used to solve similar sorts of problems. So, which one is better? What if we look at an example?

Here is a simple problem: “Given an object that has an items field and an optional parent, write a function that searches for needle: first, among its items, and if it’s not there, searches the parent, and so on” In other words, this is the expected results:

search(40, {items:[1,40,3]}) // 40 (in items)
search(40, {items:[1,2,3], parent: {items:[1,40]}}) // 40 (in parent's items)
search(40, {items:[1,2,3], parent: {items:[1,2], parent: {items:[40]}}}) // 40
search(40, {items:[1,2,3], parent: {items:[1,2], parent: {items:[]}}}) // null

💡 If the search feels useless, imagine it is searching for a whole object by name or something.

We can write this using two for-loops:

function search(needle, scope) {
  for (let cur = scope; cur !== null; cur = cur.parent) {
    for (let i = 0; i < cur.items.length; i++) {
      const item = cur.items[i]
      if (item === needle) {
        return item
      }
    }
  return null
}

Outer loop: We start with a current scope and visit all the parents while they exist.
Inner loop: We go through the items (by index from 0 till the last one).
We break as soon as we find a desired object; otherwise, we return null 🤷

Alternatively, we can write this using a recursion (I’ve turned the outer loop into a recursion):

function search(needle, scope) {
  for (let i = 0; i < scope.items.length; i++) {
    const item = scope.items[i]
    if (item === needle) {
      return item
    }
  }

  if (scope.parent) {
    return search(needle, scope.parent)
  } else {
    return null
  }
}

We still go through all the items in the scope.

If we didn’t find the object and the parent exists, we rerun the function for the parent.
Otherwise, we return null 🤷

Both of these work, but there is no punch line yet.

Intuition and Ease

Even if you’re new to the functional programming scene, somebody has probably tried to convince you how superior it is – recursion and FP in general – how easy and powerful some FP concepts or techniques are compared to an alternative.

And if you already have some experience with FP, you might be guilty of this yourself. It happens to us constantly: a new concept “clicks,” and we want to climb the tallest tree to share it with everyone else because it made our lives so much better!

But to a newcomer or a bystander, it’s not as apparent. Why would this alien functional concept be any better? It’s common to hear: “I’ve been doing X for years, and it’s okay; why would I relearn for no reason?!”

And then we have a stalemate. I have a hunch that it’s mainly due to a bit of miscommunication or misperception and the hurdles of trying a new concept.

First, quick spoiler, loops and recursions aren’t actually rivals; as I’ll show later, there are different kinds of loops and various other ways to iterate.

Second, hurdles – such as intuition and ease – can make it challenging to try a new concept. It may not immediately make sense when we encounter a new way of doing things.

But we shouldn’t expect to grasp ideas intuitively. Some concepts may be easy to understand and require little effort, while others may be more complex and require more time.

Let’s go back to iterations. Let’s reexamine a basic for-loop and a basic recursion, but then look at what people really do in production these days.

To loop or not to loop?

Note that there are many different ways to iterate over data structures:

for-loops;
recursion;
iterators;
list-comprehensions;
combinators/operators/pipelines;
while-loops (why would you do this to yourself?);
etc.

We’ve already seen loops. This time let’s ask ourselves what decisions we must make when writing a for-loop.

let numbers = [-1, 2, 3, 4, 5]

let sum = 0
for (let i = 0; i < numbers.length; i++) {
  sum += numbers[i]
}

console.log(`The sum is ${sum}`)
// Prints: The sum is 13

Where do we start? In this case: i is 0, and sum is 0.
Where do we stop? In this case: we go until the end of numbers using its length.
How to iterate? Or what is the step? In this case: we bump i by 1.
What to do on each step? In this case: add the current number to the sum.
And, for now, let’s pretend we don’t have to worry about the state outside .

So, at least four decisions for a for-loop. Okay, what about recursion?

let numbers = [-1, 2, 3, 4, 5]

function sumList(numbers) {
  if (numbers.length === 0) {
    return 0
  } else {
    const [head, ...tail] = numbers
    return head + sumList(tail)
  }
}

console.log(`The sum is ${sumList(numbers)}`)
// Prints: The sum is 13

💡 Recursive function comprises 2 parts: the base and the recursive cases.

The base case is the condition to stop the recursion.
The recursive case is where the function calls itself.

What is the base case? In this case: if the list is empty, return 0.
What is the recursive case? In this case: add the current number to the sum of the rest of the numbers.
Additionally: What is the initial input to the recursive function? In this case, we pass numbers intact, but sometimes we need to adopt the given data, for example, reverse the input list or pass some accumulator.

We have to make fewer decisions using recursion, which is neither exciting nor crucial. The crucial part is the nature of our decisions – notice that we moved from how to do something to what to do.

We don’t worry about how the code runs: where to start, where to end, and how to iterate; we specify what we want to achieve.

This is the shift we have to do. And this is the property that functional programmers prefer.

But this property is not tied to recursions. Let’s see what languages offer these days.

Alternatives

Rust, for instance, has a more concise for-loop alternative; here is a way to sum numbers:

let numbers = vec![-1, 2, 3, 4, 5];

let mut sum = 0;
for number in numbers {
    sum += number;
}

println!("The sum is ${sum}");
// Prints: The sum is 13

And, the same in Scala, we can use for-loop or for-comprehension:

val numbers = List(-1, 2, 3, 4, 5)

var sum = 0
for number <- numbers
do sum += number

println(s"The sum is $sum")
// Prints: The sum is 13

Moreover, we can add some transformation and filtering; for example, to sum the square of positive numbers:

val numbers = List(-1, 2, 3, 4, 5)

var sum = 0
for
  number <- numbers if number > 0
  square = number * number
do sum += square

println(s"The sum is $sum")
// Prints: The sum is 54

These constructs are more functional than the JavaScript loops we’ve started with – we no longer have to worry about the hows.

Also, in both languages, this is just a special syntax for using functions (or methods, or operations, or combinators, or pipelines, or whatever you want to call it).

💡 Rust’s for-loop syntax is syntactic sugar for iterators, which are responsible for the logic of iterating over some items.

💡 Scala’s for-comprehension is syntactic sugar for a sequence of calls to these methods: foreach, map, flatMap, and withFilter, which can be used on any type that defines these methods.

So, these (and other) functions can often be directly used to achieve the same results more concisely:

let numbers = vec![-1, 2, 3, 4, 5];

let sum: i32 = numbers
    .iter()
    .filter(|&n| *n > 0)
    .map(|x| x * x)
    .sum();

println!("The sum is ${sum}");
// Prints: The sum is 54

val numbers = List(-1, 2, 3, 4, 5)

val sum = numbers.filter(_ > 0).map(n => n * n).sum

println(s"The sum is $sum")
// Prints: The sum is 54

We say: filter these out, square the numbers, and then sum them up. We don’t worry about the type of the collection, how many elements it has, how to traverse it, etc.

A practical walkthrough

aka How I usually go about solving a problem using recursion

Imagine we have a problem:

We have a list of responses from different services.
Each response is either a successful number or a failure message.
We need to return one result:
- either a list of all successful numbers if there are no failures,
- or the message of the first failure.

// From
val responses: List[Either[String, Int]]

// To
val result: Either[String, List[Int]]

Each result is represented by the Either type (like Result in Rust):

Right represents success and contains a value (in our case, a number).
Left represents failure and contains an error value (in our case, an error message).

These are the example inputs and outputs:

// If all the responses are successful 
List(Right(1), Right(25), Right(82))
// The result should be: 
// Right(List(1, 25, 82))

// If there is at least one error
List(Right(1), Right(25), Left("boom"), Right(82), Left("boom 2"))
// The result should be:
// Left("boom")

We start with this question: What is the (initial) input to the recursive function?

Do we need all the elements? Yes, there is no way around it; we need to process the results:

def process(
    results: List[Either[String, Int]]
): Either[String, List[Int]] = ???

Do we need anything else? Here is a reminder:

If there is an error, we return that element right away.
If there are no errors, we must accumulate (keep track of) all the successful values.

So, while going through the results, we have to accumulate some values: we start with an empty list (and when we see a successful one, we append it to the list).

def process(
    results: List[Either[String, Int]],
    accumulator: List[Int]
): Either[String, List[Int]] = ???

process(results, List.empty)

This is not the finest interface – users shouldn’t deal with internal accumulators. We can wrap it up like a candy (or a sausage) and expose only what’s needed:

def process(results: List[Either[String, Int]]): Either[String, List[Int]] =
  go(results, List.empty)

// internal, recursive function
def go(
    results: List[Either[String, Int]],
    accumulator: List[Int]
): Either[String, List[Int]] = ???

💡 This pattern is quite common, see recursive go.

Now we can think about the recursion cases. We recurse over a list; a list is either empty (Nil in Scala) or has elements. Additionally, we can split a list as a head (first element) and a tail (the rest of the elements). Let’s show it with a skeleton:

def go(
    results: List[Either[String, Int]],
    accumulator: List[Int]
): Either[String, List[Int]] = results match {
  case head :: rest => ???
  case Nil          => ???
}

What is the base case? The recursion stops when the list ends (or doesn’t even begin) – when the list is empty. It means there are no errors, and we return success. accumulator should contain all the successful values:

if the original list is empty, accumulator is empty;
otherwise, accumulator contains all the numbers. Success!

def go(
    results: List[Either[String, Int]],
    accumulator: List[Int]
): Either[String, List[Int]] = results match {
  case head :: rest => ???
  case Nil          => Right(accumulator)
}

What is the recursive case? On every step, we have to decide what to do with a head, a tail, and calling the recursion. What is head? It contains a current value, which is either a successful number or a failure message:

def go(
    results: List[Either[String, Int]],
    accumulator: List[Int]
): Either[String, List[Int]] = results match {
  case Left(failure) :: rest => ???
  case Right(result) :: rest => ???
  case Nil                   => Right(accumulator)
}

If we’re looking at a failure, that’s it; we’re done, and we can just return it – we don’t care about the rest of the list and accumulated values:

def go(
    results: List[Either[String, Int]],
    accumulator: List[Int]
): Either[String, List[Int]] = results match {
  case Left(failure) :: rest => Left(failure)
  case Right(result) :: rest => ???
  case Nil                   => Right(accumulator)
}

And if it’s a successful value?

We add it to the accumulator.
We keep the recursion going, we have to iterate through the rest of the list.

We call the go function again, but this time the input is the rest of the list, and accumulator contains another successful value:

def process(results: List[Either[String, Int]]): Either[String, List[Int]] =
  go(results, List.empty)

def go(
    results: List[Either[String, Int]],
    accumulator: List[Int]
): Either[String, List[Int]] = results match {
  case Left(failure) :: rest => Left(failure)
  case Right(result) :: rest => go(rest, accumulator :+ result)
  case Nil                   => Right(accumulator)
}

And that’s it.

process(List(Right(1), Right(25), Right(82))
// Right(List(1, 25, 82))

process(List(Right(1), Right(25), Left("boom"), Right(82), Left("boom 2")))
// Left("boom")

Alternatives

Remember how we talked about alternatives?

We can refactor our process using a standard function called sequence.

import cats.implicits._

def process(results: List[Either[String, Int]]): Either[String, List[Int]] =
  results.sequence

process(List(Right(1), Right(25), Right(82))
// Right(List(1, 25, 82))

process(List(Right(1), Right(25), Left("boom"), Right(82), Left("boom 2")))
// Left("boom")

And that’s it. There are no tricks or magic behind it. Here is the beauty and power of functional programming. It’s also reusable and quite common, for example:

You sent multiple requests, and one service failed. You can just abort all the other operations and return the failure – you don’t have to wait or waste resources.
Same with accessing a database.
Parsing some data you got from the frontend.

If we change the type, for instance, to optional values, we don’t need to change the body:

def process(results: List[Option[Int]]): Option[List[Int]] =
  results.sequence

Final words

If you wrote thousands of loops, will writing recursion for the first time be easy? No.

Will it be very beneficial? Well, depends on your goals. If you want to impress your colleagues, probably not. If you have long term goals or aim to expand your horizon? Perfect!

After writing hundreds (or thousands) of loops and recursion, do I prefer a recursion to a loop? Yes, anytime.

Do I prefer using a combinator or a nicer comprehension syntax? Yes, most of the time. But recursion is an excellent tool for some jobs.