Prolog：如何实现三个中两个最大数的平方和？

Question

本书 Structure and Interpretation of Computer Programs 的练习 1.3 提出以下问题：

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

我正在学习序言。这是我尝试实现的功能：

square(X, Y) :- Y is X * X.
squareTwoLargest(X, Y, Z, R) :- 
    R is square(L1) + square(L2), L1 = max(X, Y), L2 = max(min(X, Y), Z).

然而，当我运行它时，它给出了以下错误：ERROR: is/2: Arguments are not sufficiently instantiated。我想我不仅没有得到 Prolog 的语法，而且还没有得到逻辑编程范式。那么，我怎样才能以良好的逻辑编程风格实现这个功能呢？

Answer 1

不幸的是，您正在使用的 max 函数是内置算术函数，并不像谓词那样运行，这可能会让您误以为您将以相同的方式编写谓词。

在 Prolog 中，您要编写的是谓词。 Predicate 没有 return 任何值，它只是持有或不持有（你可以认为它好像是 returned true 或 false）。您的谓词 square 是一个很好的例子，它 square(X,Y) 的真正含义是 'Y is square of X'。如果你问 Prolog 控制台 square(4, 16).，它会告诉你 true。如果你问square(4, 44)，它会告诉你false。那么你如何找出一些数字的平方根呢？你用自由（未知）变量 square(4,R). 问 Prolog 一个问题，然后 Prolog 会告诉你 R=16。那是逻辑编程的重要部分，你不解释 Prolog，如何计算平方，你只告诉 Prolog 什么是逻辑上的平方，然后你问 Prolog 问题，它会自己找到答案。

那么如果你尝试而不是

R is square(L1) + square(L2)

类似

square(L2, L2SQUARED), square(L1, L1SQUARED), ...

这将在 L1SQUARED

中给出 L1 的平方

然而，L1 不能是自由变量，Prolog 必须能够根据一些其他谓词 (...) 为它推导出一些值，以便它可以回答 square(L1, L1SQUARED)。想象一下问题 square(SOMETHING1, SOMETHING2)，两个参数都未知，答案会是什么？正确答案有无数个，例如 [2, 4] 或 [3, 9] 等

注意：是的，它可以与算术联机，但如果你想学习逻辑编程，请尝试更多 'logical programming' 之类的方法。在某些版本的 Prolog 中，您不会得到算术，但它们仍然有用...

Answer 2

我敢打赌，使用 'if-then-else' 结构。

squareTwoLargest(X, Y, Z, R) :- 
    ( X > Y -> A = X, B = Y ; A = Y, B = X ),
    R is A + max(B, Z).

需要两个临时变量。

Answer 3

要从三个（V1、V2 和 V3）中得到两个最大的数字，您可以按以下步骤进行：对列表 [V1,V2,V3] 排序并取最后两个列表项 [_,X,Y]，对它们进行平方和求和。

:- use_module(library(lists)).
:- use_module(library(clpfd)).

squareTwoLargest(V1,V2,V3, R) :- 
    Zs = [_,X,Y],
    chain(Zs, #=<),
    permutation([V1,V2,V3],Zs),
    R #= X*X + Y*Y.

示例查询：

?- squareTwoLargest(20,30,10, R).
R = 1300

更好的实施

以上代码基于"permutation sort"，这使得它在不止一种方式上效率低下。

如果 X、Y 和 Z 中有两个或多个相等，则目标 squareTwoLargest(X,Y,Z, R) 多次成功并给出冗余答案。以下两个查询显示了这一点：

?- squareTwoLargest(0,10,10, R).
R = 200 ;
R = 200 ;
false.

?- squareTwoLargest(10,10,10, R).
R = 200 ;
R = 200 ;
R = 200 ;
R = 200 ;
R = 200 ;
R = 200 ;
false.

我们可以使用大小为3的排序网络来剔除多余的答案。详情请看问题this answer ordering lists with constraint logic programming.

list_sorted__SN3([A0,A1,A2], [D0,D1,C2]) :-
    B1 #= min(A1,A2),   B2 #= max(A1,A2),
    C0 #= min(A0,B2),   C2 #= max(A0,B2),
    D0 #= min(C0,B1),   D1 #= max(C0,B1).

squareTwoLargest__SN(V1,V2,V3, R) :-
    list_sorted__SN3([V1,V2,V3],[_,X,Y]),
    R #= X*X + Y*Y.

考虑以下查询：

?- squareTwoLargest__SN(20,30,10, R).
R = 1300.                              % works like it did before

?- squareTwoLargest__SN(20,20,10, R).
R = 800.                               % succeeds deterministically

?- squareTwoLargest__SN(20,20,20, R).
R = 800.                               % succeeds deterministically

请注意，上面显示的极端情况的所有冗余答案都已删除。

Prolog：如何实现三个中两个最大数的平方和？

Prolog: How can I implement the sum of squares of two largest numbers out of three?

prolog

sicp

logic-programming

更好的实施