Избегайте линейной стоимости append / 3 в Прологе - PullRequest
Новая
       5

Избегайте линейной стоимости append / 3 в Прологе

3 голосов
/ 08 июня 2011

Давайте предположим, что мы читаем из стандартного ввода и строим список всех прочитанных строк.В конце нам нужно отобразить эти строки, разделенные запятыми. 

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

И мы могли бы перевернуть список перед его отображением.Но это кажется вздорным.Есть ли лучший способ?

Ответы [ 2 ]

7 голосов
/ 08 июня 2011

Я не считаю решение, которое вы предлагаете (добавление элементов списка, затем изменение списка в конце) "хакерским". Решение 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).

2 голосов
/ 08 июня 2011

Вы можете сделать это, используя полу-экземплярную структуру. Проверьте этот код: 

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