使用Prolog读取记录列表并执行有关先前记录的持续计算 [英] Read a list of records and perform ongoing calculations about the previous records using Prolog

问题描述

这是一个游乐场示例，它受我曾经做过的真实任务(复杂得多)的启发.基本流程是从顺序文件中读取记录.一些记录包含要求检查以前的记录以计算值的命令.

This is a playground example inspired by a real task (much more complicated) that I once did. The basic flow is that there is the reading of records from a sequential file. Some of the records contain commands that require examining the previous records to calculate a value.

此解决方案不理想的是，它需要一个额外的列表，因此需要额外的重复存储. 在下面的代码中，该额外列表称为REMEMBER. 此示例具有一个简单的记录结构，仅包含一个数据值，因此复制REMEMBER列表中的所有内容都不是真正的问题. 但是，请假定实际任务涉及更为复杂的记录结构，因此非常不希望复制REMEMBER列表中的所有内容.

Undesirable about this solution is that it requires an extra list thus extra duplicate storage. That extra list is called REMEMBER in the following code. This example has a simple record structure just containing one data value so duplicating everything in the REMEMBER list is not a real issue. But please assume the real task involves a much more complicated record structure such that duplicating everything in the REMEMBER list is very undesirable.

我倾向于使用双向链表，但是根据此链接的讨论 Prolog中的双向链接列表 看来这不是Prolog的处理方式. 因此，我有兴趣了解Prolog的处事方式.

I am inclined to use a doubly linked list however per discussion at this link Doubly Linked List in Prolog it seems that is not the Prolog way to do things. Therefore I am interested to see what the Prolog way of doing things should be.

/*
A file contains sequential records.
There are two types of record.
A data record provides a data value.
An average record provides a count and is a request for an average of the last count data values.
The parse dcg below parses a list from the data file.
The report dcg uses that list to generate a report.

After parse the list looks like this:

[value=5.9,value=4.7,value=7.5,average=3,value=9.0,value=1.1,value=8.3,average=5,value=7.1,value=1.3,value=6.7,value=9.9,value=0.5,value=0.3,value=1.5,value=0.2,average=7,value=2.2,value=7.8,value=2.5,value=4.5,value=2.4,value=9.7,average=4,value=5.2,value=8.5,value=2.2,value=8.0,value=0.7].

An example report looks like this:

[[count=3,total=18.1,average=6.033333333333333],[count=5,total=30.599999999999998,average=6.12],[count=7,total=20.400000000000002,average=2.9142857142857146],[count=4,total=19.1,average=4.775]].
*/

:- use_module(library(dcg/basics)).
:- use_module(library(readutil)).
:- use_module(library(clpfd)).
:- use_module(library(clpr)).

dospy
:-
spy(report),
spy(average),
leash(-all).

:- initialization main.

report(LIST)
-->
% the report starts with nothing to REMEMBER.
report(LIST,[]).

report([value=VALUE|LIST],REMEMBER)
-->
% value in the LIST goes into REMEMBER.
report(LIST,[value=VALUE|REMEMBER]).

report([average=COUNT|LIST],REMEMBER)
-->
% request for average in the LIST.
average(REMEMBER,COUNT),
report(LIST,REMEMBER).

report([],_REMEMBER)
% the LIST is empty so the report is done.
--> [].

average(REMEMBER,COUNT)
-->
% the average starts at 0 then accumulates for COUNT values from REMEMBER.
average(REMEMBER,COUNT,0,0.0).

