0

我们目前正在研究谓词reduce的实现，它需要一个列表L，一个二元函数F，它对L的元素进行操作，并且具有中性元素N，并将它们映射到通过将F应用于获得的数字E L 的元素递归。

到目前为止，这是我们的代码：

reduce([],F,NEUTRAL,EE).

reduce([H|T],F,NEUTRAL,EE) :-
    Goal =.. [F, H, NEUTRAL, EE],
    call(Goal),
    reduce(T,F,NEUTRAL,EE).

add(N1,NEUTRAL, EE) :- EE is EE + N1 + NEUTRAL.

mult(N1,NEUTRAL, EE) :- EE is N1 * EE * NEUTRAL.

问题是：对于相同的示例查询，例如?- reduce([], add, 0, R).我们只得到一个布尔值（在这种情况下为真），对于其他人返回一个错误，这告诉我们我们的参数没有正确实例化。我们真正的目标是像 Response 一样R = 0。（对于上面给出的示例）。

希望你能帮助我们，请不要太复杂，因为我们是 Prolog 初学者；）

4

4 回答 4

3

基于上面的评论和你仍然是 Prolog 初学者的事实，我将尝试解释一些可能不太清楚的事情：

What are variables in Prolog and what is instantiation ?

在 Prolog 中，变量是以大写字母和匿名变量开头的_ （只是下划线定义了一个匿名变量，它是一个没有名称的变量）。Prolog 中的变量意味着它们可以表示任何东西，一个列表、一个字符串、一个原子（......无论如何），当你使用一个新变量时，它不会被实例化，这意味着它可以表示任何东西，但现在它确实表示 - 它没有'不是bind列表，原子......当你想实例化一个变量时，你可以这样做：

  • 通过使用统一=/2，例如X = 2统一实例化变量 X 与数字 2。
  • 或仅使用类似上述is/2的表达式。X is 2

非常重要的是，当 Prolog 中的一个变量被实例化时，我们知道它代表什么并且我们不能改变例如X =2, X = 3 will fail!!，因为我们知道 X 与 2 绑定并且我们尝试用 3 重新实例化失败。

What is =/2, is/2, and what's the difference between these two prediactes ??

  • is/2：它将算术 表达式的结果返回给未实例化的变量。这意味着您可以像这样使用它： X is 2, or X is mod(Z,Y)但重要的是要注意这里的任何内容，expression MUST be instantiated如果它是以前的 Y 和 Z 之类的变量。如果表达式未实例化，您将获得instantiation error与您的情况相同的结果。如果 X 没有被实例化，即使是简单的事情2 is X+1也会因实例化错误而失败，所以不要指望 is/2 会返回类似于X=1前一种情况的东西，这是一个明显的答案（但不是唯一的，所以它会不一致！）。算术表达式也意味着你不能使用类似的东西X is [], 将 X 与空列表统一这当然会失败，所以为了做到这一点=/2，如下所述。

  • =/2：这用于将变量（或一般而言的术语）与另一个术语统一。例如，您可以像这样使用它：X = 2将 X 与数字 2X = [1, 2]统一，或者将 X 与一个列表统一，或者X = 1 + 2 不会给出 3 而只是术语 1 + 2，我认为最后两个示例清楚地显示了与is/2.

But then how could we use arithmetic expressions like is/2 but more relational ?

这里的答案是library CLPFD（正如@lurker 在评论中所推荐的那样）您所要做的就是将其:- use_module(library(clpfd)).放入您的文件中并使用运算符#=而不是is/2. 现在您可以尝试X #= 2，它将用数字 2 或什至实例化变量 X， 2 #= 1 + X现在您没有收到实例化错误，但您得到了答案X = 1，因此您可以看到它现在更具相关性。

现在问题...

我同意@Boris 中性不应该通过递归进行，而是用函数声明。虽然我会尽量跟上你的回答尝试：

首先，当尝试在 swi prolog 中使用您的代码查询文件时，我得到：

Warning: /Users/Desktop/reduce.pl:1:
    Singleton variables: [F,NEUTRAL,EE]

这表示变量 F,Neutral,EE 在这个子句中是单例的：

reduce([],F,NEUTRAL,EE).

如您所见，您没有在此子句中的任何地方使用，例如变量 F。

在我看来，reduce 谓词应该因空列表而失败，因为您不能对中性元素和带有两个参数的函数进行任何操作。因此，作为基本情况，我将使用只有一个元素的列表来定义：

reduce([H],F,NEUTRAL,EE):-
        Goal =.. [F, H, NEUTRAL, EE], 
        call(Goal).

然后如上所述，规则如下：

add(N1,NEUTRAL, EE) :- EE is EE + N1 + NEUTRAL.

将导致实例化错误，因为在 EE 中是 var 并且您不能在 is/2 中使用它，但即使它已被实例化，您也无法使用它，因为正如所解释的 EE is EE + whatever那样不起作用，因为you try to reinstantiate a variable..!!

为了修复它，我会尝试使用另一个变量进行下一次递归，然后计算结果如下：

 reduce([H],F,NEUTRAL,EE):-
     Goal =.. [F, H, NEUTRAL, EE], 
     call(Goal).
  reduce([H|T],F,NEUTRAL,EE) :-
     reduce(T,F,NEUTRAL,EE1),
     Goal =.. [F, H, EE1, EE],
     call(Goal).

（这里添加了一个新变量 EE1 进行递归调用，然后根据递归调用返回的 EE1 的 Result 计算结果。）

现在让我们测试一下：

?- reduce([1,2,3,4],add,0,L).
L = 10 ;
false.

?- reduce([1,2,3,4],mult,1,L).
L = 24 ;
false.

