Lire une liste d'enregistrements et effectuer des calculs en cours sur les enregistrements précédents à l'aide de Prolog

Suit une solution Logtalk + SWI-Prolog, qui ne nécessite aucune matérialisation de listes à double lien. Seule une pile, implémentée de manière triviale à l'aide d'une liste, est requise:

compute_record(Count, Stack, r(Count,Total,Average)) :-
    compute_record(0, Count, Stack, 0, Total),
    Average is Total / Count.

compute_record(Count, Count, _, Total, Total) :-
    !.
compute_record(Count0, Count, [Value| Stack], Total0, Total) :-
    Count1 is Count0 + 1,
    Total1 is Total0 + Value,
    compute_record(Count1, Count, Stack, Total1, Total).

Exemple d'appel utilisant le fichier de données dans la question:

?- {library(types_loader), library(reader_loader), reports}.
...

?- reports::process('doubly_motivation_data.txt', Report).
Report = [r(3, 18.1, 6.033333333333334), r(5, 30.599999999999998, 6.119999999999999), r(7, 20.400000000000002, 2.9142857142857146), r(4, 19.1, 4.775)] .

Comme vous remarqué, j'utilise une représentation plus sensée pour le rapport qu'une liste de listes. Une solution un peu plus efficace peut être codée en combinant les appels take / 3 et sum / 2 dans un prédicat personnalisé en évitant le préfixe de pile de longueur Count code> étant parcouru deux fois et créant une liste temporaire de valeurs. Par exemple:

------------ reports.lgt ------------
% load the required modules
:- use_module(library(dcg/basics), []).

% ensure desired interpretation of double-quoted text
:- set_prolog_flag(double_quotes, codes).

% optimize the generated code
:- set_logtalk_flag(optimize, on). 


