prolog - 避免Prolog中append/3的线性成本

Question

假设我们正在从标准输入读取并构建已读取的所有行的列表。最后，我们需要显示这些行，并用逗号分隔。

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)。我们如何避免这种成本并仍然让我们的谓词是尾递归的(因为我们可能从标准输入读取很多行)？

我想到我们可以用以下内容替换append。

LinesSoFar1 = [ Line | LinesSoFar ],

我们可以在显示列表之前反转列表。但这似乎很古怪。有更好的办法吗？

Answer 1

我不认为您提出的解决方案(预先添加列表元素，然后在末尾反转列表)“hacky”。 gusbro 具有显式差异列表的解决方案也可以。我认为最优雅的方法是使用 DCG 表示法(差异列表的隐式接口(interface))，即使用描述行列表的 DCG:

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

用法:phrase(read_lines, Lines)。