L=10当它通过按“;”给你结果时，还有一件事 我们要求更多答案并返回 false，因为没有可能的答案。错误或真实的事情只是 Prolog 的顶层通知您谓词成功或失败的一种方式。例如：

?- reduce([1,2,3,4],mult,1,24).
true ;
false.

这表明上述情况是正确的，当我们询问是否有任何其他方式可能是真的时，它返回错误......就是这样，毕竟Prolog似乎没有那么糟糕:)（根据你的描述）。
作为一个练习，您可以尝试使用 CLPFD 编写相同的代码，以便更具关系性并能够回答以下查询：reduce(L,mult,1,24).也许@Boris 的想法是不通过递归一直携带中性。

编辑

根据@false 的建议和有用的评论，我将使用 call/N 编写第二种方式，这显然更好（见评论...）：

reduce([H],F,NEUTRAL,EE):-
        call(F, H, NEUTRAL, EE).
reduce([H|T],F,NEUTRAL,EE) :-
        reduce(T,F,NEUTRAL,EE1),
        call(F, H, EE1, EE).
于 2017-05-25T14:25:12.757 回答
3

您需要中性元素来结束递归。您不需要在每一步都使用它。我几乎要说中性元素属于运算符，而不是归约。像这样的东西：

operation_neutral(add, 0).
operation_neutral(mult, 1).

然后，您reduce可能看起来像这样：

reduce([], Op, Result) :- operation_neutral(Op, Result).
reduce([X|Xs], Op, Result) :-
    reduce(Xs, Op, R0),
    call(Op, X, R0, Result).

但是，让我们暂时保持简单，并按照问题中的建议进行操作。仅当操作数列表为空时才需要中性元素来设置结果：

reduce([], _, N, N).

否则，进入递归，然后将操作应用于结果（您可以call直接使用）：

reduce([X|Xs], Op, N, R) :-
    reduce(Xs, Op, N, R0),
    call(Op, X, R0, R).

例如，您可以在此处查看如何使用.reduce/4append/3

你看到N里面了call吗？我没有看到它，它也不属于那里。

为了完整起见，这两个运算符：

add(X, Y, R) :- R is X+Y.
mult(X, Y, R) :- R is X*Y.

也没有提到中性元素。

顺便说一句：您所说的“减少”也称为列表上的“折叠”。你可以这样定义你reduce/3的foldl：

reduce(List, Op, Result) :-
    operation_neutral(Op, N),
    foldl(Op, List, N, Result).

递归和call两者都发生在里面foldl，你根本不需要reduce/4。

你将如何用程序语言解决这个问题？使用具有类 C 语法的伪代码，并假设我们对泛型有一些支持，它可以像这样：

template <typename A, typename Op>
A reduce(A[] operands, Op op) {
    return reduce(operands, op, 0);
}

template <typename A, typename Op>
A reduce(A[] operands, Op op, int n) {
    if (n == operands.length) return neutral<Op>();
    return op(operands[n], reduce(operands, op, n+1));
}

（显然，如果这确实是 C++，我们将使用迭代器，而不是索引......）

它与 Prolog 版本没有什么不同。如果你按照foldl上面的方法做，它可能看起来像这样：

template <typename A, typename Op>
A reduce(A[] operands, Op op) {
    A x = neutral<Op>();
    for (int n = 0; n < operands.length; ++n)
        x = op(x, operands[n]);
    return x;
}

同样，没有提到循环内的中性元素，也没有在对op().

于 2017-05-25T04:46:02.187 回答
-2

正如前面的答案中提到的，您真的想消除对call/99.

这里有一些让你开始的东西。它是您原来的完全功能失调的代码，具有不同的语法。我的意思是，我希望提供一种可能对您有用的替代语法，但原始的损坏语义保持不变。

  % [ reduce , VECTOR , FUNCTION , NEUTRAL , EE ] 

  :- [library(clpfd)] .

  [reduce , [] , F , NEUTRAL , EE] :- ( true ) .

  [reduce , [N|NN] , F , NEUTRAL , EE]
  :-
  (
      [F , N , NEUTRAL , EE] ,
      [reduce , NN , Z , NEUTRAL , EE] 
  )
  .

  [add , N , NEUTRAL , EE] :- ( EE #= EE + N + NEUTRAL ) .

  [mult , N , NEUTRAL , EE] :- ( EE #= N * EE * NEUTRAL ) .

为了方便比较，这里是原图...

  %

  reduce([],F,NEUTRAL,EE).

  reduce([H|T],F,NEUTRAL,EE) :-
      Goal =.. [F, H, NEUTRAL, EE],
      call(Goal),
      reduce(T,F,NEUTRAL,EE).

  add(N1,NEUTRAL, EE) :- EE is EE + N1 + NEUTRAL.

  mult(N1,NEUTRAL, EE) :- EE is N1 * EE * NEUTRAL.
于 2017-05-28T02:55:04.280 回答
-2

我希望这个部分答案不会太离题，因此不能将其包含在本次讨论中。

关于 OP 语句“对于相同的示例查询，例如？-reduce([], add, 0, R)。我们只是得到一个布尔值（在这种情况下为真）”，重要的是要对你的意思有一个很好的解释“真的” 。在我看来，将您标识的“返回值”（即（隐式）返回值）视为具有“布尔”类型是不合适的。这是因为布尔类型 >>"false"与true<<的含义相反。在该特定上下文的序言中（即关于（隐式）返回值），布尔类型期望的应用不适用，因为在该类型和非相似的布尔类型的情况下 --- >>“false”表示不同于"true"<< 的东西。

于 2017-05-27T23:22:03.863 回答