:- object(reports).

    :- public(process/2).

    :- uses(list, [take/3]).
    :- uses(numberlist, [sum/2]).
    :- uses(reader, [file_to_codes/2]).

    :- use_module(dcg_basics, [blanks//0, whites//0, integer//1, float//1]).

    process(File, Report) :-
        file_to_codes(File, Codes),
        phrase(report(Report), Codes).

    report(Report) -->
        data(Value),
        report(Report, [Value]).

    report([], _) -->
        eos.
    report([Record| Records], Stack) -->
        average(Count),
        {compute_record(Count, Stack, Record)},
        report(Records, Stack).
    report(Records, Stack) -->
        data(Value),
        report(Records, [Value| Stack]).

    average(Count) -->
        "average", whites, integer(Count), blanks.

    data(Value) -->
        "data", whites, float(Value), blanks.

    compute_record(Count, Stack, r(Count,Total,Average)) :-
        take(Count, Stack, Values),
        sum(Values, Total),
        Average is Total / Count.

:- end_object.
-------------------------------------

À partir de l'exemple de fichier de données, il semble que le fichier puisse se terminer par une demande de calcul de la moyenne de toutes les valeurs dans fichier. Ainsi, le report // 2 non-terminal doit conserver toute la pile jusqu'à ce que tout le fichier de données soit traité.

J'essaierais d'exploiter DCG semicontext, comme expliqué sur la page metalevel.at . Un exemple OT, je pense qu'il est facile à saisir, est cette réponse (résoudre un casse-tête semblable à un zèbre dans un DCG). XXX

Les astuces accèdent au partage de contexte 'par magie':

?- cc_main.
ave(6.033333333333334)=sum(18.1)/3
ave(6.119999999999999)=sum(30.599999999999998)/5
ave(2.9142857142857146)=sum(20.400000000000002)/7
ave(4.775)=sum(19.1)/4
true .

le DCG doit être appelé de cette manière, en fournissant l'état initial pertinent:

cc_main :-
    %system:( read_file_to_codes("doubly_motivation_data.txt",CODES,[]) ),
    codes(CODES),
    tokenize_atom(CODES, Tks),
    phrase(cc_report([],Rep), Tks),
    maplist(writeln, Rep).

cc_report(_,[]) --> [].
cc_report(R,Re) -->
    [data,N],
    cc_report([N|R],Re).
cc_report(R,[ave(Ave)=sum(Sum)/C|Re]) -->
    [average,C],
    {aggregate_all((sum(V),count),(
         % no need for doubly linked lists, just peek from stack...
         nth1(I,R,V),I=<C
       ),(Sum,Count)),Ave is Sum/Count},
    cc_report(R,Re).

Maintenant, pour votre cas applicatif, c'est presque inutile (vous avez déjà résolu, juste de manière verbeuse). Pour commencer, je ne comprends pas pourquoi vous effectuez un algorithme à 2 passes. Considérez à quel point le code pourrait être concis, qui donne les mêmes résultats que ce que vous avez publié (juste affiché différemment), en un seul passage, en utilisant la bibliothèque (agrégat) pour effectuer de l'arithmétique. BTW, pourquoi clpfd, clpr peuvent également compter ... êtes-vous vraiment intéressé par les services de CLP pour une tâche aussi simple?

bagels(Sol):- Sol =
    [[brad,_,_,_,_],
     [walt,_,_,_,_],
    ...],
  phrase((hint1, hint2, hint3, hint4, hint5, hint6), [state(Sol)], _).

donne:

kind(P, K) --> state([P, K, _, _, _]).
topping(P, T) --> state([P, _, T, _, _]).
...

Quoi qu'il en soit, les addons swipl offrent du matériel utile. Voir par exemple edgc , une extension pour gérer beaucoup de plusieurs accumulateurs en effectuant plusieurs visites de l'arbre de syntaxe concret de Acquarius Prolog compilateur - développé dans les années 90.

Donc, pour commencer, j'ai remarqué que vous pouvez générer des résultats dans les deux sens. En d'autres termes, la grammaire classique "liste int" est quelque chose comme ceci:

commandsdl(Report) --> commandsdl(nil, _, Report).
commandsdl(Prev, Prev, []) --> [].
commandsdl(Prev, Last, Report) -->
    record(data(V)),
    blanks,
    {
     Prev = node(PV, PP, Cur)
     ->
         Cur = node(V, node(PV, PP, Cur), _)
     ;
         Cur = node(V, Prev, _)
    },
    commandsdl(Cur, Last, Report).
commandsdl(Prev, Last, [report(Count, Total, Avg)|Report]) -->
    record(average(N)),
    blanks,
    {
       calculate_average_dl(N, Prev, Count, Total, Avg)
    },
    commandsdl(Prev, Last, Report).

calculate_average_dl(N, Prev, Count, Total, Avg) :-
    take_upto(N, Prev, L),
    length(L, Count),
    sumlist(L, Total),
    Avg is Total / Count.

Cela fonctionne comme ceci:

?- phrase(dlist(X), "1 2 3 4 5 6 7 8 9 10"), take_upto(5, X, L).
X = node(10, _S2, nil), % where
   ... [trimmed]
L = [6, 7, 8, 9, 10] .


?- phrase(dlist(X), "1 2 3 4 5 6 7"), take_upto(15, X, L).
X = node(7, _S2, nil), % where
   ... [trimmed]
L = [1, 2, 3, 4, 5, 6, 7] .

Mais vous pouvez retournez-le pour qu'il analyse la liste à l'envers comme ceci:

take_upto(N, DL, Result) :- take_upto(N, 0, DL, [], Result).
take_upto(N, N, _, Result, Result).
take_upto(_, _, nil, Result, Result).
take_upto(N, I, node(V, Prev, _), Rest, Result) :-
    I < N,
    succ(I, I1),
    take_upto(N, I1, Prev, [V|Rest], Result).

Cela fonctionne, ish:

?- phrase(dlist(L), "1 23 45 9").
L = node(9, _S2, nil), % where
    _S1 = node(1, nil, node(23, _S1, _S2)),
    _S2 = node(45, node(23, _S1, _S2), _71658) 

Le problème avec c'est que mettre l'appel récursif au premier plan, suivi de quelque chose comme des "blancs" qui peuvent correspondre à des listes vides est une recette pour une explosion de pile. Mais, vous pouvez également analyser les choses à l'envers en passant l'état "précédent" via le DCG lui-même:

% entry point (nil meaning there is no previous)
dlist(X) --> dlist(nil, X).

% base case: last integer
dlist(Prev, node(X, Prev, nil)) --> integer(X).
dlist(Prev, Last) -->
    integer(X), whites,
    {
     Prev = node(PV, PP, Cur)
     -> 
         Cur = node(X, node(PV, PP, Cur), _)
     ;
         Cur = node(X, Prev, _)
    },
    dlist(Cur, Last).

Maintenant, je pense que nous pouvons résoudre votre problème simplement à partir de cela; J'ai écrit ma solution et je vois maintenant qu'elle est assez similaire à celle de @ PauloMoura ci-dessus, mais la voici quand même:

?- phrase_from_file(commands(C), 'mdata.txt'), write_canonical(C).
[report(3,18.1,6.033333333333334),
 report(5,30.599999999999998,6.119999999999999),
 report(7,20.400000000000002,2.9142857142857146),
 report(4,19.1,4.775)]

Cela semble donner un résultat similaire à votre exemple: p >

commands(Report) --> record(data(V)), blanks, commands([V], _, Report).

commands(Prev, Prev, []) --> [].
commands(Prev, Last, Report) -->
    record(data(V)),
    blanks,
    commands([V|Prev], Last, Report).
commands(Prev, Last, [report(Count, Total, Avg)|Report]) -->
    record(average(N)),
    blanks,
    { calculate_average(N, Prev, Count, Total, Avg) },
    commands(Prev, Last, Report).

calculate_average(N, Prev, Count, Total, Avg) :-
    length(L, N),
    append(L, _, Prev),
    sumlist(L, Total),
    Avg is Total / N,
    Count = N.

Maintenant, en l'étendant à la liste doublement liée, voyons d'abord ce que nous aurions besoin de faire pour gérer la grammaire "int list" de manière doublement liée. Tout comme celui-ci, nous devons transmettre un lien précédent à l'appel récursif, mais le rendant un peu pire que celui-ci, nous devons remplir le lien "suivant" dans la variable précédente que nous recevons, avec le nœud actuel. Mais comme ce lien sera nul la première fois, nous devons avoir un peu de logique conditionnelle pour ignorer celui-là. Et je ne pouvais pas penser à une liste doublement liée vide sensée, alors j'ai changé le cas de base pour être [X] au lieu de [] . Donc ça devient un peu sale.

rintlist(L) --> rintlist([], L).
rintlist(Prev, Prev) --> [].
rintlist(Prev, Last) --> integer(X), whites, rintlist([X|Prev], Last).

?- phrase(rintlist(X), "1 23 45 9").
X = [9, 45, 23, 1] .

Notez l'auto-référence dans Cur = node (..., node (..., Cur), .. .) . Cette unification est en quelque sorte ce qui "fait le nœud" entre le lien précédent et ce lien. Essayons-le:

?- phrase(rintlist(X), "1 23 45 9").
X = [9, 45, 23, 1] 

Un peu difficile à lire, mais en gros, 9 points à 45 points à 23 points à 1. Nous l'avons analysé dos à front et avons terminé avec des pointeurs dans les deux sens.

Ce qui reste à faire à ce stade est de changer l'analyseur pour émettre des enregistrements avec ces pointeurs à la place, et d'écrire un moyenneur qui fonctionne de cette façon. Je ne pouvais pas vraiment y arriver en faisant la moyenne sur place, alors j'ai écrit une aide pour me donner "jusqu'à N précédents" à partir d'une liste à double lien:

rintlist([]) --> [].
rintlist([X|Xs]) --> rintlist(Xs), whites, integer(X).

Cela fonctionne comme ceci:

?- phrase(intlist(X), "1 23 45 9").
X = [1, 23, 45, 9] ;

Avec cet utilitaire en place, nous pouvons terminer ceci:

intlist([]) --> [].
intlist([X|Xs]) --> integer(X), whites, intlist(Xs).

Dans l'ensemble, je Je suis ravi d'avoir pu faire ce travail, mais dans cette formulation, vous n'avez vraiment pas besoin des pointeurs "suivant" dans votre liste à double lien, donc je serais enclin à simplement opter pour l'implémentation de la liste ci-dessus mise en œuvre si je regardais Logtalk). J'espère que cela illustre comment vous pouvez faire cela avec des listes à double lien, si votre problème réel l'exige alors que votre modèle n'en a pas vraiment besoin. J'espère que ça aide!