避免 Prolog 中 append/3 的线性成本 [英] Avoid linear cost of append/3 in Prolog

问题描述

让我们假设我们正在从标准输入中读取并构建一个包含所有已读取行的列表.最后，我们需要显示这些行，以逗号分隔.

Let's assume that we're reading from standard input and building a list of all the lines that have been read. In the end, we need to display those lines, separated by commas.

go:-
    prompt(_, ''),
    processInput([ ], Lines),
    findall(_, (member(L, Lines), write(L), write(',')), _),
    nl.

processInput(LinesSoFar, Lines):-
    read_line_to_codes(current_input, Codes),
    processInput(Codes, LinesSoFar, Lines).

processInput(Codes, LinesSoFar, Lines):-
    ( Codes \= end_of_file
    ->
        atom_codes(Line, Codes),
        append(LinesSoFar, [ Line ], LinesSoFar1),  % <---- append/3 - O(n)
        processInput(LinesSoFar1, Lines)
    ;
        Lines = LinesSoFar ).

此代码的问题在于 processInput/3 中的 append 调用花费了我们 O(n).我们怎样才能避免这种成本&仍然让我们的谓词是尾递归的(因为我们可能会从标准输入中读取很多行)?

The issue w/ this code is that the append call in processInput/3 costs us O(n). How can we avoid this cost & still let our predicate be tail-recursive (because we may be reading a lot of lines from standard input)?

我突然想到我们可以用以下内容替换 append.

It occurred to me that we could replace the append with the following.

LinesSoFar1 = [ Line | LinesSoFar ],

我们可以在显示之前反转列表.但这似乎很hacky.有没有更好的办法?

And we could reverse the list before displaying it. But that seems hacky. Is there a better way?

推荐答案

我不认为您提出的解决方案(在列表元素之前添加，然后在末尾反转列表)hacky".gusbro 的带有显式差异列表的解决方案也可以.我认为最优雅的方法是使用 DCG 符号(差异列表的隐式接口)，即使用描述行列表的 DCG:

I do not consider the solution you propose (prepending list elements, then reversing the list at the end) "hacky". gusbro's solution with explicit difference lists is OK as well. I think the most elegant way is to use DCG notation (an implicit interface to difference lists), i.e., use a DCG that describes the list of lines:

read_lines -->
        { read_line_to_codes(current_input, Codes) },
        (   { Codes == end_of_file } -> []
        ;   { atom_codes(Line, Codes) },
            [Line],
            read_lines
        ).

用法:phrase(read_lines, Lines).

这篇关于避免 Prolog 中 append/3 的线性成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！