Prolog语言的尺寸程序

本文介绍了Prolog语言的尺寸程序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我对Prolog并不陌生，就递归算法而言并没有那么出色，因此我对以下两个子句感到困惑:

I am new to Prolog and am not that great when it comes to recursive algorithms as is, thus I am confused with the following two clauses:

size([], 0).
size([H|T], N) :- size(T, N1), N is N1+1.

我在寻找以下问题时遇到了麻烦:

I am having trouble tracing this problem for:

?- size([a,b,c,d], N).

这将与第二个子句统一形成:

This will unify with the second clause to form:

size([a,b,c,d], N) :- size([b,c,d], N1), N is N1+1.

但是我对N是N1+1感到困惑，因为这些变量从未统一.这些变量取什么值?

But I am confused with the N is N1+1 as these variables are never unified. What values do these variables take?

任何有关此问题的帮助或对该算法的简单了解，将不胜感激.

Any help regarding this question, or a simple trace of this algorithm, would be greatly appreciated.

推荐答案

我认为您的意思是它们从未实例化，即它们从未获得价值.统一两个变量可以实例化它们，但这不是必需的.例如，您可以在prolog REPL中运行它:

I think you mean that they are never instantiated i.e. they never get a value. Unifying two variables can instantiated them but it's not necessary. For example you could run this in a prolog REPL:

?- N = N1.
N = N1.

，而N和N1没有值(尚未)，它们是统一的；如果稍后再实例化N1，则N也将使用相同的值实例化.另一个不那么琐碎的示例:

while N and N1 have no value (yet), they are unified; if N1 gets instantiated later, N will be instantiated with the same value as well. Another, less trivial, example:

?- [H|T] = L, L = [1|M], writeln(H).
1
H = 1,
T = M,
L = [1|M].

但是，确实N从未与N1+1统一！ is将评估N1+1，并且值将与N统一.在内部size([b,c,d],N1)求值后，将发生此情况，因此N1变量将被实例化.

However, it is true that N is never unified with N1+1! is will evaluate N1+1 and that value will be unified with N. This will happen after the inner size([b,c,d],N1) has been evaluated so the N1 variable will have been instantiated.

本质上，执行将是这样的:

Essentially, the execution will be like this:

size([a,b,c,d],N).
          size([b,c,d],N1)
               size([c,d],N1)
                   size([d],N1)
                        size([],0)
                        N is 0+1.
                   N is 1+1.
               N is 2+1.
          N is 3+1.

这有点效率低下，因为我们需要将所有函数调用都保留在内存中；调查尾递归和累加器以解决此问题.

Which is a bit inefficient as we need to keep all the function calls in memory; look into tail-recursion and accumulators to fix this.

还请注意，仅因为is将要计算表达式而需要实例化N1.您可以这样写:

Also note that N1 needs to be instantiated only because is is going to evaluate the expression. You could write something like this:

size([],0).
size([_|T], 1+ N1):-size(T,N1).

，如果您叫它:

?- size([1,2],N).
N = 0+1+1.

好玩，不是吗?您可能需要评估最后一个N，例如称为size([1,2],N), Result is N.但是，一个问题是，我们在内存中保留了一个0+1+1+1+1+......链，该链可以很快变得很大.因此，最好将这种技巧用于不会增长的事情，例如表达式模板.

Fun, isn't it? You might want to evaluate the last N, e.g. call it as size([1,2],N), Result is N. However, one problem is that we keep a chain of 0+1+1+1+1+...... in memory which can get big very fast. So it's best to use this trick for things that are not going to grow, e.g. expression templates.

这篇关于Prolog语言的尺寸程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

n1