Продукт массива с динамическим числом аргументов

Question

У меня есть функция, которая выполняет массив:

arrayProduct(l1,l2,l3) = [[a, b, c] |
    a := l1[_]
    b := l2[_]
    c := l3[_]
]

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

animals1 = ["hippo", "giraffe"]
animals2 = ["lion", "zebra"]
animals3 = ["deer", "bear"]

Тогда вывод arrayProduct(animals1, animals2, animals3) было бы:

[["hippo","lion","deer"],["hippo","lion","bear"],["hippo","zebra","deer"],["hippo","zebra","bear"],["giraffe","lion","deer"],["giraffe","lion","bear"],["giraffe","zebra","deer"],["giraffe","zebra","bear"]]

Если я могу гарантировать, что входные данные всегда будут списками, я мог бы создать функцию, которая будет делать то же самое, за исключением того, что она может принимать динамическое количество списков в качестве входных данных, а не только 3?

Я также изучаю, можно ли сделать это только с одним аргументом, содержащим все массивы внутри него, в отличие от принятия нескольких аргументов. Например:

[["hippo", "giraffe"], ["lion", "zebra"], ["deer", "bear"], ["ostrich", "flamingo"]]

Любое понимание решения с помощью любого подхода будет оценено.

Answer 1

Нет известного способа вычислить произвольное N-линейное перекрестное произведение в Rego без встроенной функции.

Почему что-то не может быть написано на языке, может быть сложно объяснить, потому что это сводится к отрисовке доказательства. Нам нужно аргументировать, что в Rego нет политики, вычисляющей N-стороннее перекрестное произведение. Формальные доказательства выразительности / сложности не были разработаны, поэтому лучшее, что мы можем сделать, - это попытаться сформулировать, почему это может быть невозможно.

Для N-образного кросс-продукта это сводится к тому факту, что Rego гарантирует завершение для всех политик на всех входах и для этого ограничивает, насколько глубоко может быть вложенная итерация. В вашем примере (используяsome и отступ для ясности) у вас есть 3 вложенных цикла с индексами i, j, k.

arrayProduct(l1,l2,l3) = [[a, b, c] |
    some i
        a := l1[i]
        some j
            b := l2[j]
            some k
                c := l3[k]
]

Для реализации N-стороннего кросс-продукта arrayProduct([l1, l2, ..., ln]) вам понадобится что-то эквивалентное N вложенным циклам:

# NOT valid Rego
arrayProduct([l1,l2,...,ln]) = [[a, b, ..., n] |
    some i1
        a := l1[i1]
        some i2
            b := l2[i2]
              ...
                    n := ln[in]
]

где, что важно, степень вложенной итерации N зависит от ввода.

Чтобы гарантировать завершение, Rego ограничивает степень вложенной итерации в политике. Вы можете вложить итерацию столько раз, сколько у вас естьsome(или, точнее, переменные), появляющиеся в вашей политике. Это аналогично SQL, ограничивающему количество СОЕДИНЕНИЙ до тех, которые появляются в определениях запросов и представлений.

Поскольку степень вложенности, необходимая для N-образного перекрестного произведения, равна N, и N может быть больше, чем количество somes в политике нет способа реализовать N-образное перекрестное произведение.

Для сравнения, количество ключей или значений, которые повторяются внутри любого одного цикла CAN и обычно ДЕЙСТВИТЕЛЬНО зависят от ввода. Это количество петель, которое не может зависеть от ввода.

Answer 2

Невозможно вычислить n-арное произведение списков / массивов (или наборов или объектов) в Rego без добавления встроенной функции.

В сценарии, описанном выше, предоставление динамического количества массивов в качестве входных данных функции было бы эквивалентно передаче массива массивов (как вы упомянули в конце):

arrayProduct([arr1, arr2, ..., arrN])

Это работает, за исключением того, что когда мы пытаемся реализовать arrayProductмы застреваем, потому что Rego не разрешает рекурсию, а итерация происходит только тогда, когда вы вставляете переменную в ссылку. В вашем исходном примереl1[_] ссылка на элементы в первом списке и _ - уникальная переменная, относящаяся к индексам массива в этом списке.

OPA / Rego оценивает это выражение, находя назначения каждому _которые удовлетворяют запросу. "Проблема" в том, что для этого требуется одна переменная для каждого списка во входных данных. Если длина массива массивов неизвестна, нам понадобится бесконечное количество переменных.

Если вам действительно нужна n-арная функция продукта, я бы посоветовал вам реализовать специальную встроенную функцию.