1. Overview
Situations often arise where we need to delve into nested structures, such as finding specific elements in a “lists within lists” structure. Kotlin, with its expressive syntax and powerful features, provides elegant and efficient solutions to such challenges.
In this tutorial, we’ll explore how to efficiently find the first matching element in nested Lists using Kotlin.
2. Introduction to the Problem
Imagine we have a nested List containing various elements, and our objective is to find the first occurrence of a particular element within this nested structure.
As usual, an example can quickly clarify the problem. Let’s say we have two data classes:
data class Player(val name: String, val score: Int)
data class Team(val name: String, val players: List<Player>)
As the code shows, a Team object holds a List of Players. Our input is a List of Team instances, and we aim to find the first Player whose score is higher than 100. Also, we assume the input (List<Team>) always contains at least one matched player.
Next, let’s prepare some example data:
val teamA = Team(
"Team A", listOf(
Player("Sam", 7),
Player("Mike", 35),
Player("Vincent", 15),
Player("Paul", 12)
)
)
val teamB = Team(
"Team B", listOf(
Player("Tom", 50),
Player("Jim", 35),
Player("Kai", 150),
Player("Tim", 200)
)
)
val teamC = Team(
"Team C", listOf(
Player("Leo", 15),
Player("Sean", 25),
Player("Jack", 10),
Player("Tim", 8)
)
)
val teamD = Team(
"Team D", listOf(
Player("Eric", 54),
Player("Liam", 104),
Player("Kevin", 70),
Player("Peter", 177),
)
)
We created four Team instances. Each Team has four players. Now, let’s put these four teams in a List:
val teams = listOf(teamA, teamB, teamC, teamD)
As we can see, none of the players in teamA have a score exceeding 100. In contrast, teamB has two players who meet our criteria: “Kai” and “Tim,” with “Kai” being the first player to fulfill the condition.
Next, let’s explore how to find “Kai” from the teams List.
For simplicity, we’ll employ unit test assertions to verify whether we get the expected result.
3. Using flatMap() and first()
One way to handle elements within the inner List in a nested List structure is by flattening the List of Lists. For example, we can use the flatMap() function to gather each Team instance’s players into one List<Player>, and then employ the first() function to find the first matched player:
val result = teams.flatMap { it.players }.first { it.score > 100 }
assertEquals(Player("Kai", 150), result)
As we can see, the code is compact and easy to read. It’s worth noting that the flatMap() function serves as an extension of the Iterable interface:
public inline fun <T, R> Iterable<T>.flatMap(transform: (T) -> Iterable<R>): List<R>
Consequently, if the Iterable object maintains a guaranteed order, the List result produced by flatMap() also retains that order.
We’ve solved the problem, but it’s important to note that the flatMap() function must iterate through each Team‘s players to aggregate them into the final List<Player>. Next, let’s add two log output lines to the solution, allowing us to track how this approach discovers the target player:
teams.flatMap {
log.info("Transforming players of the team: ${it.name}")
it.players
}.first {
log.info("Checking the player: ${it.name}")
it.score > 100
}
If we run the code again, we’ll see this output:
Transforming players of the team: Team A
Transforming players of the team: Team B
Transforming players of the team: Team C
Transforming players of the team: Team D
Checking the player: Sam
Checking the player: Mike
Checking the player: Vincent
Checking the player: Paul
Checking the player: Tom
Checking the player: Jim
Checking the player: Kai
The output makes it evident that flatMap()Â iterates through all Team objects in the teams List. In our scenario, it’s unnecessary to traverse through the players in teams C and D. Our example involves only four teams in the input List, with each team having four players. However, in real-world projects, the nested List might contain a substantial amount of data. Consequently, iterating through all elements becomes inefficient.
Next, let’s explore whether we can find a more efficient way to access only the essential elements within the nested List.
4. Creating a Function With Nested forEach()
One strategy to enhance efficiency involves manually controlling the iterations to terminate the loop once the target element is found. Since our input is a nested List, we can leverage nested forEach() to achieve that. Next, let’s create a function to solve the problem:
fun findTheFirstPlayerHigherThan100(teams: List<Team>): Player {
teams.forEach { team ->
log.info("Checking players of the team: ${team.name}")
team.players.forEach { player ->
log.info("|- Checking the player: ${player.name}")
if (player.score > 100) return player
}
}
throw IllegalStateException("No matched player found")
}
If we call the above function with our teams as the input, it returns the expected result:
val result = findTheFirstPlayerHigherThan100(teams)
assertEquals(Player("Kai", 150), result)
Additionally, by examining the output, we can observe that this approach avoids accessing unnecessary elements:
Checking players of the team: Team A
|- Checking the player: Sam
|- Checking the player: Mike
|- Checking the player: Vincent
|- Checking the player: Paul
Checking players of the team: Team B
|- Checking the player: Tom
|- Checking the player: Jim
|- Checking the player: Kai
5. Using the asSequence() Function
The nested forEach() approach efficiently solves the problem by avoiding unnecessary iterations. However, it’s less concise and straightforward than the flatMap() solution: teams.flatMap { it.players }.first { it.score > 100 }.
Another strategy to enhance the efficiency of the flatMap() approach while maintaining its idiomatic style is to convert the nested List to a Sequence before invoking flatMap():
teams.asSequence().flatMap { it.players }.first { it.score > 100 }
Next, let’s add some log outputs and test this line of code:
val result = teams.asSequence().flatMap {
log.info("Transforming players of the team: ${it.name}")
it.players
}.first {
log.info("|- Checking the player: ${it.name}")
it.score > 100
}
assertEquals(Player("Kai", 150), result)
As we can see, it does the job. Further, the console output shows this approach solves the problem efficiently:
Checking players of the team: Team A
|- Checking the player: Sam
|- Checking the player: Mike
|- Checking the player: Vincent
|- Checking the player: Paul
Checking players of the team: Team B
|- Checking the player: Tom
|- Checking the player: Jim
|- Checking the player: Kai
Next, let’s investigate why the asSequence() call prevents flatMap() from traversing unnecessary elements.
When we use asSequence(), we convert the Collection (in this case, the nested List) to a Sequence. A crucial distinction between Collection and Sequence is that Sequences are lazily evaluated, meaning elements are evaluated only when needed.
6. Conclusion
In this article, we explored how to find the first occurrence of a specific element within a nested List in Kotlin. Additionally, we discussed strategies for efficiently solving this problem by minimizing the traversal of unnecessary elements.
As always, the complete source code for the examples is available over on GitHub.
