la récursivité en prolog (sur les listes)

quelqu'un peut s'il vous plaît aidez-moi seulement w/notions de base sur la réalisation récursive prologue de fonctions..

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.

Quelqu'un peut m'expliquer ce soit en anglais ou en C/C++/Java que ce soit.. comment les étapes. En fait je préfère voir ce genre de choses à ajouter ou inverse.. je suis la plupart du temps que manipuler des listes de variables au lieu des nombres entiers.. (j'ai essayé de travailler grâce à ajouter comme 10 fois.. pouah).

OriginalL'auteur DJPlayer | 2011-04-28

prolog

3

En ligne gratuit livre "Apprendre Prolog Maintenant" a une section dédiée à expliquer les étapes que append effectue:

http://cs.union.edu/~striegnk/apprendre-prologue-maintenant/html/node47.html#subsec.l6.la définition.ajouter

c'est la meilleure étape par étape de la réponse, je l'ai vu.. et j'ai regardé à travers plusieurs livres. Fait beaucoup plus de sens maintenant, après avoir regardé une trace

OriginalL'auteur Nick Main
5

append(A, B, R) signifie que R est le résultat de l'ajout de A à B.

Le cas de base
```
append([], X, X).
```
dit que si A = [] et B = X puis R = X = B: une liste vide A ajouté à certains autres liste B est égal à B.

Le récursive cas
```
append([X | Y], Z, [X | W]) :- append(Y, Z, W).
```
dit que si A = [X | Y] est un non-vide de la liste pour ajouter à B = Z, et si W est Y ajouté à Z, puis R = [X | W].

Une autre façon de le dire est: pour l'ajout d'un non-vide de la liste A à une autre liste B, tout d'abord ajouter la queue de A à B puis ajouter la tête de A à l'avant de la liste.

ce qui suit est le meilleur format de l'OMI. J'ai vu de nombreuses aiment ceci tout simplement pas traduit de l'anglais pour la récursivité. est une version récursive toujours lire de gauche à droite.. aka ", = " et par conséquent, l'opération à effectuer dans l'ordre de gauche à droite.. ([x|y], z, [x|l]). mais seulement si append(y,z,w) est titulaire.

OriginalL'auteur antonakos

Vous voulez le voir en 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;
    }
}

Je vais immédiatement admettre que c'est horridly laid C++, mais c'est la traduction directe du Prologue de programme, sauf que les listes sont simulées à l'aide de tableaux et d'une profondeur de comptoir.

OriginalL'auteur Fred Foo

Récursivité dans prolog est à peu près identique à la récursivité dans toute autre langue. Le truc avec prolog est que

chaque variable est locale, et,
la fois unifiée, variables cessent d'être des variables. Ils ne peuvent jamais changer la valeur.

Cela signifie que vous aurez souvent besoin de construire ce que je vais appeler "travailleur" prédicats qui ne sont en fait que le travail requis et transporter 1 ou plusieurs variables qui agissent en tant que mémoire de travail. Voici une implémentation de la somme/2 à la somme d'une liste d'entiers:

% 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 ).

Voici une implémentation en C ANSI que reflète étroitement les ci-dessus prologue code:

#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 ;
}

OriginalL'auteur Nicholas Carey

Vous devez vous connecter pour publier un commentaire.