Идиоматический способ создания n-арного декартового произведения (комбинации нескольких наборов параметров)

Question

Чтобы создать все возможные комбинации двух наборов параметров и выполнить над ними какие-либо действия, вы можете сделать:

setOf(foo, bar, baz).forEach { a ->
    setOf(0, 1).forEach { b ->
        /* use a and b */
    }
}

Однако, если у вас (потенциально много) больше параметров, это быстро превращается в пирамида гибели :

setOf(foo, bar, baz).forEach { a ->
    setOf(0, 1).forEach { b ->
        setOf(true, false, null).forEach { c ->
            setOf("Hello,", "World!").forEach { d ->
                /* use a, b, c and d */
            }
        }
    }
}

Вы можете написать это так же, как for петли, или по-другому так:

val dAction = { d: String -> /* use a, b, c and d */ }
val cAction = { c: Boolean? -> setOf("Hello,", "World!").forEach(dAction) }
val bAction = { b: Int -> setOf(true, false, null).forEach(cAction) }
val aAction = { a: Any? -> setOf(0, 1).forEach(bAction) }
setOf(foo, bar, baz).forEach(aAction)

Но я не думаю,это немного лучше, потому что здесь есть некоторые проблемы с читабельностью: действия d, c, b и a записываются в обратном порядке.Их спецификации типа не могут быть выведены, поэтому они должны быть указаны.Это последовательно наоборот по сравнению с пирамидой гибели.Порядок наборов, предоставляющих возможные значения, не должен иметь значения, но это имеет значение: вы просто хотите создать любые комбинации из набора наборов, однако в этом коде каждая строка зависит от предыдущего.

Это будетбыло бы очень хорошо иметь идиоматический способ сделать что-то вроде Python's или Haskell понимания, в котором вы ( почти как математическая запись ) можете сделать что-то вроде:

{ /* use a, b, c and d */
    for a in setOf(foo, bar, baz),
    for b in setOf(0, 1),
    for c in setOf(true, false, null),
    for d in setOf("Hello,", "World!")
}

Что очень легко прочитать: нет чрезмерного отступа, сначала интересует интересующее вас действие, источники данных очень четко определены и т. Д.

Примечание: похожие проблемы возникают с flatMap - flatMap -...- flatMap - map.

Есть идеи о том, как аккуратно создавать n-арные декартовы произведения в Котлине?

Answer 1

Я сам создал решение, поэтому мне не нужно добавлять зависимость, как подсказывает ответ Омара .

Я создал функцию, которая принимает любое количество наборовлюбой размер:

fun cartesianProduct(vararg sets: Set<*>): Set<List<*>> =
    when (sets.size) {
        0, 1 -> emptySet()
        else -> sets.fold(listOf(listOf<Any?>())) { acc, set ->
            acc.flatMap { list -> set.map { element -> list + element } }
        }.toSet()
    }

Пример:

val a = setOf(1, 2)
val b = setOf(3, 4)
val c = setOf(5)
val d = setOf(6, 7, 8)

val abcd: Set<List<*>> = cartesianProduct(a, b, c, d)

println(abcd)

Вывод:

[[1, 3, 5, 6], [1, 3, 5, 7], [1, 3, 5, 8], [1, 4, 5, 6], [1, 4, 5, 7], [1, 4, 5, 8], [2, 3, 5, 6], [2, 3, 5, 7], [2, 3, 5, 8], [2, 4, 5, 6], [2, 4, 5, 7], [2, 4, 5, 8]]

Функция cartesianProduct возвращает набор списков.Существует ряд проблем с этими списками:

• Любая информация о типах теряется, поскольку возвращаемый набор содержит списки, которые содержат объединение типов входных наборов.Тип возвращаемых элементов этих списков Any?.Функция возвращает Set<List<*>>, то есть Set<List<Any?>>.
• Списки могут быть любого размера, в то время как вы хотите, чтобы они были указанного размера (количество входных наборов, 4 в примере выше).

Однако, используя отражение, мы можем решить эти проблемы.Действие, которое мы хотим выполнить с каждым списком, можно записать как функцию (например, конструктор некоторого класса, который также является просто функцией):

data class Parameters(val number: Int, val maybe: Boolean?) {
    override fun toString() = "number = $number, maybe = $maybe"
}

val e: Set<Int> = setOf(1, 2)
val f: Set<Boolean?> = setOf(true, false, null)

val parametersList: List<Parameters> = cartesianProduct(e, f).map { ::Parameters.call(*it.toTypedArray()) }

println(parametersList.joinToString("\n"))

Вывод:

number = 1, maybe = true
number = 1, maybe = false
number = 1, maybe = null
number = 2, maybe = true
number = 2, maybe = false
number = 2, maybe = null

Подпись преобразования (::Parameters в примере) указывает контракт для содержимого списков.

Поскольку map { ::Parameters.call(*it.toTypedArray()) } не очень хорошо, я создал вторую функцию расширения, которая делает это дляme:

fun <T> Set<List<*>>.map(transform: KFunction<T>) = map { transform.call(*it.toTypedArray()) }

При этом код становится совершенно идиоматичным:

val parametersList: List<Parameters> = cartesianProduct(e, f).map(::Parameters)

Код доступен с этого GitHub Gist , где я буду обновлять его, еслиЯ когда-либо улучшал это.Существуют также тесты: декартово произведение без входов или с одним входом возвращает пустое множество , как математически ожидается .Я не говорю, что это оптимальное решение или что оно математически обоснованно (не каждое математическое свойство явно реализовано и проверено), но оно работает для цели вопроса.

Answer 2

Я бы рекомендовал использовать Arrow-kt Applicative on List.См. Пример:

val ints = listOf(1, 2, 3, 4)
val strings = listOf("a", "b", "c")
val booleans = listOf(true, false)

val combined = ListK.applicative()
    .tupled(ints.k(), strings.k(), booleans.k())
    .fix()

// or use the shortcut `arrow.instances.list.applicative.tupled`
// val combined = tupled(ints, strings, booleans)

combined.forEach { (a, b, c) -> println("a=$a, b=$b, c=$c") }

, который производит декартово произведение

a = 1, b = a, c = true

a = 1, b = b, c = true

a = 1, b = c, c = true

a = 2, b = a, c = true

a = 2, b = b, c = true

a = 2, b = c, c = true

a = 3, b = a, c = true

a = 3, b = b, c = true

a = 3, b = c, c = true

a = 4, b = a, c = true

a = 4, b = b, c = true

a = 4, b = c, c = true

a = 1, b = a, c = false

a = 1, b = b, c = false

a = 1, b = c, c = false

a = 2, b = a, c = false

a = 2, b = b, c = false

a = 2, b = c, c = false

a = 3, b = a, c = false

a = 3, b = b, c = false

a = 3, b = c, c = false

a = 4, b = a, c =false

a = 4, b = b, c = false

a = 4, b = c, c = false