Kotlin:以函数方式组合列表中的某些元素

Question

最近有人问我，我可以推荐哪些Kotlin stdlib函数来处理某个问题:将具有相同开始/结束时间的某些会议组合在一个列表中。

假设这个数据类给出了一个会议：

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?
}

我已经用fold解决了这个问题，但我觉得它不是正确的用法(一个简单的forEach就足够了)：

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()
}

另外，使用forEach而不是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()
}

然而，我觉得必须有一种更优雅、功能更强大、易变性更小的方法来解决这个问题。您将如何处理此问题？

哦，在我忘记之前:我当然有一些单元测试可供您试用！

@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))
}

这里有一个入门的Kotlin Playground link。

非常感谢你的帮助！

Answer 1

这里有一个函数式的方法。其思想是获取列表中的所有会议端点，然后比较相邻的endTime和startTime对，并筛选出相等的端点。然后将结果分组成对，并根据它们生成结果会议列表。

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) }
}

它适用于非空的会议列表；处理空的会议列表需要在开始时进行额外的if (meetings.isEmpty()) return meetings检查。

然而，我并不觉得它更优雅，因为对于一个大型会议列表，它需要更多的对象分配。在操作链的开头使用.asSequence()函数将meetings转换为一个序列可能会有一些帮助，但不会有太大帮助。

Answer 2

我发现使用fold的解决方案是最优雅的，而且它没有分配任何多余的对象。然而，我能够简化它：

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
    }
}

请注意，这不一定要通过搜索列表来删除以前的会议。它只是将以前的会议替换为会议的组合。

它确实需要一个可变列表，因为这个解决方案应该是有效的。

Answer 3

递归和不可变。

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))
    }
}

递归函数接受3个参数：

• tail:不能再组合的已处理会议
• head:我们目前正在处理并试图扩展的会议与possible
• remaining：
• meetings

一样多