Functional Programming With Scala - NonEmptyList

At Upsolver, our main programming language is Scala. One of Scala’s advantages is that it lets you combine object-oriented programming (OOP) with functional programming (FP) and get the best from both worlds.

However, most of our developers who start working in Scala come from the OOP world. If you’ve had very little exposure to FP, how would you know what those “best” things are? In addition, some parts of functional programming have a reputation of being difficult and abstract. Indeed, the names and concepts that libraries like Cats expose can look daunting to the uninitiated.

But the good news is that you don’t have to jump in at the deep end. You can get your feet wet and start reaping the benefits of FP using the tools I’ll present in this series.

Part 1: Avoiding edge cases with NonEmptyList #

Today we’ll look at the NonEmptyList type. We’ll use it as provided by the Cats library, but actually you’ll see it’s so easy you could have invented it yourself, and some of our team members actually did.

If you’ve been developing software for a non-zero amount of time, you’ll know that there are cases where it simply does not make sense for a list (or sequence, array or set) to be empty. You’ll reach places in the code where you have to abort, throw exceptions or do other ugly things if a certain list is empty.

• Despite all the progress with self-driving cars, the function in your application that assigns drivers to cars should probably receive at least one driver.
• As a trivial example, calling Scala’s .head method on an empty sequence will produce the following exception:

  java.util.NoSuchElementException: head of empty list
  at scala.collection.immutable.Nil$.head(List.scala:469)
  at scala.collection.immutable.Nil$.head(List.scala:466)
  ... 36 elided
  

Clearly, some functions only work properly with non-empty lists. Let’s look at a concrete example.

Example scenario #

You need to look up the IP address corresponding to a given host name on one of several DNS servers. Your task is to write a function that takes a host name and a list of DNS servers and return the IP address, if the lookup succeeds. The function has no way of knowing about any DNS servers other than the ones you provide.

The problem is that if the list of DNS servers is empty, you have no way of doing the lookup.

We’ll compare and contrast three solutions below. Note: the ??? is a placeholder for things we haven’t implemented.

Solution 1: Throwing an exception #

The most basic approach is to just throw an exception if the list is empty. The Option type of the return value will contain Some(value) if there is an IP address associated to that host name, and None otherwise.

// Approach: Throw an exception when called with an empty list, since we can't do the lookup.
// Downside: If the list is empty, you may only find out at runtime by getting an exception.
def lookupDns1(hostname: String, dnsServers: Seq[InetAddress]): Option[InetAddress] = {
  if (dnsServers.isEmpty) {
    throw new UnsupportedOperationException("Need to provide at least one DNS servers")
  } else {
    ??? // omitted
  }
}

Solution 2: Returning a special value #

The exception thrown in solution 1 is annoying, and if it shows up in your logs there’s definitely something wrong with your code. Let’s avoid throwing that exception.

// Approach: You can decide to not throw an exception, and just return `None` instead.
// Downside: Your function can fail because
// 1. you didn't pass in any DNS servers or
// 2. because the DNS record does not exist or
// 3. other reasons (like timeout etc.)
// While you can't prevent #2 and #3, clearly #1 is a silly reason for this thing to fail.
def lookupDns2(hostname: String, dnsServers: Seq[InetAddress]): Option[InetAddress] = {
  if (dnsServers.isEmpty) {
    None
  } else {
    ??? // omitted
  }
}

Solution 3: Preventing the function from being called #

Solution 2 is arguably a slight improvement over solution 1, because we no longer throw a pointless exception. However, we did not solve the fundamental problem: You can’t do the lookup if you don’t have at least one DNS server to send the request to. No one should ever call this function with an empty list as an argument. This is where NonEmptyList comes to the rescue:

// Approach: Using a NonEmptyList, you can prevent the function from being called without any DNS servers.
// Downside: Need to use this scary type from the Cats library. Just kidding.
import cats.data.NonEmptyList
def lookupDns3(hostname: String, dnsServers: NonEmptyList[InetAddress]): Option[InetAddress] = {
  // no need to handle an empty list, because there's no way of calling the function with such an argument
  // if we get `None` as a result, we know it's for "valid" reasons, as opposed to solution 2
  ??? // omitted
}

Conclusion #

As solution 3 demonstrates, using appropriate types prevents us from calling this function with nonsensical arguments.

So what’s the complicated machinery that achieves this? Have a look at the definition. A non-empty list is a list that contains its head and the (possibly empty) rest of the list. It’s that simple, and that’s why you could have invented it yourself.

Of course the advantage of using the version from the Cats library is that it comes with all the nice goodies you’d expect:

• .map() (whose return type is NonEmptyList)
• .filter() (whose return type is not a NonEmptyList and it should be obvious why)
• playing nice with all the other types in the same library

See the Cats documentation of NonEmptyList for more information.

In the next post in this series, we’ll look at other simple and powerful techniques from the Functional Programming toolbox.

Want to join a world-class software engineering team and solve some of the toughest cloud data processing challenges? Check out our open positions