Check if a List Is a Sublist of Another List

1. Overview

In this tutorial, we will discuss and compare several methods to determine whether one List is part of another List in Scala. We’ll go over four different ways of solving this problem, each with slightly different outcomes, which should fulfill every use case we could have for this problem.

2. Using .forAll

The first approach we’ll explore is using the .forAll function on Lists. This function will only return true if the given predicate is true for all elements in the List:

def usingForAll(bigList: List[String], littleList: List[String]): Boolean = {
    littleList.forall(bigList.contains)
  }

In this function, we check if littleList is a sublist of bigList by iterating through littleList using the .forAll function, checking that every element in littleList can be found in bigList. If this returns true, it indicates that bigList contains all the elements of littleList, making it a sublist of bigList. It’s worth noting that this approach does not take element order into consideration.

3. Using .foldLeft

Next, we’re going to solve this problem using .foldLeft. The .foldLeft function takes a starting value and will iterate through a List, modifying the starting value as it goes and returning the final value of whatever the starting value has become:

def usingFoldLeft(
  bigList: List[String],
  littleList: List[String]
): Boolean = {
  bigList
    .foldLeft(littleList)((lList, string) => {
      val isStringInList = lList.headOption.map(_ == string).getOrElse(false)
      if (isStringInList) lList.tail else lList
    })
    .isEmpty
}

This function is folding over bigList, using littleList as the starting value. For every iteration through bigList, we take the .headOption of lList and check if that is equal to the current element from bigList. If it is, we return the tail of lList, as the head element has been found. If not, we return all of lList as the head element still is yet to be found.

Once the .foldLeft has been completed, if we’re left with an empty List, then all the elements in littleList were found within bigList, therefore, it’s a sublist.

Compared to the previous approach, this function does take order into consideration since it checks the head of the List each time. However, it will accept gaps, so the elements in littleList need to be present in bigList, in the same order, but not necessarily together.

4. Using .sliding

In this approach, we’ll utilize a function on Iterable in Scala called .sliding. The .sliding function returns a sliding window through the List of a given size, returning a List of List. We can provide the arguments for how big we want the window to be and how many big each step should be.

For example, if we had List(“a”, “b”, “c”, “d”) and called .sliding(2, 1) on it, it would return a sliding window of 2 elements, stepping 1 element through for each window: List(List(“a”, “b”), List(“b”, “c”), List(“c”, “d”)).

Now that we understand how sliding works, let’s have a go at using it to solve our sublist problem:

def usingSliding(bigList: List[String], littleList: List[String]): Boolean = {
  bigList.sliding(littleList.size, 1).exists(_ == littleList)
}

In this function, we create a sliding window with windows the same size as littleList. We’re then mapping through the sliding window and checking for an exact match for littleList.

This is the first method we’ve used to find an exact match for littleList within bigList. So, this will only return true if the elements of littleList exist within bigList in order, with no gaps.

5. Using .containsSlice

The final method we’re going to investigate to solve this issue is using a function called .containsSlice. It’s used to check if the List provided in the arguments is a sublist of the List .conatinsSlice has been called on:

def usingContainsSlice(
  bigList: List[String],
  littleList: List[String]
): Boolean = {
  bigList.containsSlice(littleList)
}

This is the simplest of all the ways we’ve tried, as it’s an “out-of-the-box” solution in the standard Scala library. Like the previous section, this will method will check that bigList contains all elements of littleList, in order, with no gaps.

6. Conclusion

In this article, we’ve explored four ways to check if a List is a sublist of another List in Scala. The approach depends on the use case and how strict we must be with the checking. If the order doesn’t matter to us, then the original method using the .forall function is best. If we want elements to be in order but not necessarily together, then the .foldLeft solution is our best bet.

And finally, if we need the elements to be in order, with no gaps, then we can use either the .sliding or .containsSlice method.

As always, the sample code used in this tutorial is available over on GitHub.