递归在 Prolog（关于列表）中的应用

Question

请问有人能帮我解释一下如何执行递归的Prolog函数吗？

append([],X,X). % base
append([X|Y],Z,[X|W]) :- append(Y,Z,W). %recursive

% base case
addup([], 0). % sum of the empty list of numbers is zero

% recursive case: if the base-case rule does not match, this one must:
addup([FirstNumber | RestOfList], Total) :-
    addup(RestOfList, TotalOfRest),   % add up the numbers in RestOfList
    Total is FirstNumber + TotalOfRest.

有人可以用英语或C/C++/Java之类的语言解释一下吗？我实际上更想看到像追加或反转这样的东西。我主要是在操作变量列表而不是整数。(我已经试过10次追加了..呃)。

- DJPlayer

Answer 1

append(A, B, R) 表示把 A 追加到 B 后得到结果 R。

基本情况：

append([], X, X).

如果A = []，并且B = X，则R = X = B：A空列表附加到其他列表B等于B。

递归情况

append([X | Y], Z, [X | W]) :- append(Y, Z, W).

如果A = [X | Y]是一个非空列表，要将其附加到B = Z中，如果W是Z附加到Y后的结果，则R = [X | W]。

另一种说法是：要将一个非空列表A附加到另一个列表B中，首先将A的尾部附加到B中，然后将A的头部添加到列表的前面。

- antonakos

---

这是在我看来最好的格式。我已经见过很多像这样的形式，只是没有针对递归翻译成英语。 递归版本总是从左到右读取吗？ 即“，=和”操作按顺序从左到右执行吗？（[x | y]，z，[x | w]）。但仅当append（y，z，w）成立时。 - DJPlayer

Answer 2

免费在线书籍“Learn Prolog Now”有一个专门介绍append执行步骤的部分： http://cs.union.edu/~striegnk/learn-prolog-now/html/node47.html#subsec.l6.defining.append

- Nick Main

---

这是我看过的最好的逐步解答，我查阅了几本书。在查看跟踪后，现在更加合理易懂了。 - DJPlayer

Answer 3

你想用C++看吗？

int const a[] = {1,2,3,4,5};
size_t const N = sizeof(a) / sizeof(int);

void addup(size_t depth, int &total)
{
    if (depth == N)   // base case; sum of no numbers is zero
        total = 0;
    else {            // recursive case
        int first_number = a[depth];
        size_t rest_of_list = depth+1;
        int total_rest;
        addup(rest_of_list, total_rest);
        total = first_number + total_rest;
    }
}

我必须承认这是非常丑陋的C++代码，但它是Prolog程序的直接翻译，只不过使用数组和深度计数器来模拟列表。

- Fred Foo

Answer 4

在Prolog中，递归与任何其他语言中的递归几乎完全相同。Prolog的诀窍在于：

• 每个变量都是本地的，并且
• 一旦统一，变量就不再是变量。它们永远不会改变值。

这意味着您经常需要构建我称之为“工作”谓词的东西，以执行所需的实际工作并携带一个或多个变量作为工作存储。以下是对sum/2的实现，用于对整数列表求和：

% sum/2
sum( [] , 0 ).
sum( [X|Xs] , Total) :-
  sum(Xs,X,Total).

% sum/3 (worker predicate)
sum( [], Total, Total ).
sum( [X|Xs] , Subtotal , Total ) :-
  NewSubTotal is Subtotal + X ,
  sum( Xs , NewSubTotal , Total ).

这里是一个使用 ANSI C 实现的代码，与上面的 Prolog 代码非常相似：

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
// linked list structure
typedef struct listnode
{
  int              value ;
  struct listnode *next  ;
} LISTNODE ;

// core recursive worker function
int sum_core( int subtotal , LISTNODE *list )
{
  LISTNODE *head ;
  LISTNODE *tail ;
  int       list_item ;

  if ( list == NULL ) return subtotal ;

  head      = list        ;
  tail      = list->next  ;
  list_item = head->value ;

  return sum_core( subtotal + head->value , tail ) ;

}

// external interface
int sum( LISTNODE *list )
{
  LISTNODE *head      ;
  LISTNODE *tail      ;
  int       list_item ;

  if ( list == NULL ) return 0 ;

  head      = list        ;
  tail      = list->next  ;
  list_item = head->value ;

  return sum_core( list->value , tail ) ;

}

int main ( int argc , char * argv[] )
{
  LISTNODE *list ;
  int       total ;

  list                   = malloc(sizeof(LISTNODE)) ; list->value             = 1 ;
  list->next             = malloc(sizeof(LISTNODE)) ; list->next->value       = 2 ;
  list->next->next       = malloc(sizeof(LISTNODE)) ; list->next->next->value = 3 ;
  list->next->next->next = NULL ;

  total = sum( list ) ;

  return ;
}

- Nicholas Carey