Kotlin: combine certain elements in list in a functional way

Question

Recently I was asked what Kotlin stdlib functions I could recommend to handle a certain problem: combine certain meetings in a list that have the same start/end time.

Let's say a meeting is given by this data class:

data class Meeting(val startTime: Int, val endTime: Int)

fun main() {
    val meetings = listOf(
        Meeting(10, 11),
        Meeting(12, 15),  // this can be merged with
        Meeting(15, 17)   //  this one
    )
    println(combine(meetings))
    // should print: [Meeting(startTime=10, endTime=11), Meeting(startTime=12, endTime=17)]
}

fun combine(meetings: List<Meeting>): List<Meeting> {
    // TODO: elegant, functional way to do this?
}

I already solved this problem using fold, but I didn't feel it was the right use for it (a simple forEach should have been enough):

fun combine(meetings : List<Meeting>) : List<Meeting> {
    return meetings.fold(mutableListOf<Meeting>()) { combined: MutableList<Meeting>, meeting: Meeting ->
        val lastMeeting = combined.lastOrNull()
        when {
            lastMeeting == null -> combined.add(meeting)
            lastMeeting.endTime == meeting.startTime -> {
                combined.remove(lastMeeting)
                combined.add(Meeting(lastMeeting.startTime, meeting.endTime))
            }
            else -> combined.add(meeting)
        }
        combined
    }.toList()
}

Also, another solution with forEach instead of fold:

fun combine(meetings: List<Meeting>): List<Meeting> {
    val combined = mutableListOf<Meeting>()

    meetings.forEachIndexed { index, meeting ->
        val lastMeeting = combined.lastOrNull()
        when {
            lastMeeting == null -> combined.add(meeting)
            lastMeeting.endTime == meeting.startTime ->
                combined[combined.lastIndex] = Meeting(lastMeeting.startTime, meeting.endTime)
            else -> combined.add(meeting)
        }
    }

    return combined.toList()
}

However, I feel there must be a more elegant, functional way with less mutability to solve this. How would you approach this?

Oh, and before I forget: of course I have some unit tests for you to play around with! 😇

@Test
fun `empty meeting list returns empty list`() {
    val meetings = emptyList<Meeting>()
    assertEquals(emptyList<Meeting>(), combine(meetings))
}

@Test
fun `single meeting list returns the same`() {
    val meetings = listOf(Meeting(9, 10))
    assertEquals(meetings, combine(meetings))
}

@Test
fun `3 different meetings`() {
    val meetings = listOf(Meeting(9, 10), Meeting(11, 12), Meeting(13, 14))
    assertEquals(meetings, combine(meetings))
}

@Test
fun `2 meetings that can be merged`() {
    val meetings = listOf(Meeting(9, 10), Meeting(10, 11))
    assertEquals(listOf(Meeting(9, 11)), combine(meetings))
}

@Test
fun `3 meetings that can be merged`() {
    val meetings = listOf(Meeting(9, 10), Meeting(10, 11), Meeting(11, 13))
    assertEquals(listOf(Meeting(9, 13)), combine(meetings))
}

And here's a Kotlin Playground link to get started.

Thanks a lot for your help! 😊

Answer 1

Recursive and immutable.

fun combine(meetings: List<Meeting>): List<Meeting> {
    return if (meetings.isEmpty()) meetings
    else combineRecurse(emptyList(), meetings.first(), meetings.drop(1))
}

fun combineRecurse(tail: List<Meeting>, head: Meeting, remaining: List<Meeting>): List<Meeting> {
    val next = remaining.firstOrNull()
    return when {
        next == null -> tail + head
        next.startTime == head.endTime -> combineRecurse(tail, Meeting(head.startTime, next.endTime), remaining.drop(1))
        else -> combineRecurse(tail + head, next, remaining.drop(1))
    }
}

The recursive function takes 3 arguments:

• tail: Processed meetings that cannot be combined anymore
• head: The meeting we're currently working on and trying to extend as much as possible
• remaining: Unprocessed meetings

Answer 2

Here's a functional way. The idea is to get all the meeting endpoints in a list, then compare pairs of adjacent endTime and startTime and filter out those that are equal. Then group the result into pairs and make the resulting list of meetings from them.

fun combine(meetings: List<Meeting>): List<Meeting> {
    return meetings
        .zipWithNext { current, next -> listOf(current.endTime, next.startTime) }
        .filterNot { (end, start) -> end == start }
        .flatten()
        .let { listOf(meetings.first().startTime) + it + listOf(meetings.last().endTime) }
        .chunked(2) { (start, end) -> Meeting(start, end) }
}

It works with non-empty lists of meetings; handling an empty one is a matter of an additional if (meetings.isEmpty()) return meetings check in the beginning.

I don't find it, however, more elegant because it requires significantly more object allocations for a big list of meetings. Turning meetings into a sequence with the .asSequence() function in the beginning of the operation chain might help a bit, but not that much.

Answer 3

I find the solution with fold most elegant, also it doesn't allocate any excess objects. However, I was able to simplify it:

fun combine(meetings : List<Meeting>) : List<Meeting> {
    return meetings.fold(mutableListOf()) { combined: MutableList<Meeting>, meeting: Meeting ->
        val prevMeeting = combined.lastOrNull()
        if (prevMeeting == null || prevMeeting.endTime < meeting.startTime) {
            combined.add(meeting)
        } else {
            combined[combined.lastIndex] = Meeting(prevMeeting.startTime, meeting.endTime)
        }
        combined
    }
}

Note that this doesn't have to search through the list to remove the previous meeting. It just replaces the previous meeting with the combination of the meetings.

It does need one mutable list, because this solution should be efficient.