0

我有一个执行数组产品的函数：

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"]]

任何对任何一种方法的解决方案的见解将不胜感激。

4

2 回答 2

2

在没有内置函数的情况下，没有已知的方法可以在 Rego 中计算任意 N 路叉积。

为什么不能用一种语言编写某些东西可能很难解释，因为它相当于一个证明草图。我们需要证明 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 将 JOIN 的数量限制为出现在查询和视图定义中的那些。

由于 N 路叉积所需的嵌套程度为 N，而 N 可以大于some策略中 s 的数量，因此无法实现 N 路叉积。

相比之下，在任何一个循环 CAN 中迭代的键或值的数量通常取决于输入。这是不能依赖于输入的循环数。

于 2020-04-30T17:52:04.063 回答
1

如果不添加内置函数，就不可能在 Rego 中计算列表/数组（或集合或对象）的 n 元乘积。

在上面描述的场景中，提供动态数量的数组作为函数的输入将等效于传递一个数组数组（就像你在最后提到的那样）：

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

这是可行的，除了当我们尝试实现时arrayProduct我们会卡住，因为 Rego 不允许递归，并且只有在将变量注入引用时才会发生迭代。在您的原始示例l1[_]中，是对第一个列表中元素的引用，并且_是引用该列表中数组索引的唯一变量。

_OPA/Rego 通过查找每个满足查询的分配来评估该表达式。“问题”是输入中的每个列表都需要一个变量。如果数组数组的长度未知，我们将需要无限数量的变量。

如果你真的需要一个 n 元乘积函数，我建议你现在实现一个自定义的内置函数。

于 2020-04-30T11:27:52.390 回答