4

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

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

这段代码的问题是append调用processInput/3成本为 O(n)。我们怎样才能避免这种成本并且仍然让我们的谓词是尾递归的（因为我们可能会从标准输入中读取很多行）？

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

LinesSoFar1 = [ Line | LinesSoFar ],

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

4

2 回答 2

8

我不认为您提出的解决方案（添加列表元素，然后在最后反转列表）“hacky”。gusbro 的具有显式差异列表的解决方案也可以。我认为最优雅的方法是使用 DCG 表示法（差异列表的隐式接口），即使用描述行列表的 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)。

于 2011-06-08T17:42:49.403 回答
2

您可以使用半实例化结构来完成。检查此代码：

append_init(Marker-Marker).

append_end(L-[I|NMarker], I, L-NMarker).

append_finish(L-[], L).

您首先通过调用append_init(L)来“初始化”半实例化结构。然后，您可以通过调用append_end(L, Item, NewList)在列表末尾添加元素。添加完元素后，您调用append_finish(L, List)来获得最终的、完全实例化的列表。

例子：

example(NL):-
  append_init(L), 
  append_end(L, a, L1), 
  append_end(L1, b, L2), 
  append_end(L2, c, L3), 
  append_finish(L3, NL).

?- example(L).
L = [a, b, c].
于 2011-06-08T14:30:43.170 回答