Liste de Longueur en Prolog

Je suis débutant dans le Prologue de la programmation.
J'ai écrit ce programme pour calculer la longueur d'une liste. Pourquoi est ci-dessous le programme de mal?

length(0, []).
length(L+l, H|T) :- length(L, T).

J'ai écrit ci-dessous le programme et qu'il fonctionne correctement.

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

quand j'ai changé l'ordre, j'ai eu une erreur. Pourquoi?

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

OriginalL'auteur Fery | 2013-10-07

  1. 6

    ce code

    length_1(0,[]).
length_1(L+1, [H|T]) :- length_1(L,T).

    œuvres (veuillez noter que l'ajoutés entre crochets), mais de façon inattendue.
    Il va construire une arborescence d'expression, qui pourrait être évaluée plus tard:

    ?- length_1(X, [1,2,3]), L is X.
X = 0+1+1+1,
L = 3.

    Dans votre réécrit le code (deuxième version), vous obtenez un message d'erreur parce que N1 n'est pas encore instanciée au moment de l'appel est/2.

    OriginalL'auteur CapelliC

  2. 5

    Vous devez utiliser un accumulateur. Alors que vous pourriez faire quelque chose comme ceci:

    list_length([]     , 0 ).
list_length([_|Xs] , L ) :- list_length(Xs,N) , L is N+1 .

    qui répète tout le chemin jusqu'à la fin de la liste et puis, comme chaque invocation de retours, d'en ajouter un à la longueur, jusqu'à ce qu'il obtient en retour vers le haut niveau avec le résultat correct.

    Le problème avec cette approche est que chaque récursion pousse une nouvelle trame de pile sur la pile. Cela signifie que vous aurez [finalement] exécutez hors de la pile de l'espace donné une assez longue liste.

    Au lieu de cela, utilisez une queue-récursive intermédiaire, comme ceci:

    list_length(Xs,L) :- list_length(Xs,0,L) .

list_length( []     , L , L ) .
list_length( [_|Xs] , T , L ) :-
  T1 is T+1 ,
  list_length(Xs,T1,L)
  .

    Ce code graines d'un travailleur prédicat qui comporte un accumulateur, ensemencés avec des 0. Sur chaque récursion il crée un nouvel accumulateur dont la valeur est la valeur actuelle + 1. Lorsque la fin de la liste est atteinte, la valeur de l'accumulateur est unifié avec le résultat souhaité.

    Le prologue du moteur est assez intelligent (TRO/Récursion sur la Queue de l'Optimisation) pour voir qu'il peut réutiliser le cadre de la pile à chaque appel (puisqu'aucun des habitants de la région sont utilisés après l'appel récursif), donc parfaitement de conversion de la récursivité dans l'itération.

    OriginalL'auteur Nicholas Carey

  3. 4

    Comme évoqué dans Carlo réponse, L+1 est un terme Prolog avec deux arguments, L et 1, dont le foncteur est +. Prologue n'est pas un langage fonctionnel, de sorte que vous ne pouvez pas le type de L+1 et attendre qu'il soit évalué à la somme. Essayez de suivre Carlo de la suggestion et de l'utilisation de la is/2 prédicat de la force de l'arithmétique de l'évaluation. Par exemple, l'appel de l'objectif X is 3 + 4 permettra d'évaluer l'opérande de droite et de tenter d'unifier le résultat avec l'opérande de gauche. Si l'opérande de gauche, X, est une variable, il sera unifié avec 7. À noter également que, dans le Prologue, les variables sont d'affectation unique (mais peut être encore plus instancié si le mandat jusqu'à son terme inclut des variables, cependant). I. e. vous ne pouvez attribuer un terme à une variable à la fois. Cette cession est annulée lorsque vous revenir sur l'objectif de faire de la cession.

    OriginalL'auteur Paulo Moura

  4. 2
    len([], LenResult):-
    LenResult is 0.

len([X|Y], LenResult):-
    len(Y, L),
    LenResult is L + 1.
    Bien que ce code peut répondre à la question, en fournissant plus de contexte sur pourquoi et/ou comment il répond à la question permettrait d'améliorer de manière significative sa valeur à long terme. Veuillez modifier votre réponse à ajouter quelques explications.

    OriginalL'auteur garciparedes