Функциональный способ проверки наличия в списке повторяющихся элементов

Question

У меня есть список элементов списка, и я хотел бы проверить, есть ли дубликаты. Я также хотел бы сломаться рано - мне все равно, что такое дубликаты, и если их много, я просто хочу знать, есть ли хотя бы один.

Императивный способ, который соответствует счёт будет:

fun main() {
    println(hasDuplicates(listOf(
        listOf("1", "2", "3"),
        listOf("4", "5"),
        listOf("1", "2")
    )))
}

fun hasDuplicates(input: List<List<String>>): Boolean {
    val seen = mutableSetOf<String>()
    input.forEach { inner ->
        inner.forEach { element ->
            if (!seen.add(element)) {
                return true
            }
        }
    }
    return false
}

Другой способ, без явной итерации, будет:

fun hasDuplicates(input: List<List<String>>): Boolean {
    val flat = input.flatten()
    return flat.size != flat.toSet().size
}

, но при этом итерируется весь список и даже создается плоский посредник на первом шаге.

У меня есть идея, но я не знаю, как ее реализовать: предположим, я мог бы сопоставить каждый (уплощенный) элемент списка с количеством раз, которое он уже был просмотрен. Пока у меня есть это:

fun hasDuplicates(input: List<List<String>>): Boolean {
    return input.asSequence().flatten()
//        .onEach {
//            println("getting $it")
//        }
        .groupingBy { it }
        .eachCount()
        .any { (_, count) -> count > 1 }
}

Он делает то, что должен, но сначала перебирает весь список (раскомментируйте посредника onEach, чтобы увидеть), чтобы собрать группы. Идея будет постепенно генерировать элемент и его количество, например (для списка ввода ["1", "2", "1"]:

// (element, seenCount)
("1", 0)
("2", 0)
("1", 1)

, и в этот момент я могу просто проверить seenCount > 0 и вернуться рано.

Любая помощь? Любые другие идеи также приветствуются.

ОБНОВЛЕНИЕ: Понял, не совсем первоначальная идея, но, кажется, работает:

fun hasDuplicates(input: List<List<String>>): Boolean {
    input.asSequence().flatten()
        .onEach {
            println("getting $it")
        }
        .fold(mutableSetOf<String>()) { seen, element ->
            if (!seen.add(element)) {
                return true
            }
            seen
        }
    return false
}

Приведенный выше код работает немного хуже, чем в самой первой версии с циклами в худшем кадре (без дубликатов), почти так же, как в лучшем случае (вторым элементом является дубликат) и в «среднем» case (средний элемент сглаженного списка является дубликатом).

Answer 1

Идея, описанная в вопросе, может быть реализована следующим образом:

fun hasDuplicates(input: List<List<String>>): Boolean {
    input.asSequence().flatten()
        // .onEach {
        //     println("getting $it")
        // }
        .groupingBy { it }
        .aggregate { _, _: Int?, _, first ->
            if (first) {
                1
            } else {
                return true
            }
        }
    return false
}

Тип аккумулятора (Int? выше) не имеет значения, поскольку он не используется.

Но следующее решение для меня даже лучше, поскольку оно позволяет мне возвращать набор в случае, если все уникально, что мне понадобится позже:

fun uniqueOrNull(input: List<List<String>>): Set<String>? {
    return input.asSequence().flatten()
        .fold(mutableSetOf()) { seen, element ->
            if (!seen.add(element)) {
                return null
            }
            seen
        }
}

Использование aggregate также будет работать, но работает ничтожно хуже и сложнее для читателя:

fun uniqueOrNull(input: List<List<String>>): Set<String>? {
    return input.asSequence().flatten()
        .groupingBy { it }
        .aggregate { _, _: Int?, _, first ->
            if (first) {
                1
            } else {
                return null
            }
        }.keys
}