average([value=VALUE|REMEMBER],COUNT,AT,TOTAL)
-->
% found needed value in the REMEMBER.
clpfd( AT #\= COUNT ),
clpfd( AT_NEXT #= AT + 1 ),
clpr( TOTAL_NEXT = TOTAL + VALUE ),
average(REMEMBER,COUNT,AT_NEXT,TOTAL_NEXT).

average(_REMEMBER,COUNT,COUNT,TOTAL)
-->
% all of the needed value have been seen so calculate and add to report. 
clpr( AVERAGE = TOTAL / COUNT ),
[[count=COUNT,total=TOTAL,average=AVERAGE]].

% now the part that does the parse of the data file.

parse(LIST) --> parse(data,LIST).
parse(LIST) --> parse(average,LIST).
parse(LIST) --> parse(end,LIST).

parse(data,[value=FLOAT|LIST])
-->
"data", whites, float(FLOAT), blanks, !,
parse(LIST).

parse(average,[average=COUNT|LIST])
-->
"average", whites, integer(COUNT), blanks, !,
parse(LIST).

parse(end,[])
-->
[].

clpr( CLPR )
-->
{ clpr:{ CLPR } }.

clpfd( CLPFD )
-->
{ CLPFD }.

main :-
system:( read_file_to_codes("doubly_motivation_data.txt",CODES,[]) ),
prolog:( phrase(parse(LIST),CODES) ),
system:( writeq(LIST),writeln(.) ),
prolog:( phrase(report(LIST),REPORT) ),
system:( writeq(REPORT),writeln(.) ).

/* doubly_motivation_data.txt
data 5.9
data 4.7
data 7.5
average 3
data 9.0
data 1.1
data 8.3
average 5
data 7.1
data 1.3
data 6.7
data 9.9
data 0.5
data 0.3
data 1.5
data 0.2
average 7
data 2.2
data 7.8
data 2.5
data 4.5
data 2.4
data 9.7
average 4
data 5.2
data 8.5
data 2.2
data 8.0
data 0.7
*/

推荐答案

因此，对于初学者来说，我注意到您可以沿任一方向生成结果.换句话说，经典的"int列表"语法是这样的:

So, for starters, I noticed that you can build results in either direction. In other words, the classic "int list" grammar is something like this:

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

这是这样的:

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

但是您可以翻转它，以便它像下面这样向后解析列表:

But you can flip it around so it parses the list backwards like so:

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

这行得通，有点:

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

这个问题是将递归调用放在最前面，然后是可以匹配空列表的空白"之类的东西，这是导致堆栈爆炸的秘诀.但是，您还可以通过将先前"状态传递到DCG本身来向后解析内容:

The problem with this is that putting the recursive call at the front, followed by something like "blanks" that can match empty lists is a recipe for a stack explosion. But, you can also parse things backwards by passing the "previous" state through the DCG itself:

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] .

现在，我想我们可以很好地解决您的问题；我编写了解决方案，现在发现它与上面的@PauloMoura非常相似，但是无论如何这里都是这样:

Now, I think we can solve your problem nicely just from this; I wrote my solution and now see it is pretty similar to @PauloMoura's above, but here it is anyway:

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.

这似乎为您的示例提供了类似的输出:

This seems to give similar output to your example:

?- 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)]

现在，将其扩展到双向链接列表，让我们首先看看我们需要做些什么来以双向链接方式处理"int list"语法.与此类似，我们必须将前一个链接向前传递到递归调用中，但要使其比该链接差一点，我们需要在接收到的前一个变量中使用当前节点填充下一个"链接.但是因为该链接是第一次nil，所以我们必须有一些条件逻辑来忽略该链接.而且我想不出一个明智的空双链表，因此我将基本情况更改为[X]而不是[].这样就有点古怪了.

Now, expanding it to the doubly-linked list, let's first see what we would need to do to handle the "int list" grammar in a doubly-linked fashion. Much like this one, we have to pass a previous link forward into the recursive call, but making it a bit worse than this one, we need to fill in the "next" link in the previous variable we receive, with the current node. But because that link will be nil the first time, we have to have a bit of conditional logic to ignore that one. And I couldn't think of a sensible empty doubly-linked list, so I changed the base case to be [X] instead of []. So it gets a bit grotty.

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

请注意Cur = node(..., node(..., Cur), ...)中的自引用.这种统一实际上就是在上一个链接和该链接之间打结".试试吧:

Note the self-reference in Cur = node(..., node(..., Cur), ...). This unification is what "ties the knot" as it were, between the previous link and this link. Let's try it:

?- 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) 

有点难以理解，但基本上是9点到45点到23点等于1.我们从头到尾解析它，并用两个方向的指针结束.

A bit hard to read, but basically, 9 points to 45 points to 23 points to 1. We parsed it back-to-front and wound up with pointers in both directions.

这时剩下要做的是更改解析器以改为使用这些指针发出记录，并编写一个以这种方式工作的平均值器.我不能完全按照原位进行平均处理，所以我写了一个助手，从双向链表中给我最多N个":

What remains to be done at this point is to change the parser to emit records with these pointers instead, and write an averager that works this way. I couldn't quite get there doing the average in-place, so I wrote a helper to give me "up to N previous" from a doubly-linked list:

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

这是这样的:

?- 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] .

有了此实用程序，我们可以完成此操作:

With this utility in place, we can finish this out:

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.

总的来说，我很高兴能够完成这项工作，但是按照这种表述，您确实不需要双向链接列表中的下一个"指针，因此我倾向于只使用该列表上面的实现(或者如果我正在看Logtalk，也许是Paulo的实现).希望这可以说明如何使用双向链接列表来实现此目的，即使您的模型实际上并不需要它，但实际问题仍需要它时，却可以这样做.希望对您有帮助！

Overall, I'm pleased I was able to make this work, but in this formulation you really don't need the "next" pointers in your doubly-linked list, so I would be inclined to just go for the list implementation above (or perhaps Paulo's implementation if I were looking at Logtalk). Hopefully this illustrates how you could do this with doubly-linked lists, if your actual problem necessitates it despite your model not really needing it. Hope it helps!

这篇关于使用Prolog读取记录列表并执行有关先前记录的持续计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！