Geek asks and answers

Avoid linear append / 3 cost in Prolog

Suppose we read from standard input and create a list of all the lines that have been read. At the end, we should display these 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 ).

The problem with this code is that the call appendto processInput/3us is O (n). How can we avoid this cost and allow our predicate to be tail-recursive (because we can read many lines from standard input)?

It occurred to me that we can replace the appendfollowing.

LinesSoFar1 = [ Line | LinesSoFar ],

And we could flip the list before displaying it. But it seems hacked. Is there a better way?

+3
source share
2 answers

( , ) "". 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).

+7

, . :

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

More articles:


All Articles