Измените список переменных в соответствии с другим списком, содержащим индекс и атомы в прологе

Question

У меня есть список переменных E и список L, и я хочу предикат, который работает следующим образом:

E=[A,B,C,D]
L=[(1,b),(3,m)]
solve(E,L).
E=[b,B,m,D]

В основном solve() должен проходить по списку L и измените E, используя (a,b), чтобы объединить переменную с индексом a с атомом B. Есть какой-либо способ сделать это?

Answer 1

Значение предиката solve/2 (с плохим именем) выглядит примерно так: «для каждой пары (Index, Element) Index -й элемент списка ввода равен Element». Скорее всего, вы используете реализацию Prolog, в которой уже есть предикат, называемый чем-то вроде nth1/3, который выражает "Index -й элемент List равен Element". Например, в SWI-Prolog:

?- List = [A, B, C, D], nth1(3, List, this_is_the_third_element).
List = [A, B, this_is_the_third_element, D],
C = this_is_the_third_element.

Таким образом, альтернативная реализация вашего предиката просто вызывает nth1/3 для каждой из ваших (Index, Element) пар:

solve(_List, []).
solve(List, [(Index, Elem) | Pairs]) :-
    nth1(Index, List, Elem),
    solve(List, Pairs).

И с этим вы закончите:

?- E = [A, B, C, D], L = [(1, b), (3, m)], solve(E, L).
E = [b, B, m, D],
A = b,
C = m,
L = [(1, b),  (3, m)] ;
false.

Обратите внимание, что это простое решение, но оно имеет квадратичную c сложность в длине списка ввода: nth1/3, возможно, придется посетить весь N-элементный список N раз. В маловероятном случае, когда вам нужен этот предикат для критически важной части какой-то более крупной программы, рассмотрите более оптимизированное решение, набросанное в другом ответе.

Answer 2

Есть ли способ сделать это?

Конечно. И, как говорится в Perl: «Есть несколько способов сделать это».

Пара проблем:

Не используйте (1,b). Вместо этого используйте идиоматиз c -(1,b), который записывается как 1-b (пара). Это дает вам список пар: L=[1-b,3-m]. Есть библиотека, специально работающая с такими парами: https://www.swi-prolog.org/pldoc/man?section=pairs - в качестве альтернативы вы можете использовать реальные карты, реализованные с помощью деревьев AVL: https://www.swi-prolog.org/pldoc/man?section=assoc

Теперь вам просто нужно

1. отсортировать список пар, возможно, используя сортировку ключей: https://www.swi-prolog.org/pldoc/doc_for?object=sort / 2 или https://www.swi-prolog.org/pldoc/doc_for?object=sort / 4
2. Go по списку слева направо, сохраняя текущий индекс и выполняя замену, когда нажимается следующий ключ в вашем отсортированном списке, или просто сохраняя существующий термин из списка в противном случае. Результат помещается в переменную-накопитель в качестве заголовка списка.
3. Готово! Специальная обработка за пределами индексов et c. быть подходящим образом обработанным путем броска или неудачи.

Как go просмотреть отсортированный список пар (я не проверял это!):

% case of Index hit:

go_through([Index-Value|Rest],Index,InList,OutList) :-
   InList  = [I|Rest],
   OutList = [Value|More],
   succ(Index,NextIndex),
   go_through(Rest,NextIndex,Rest,More).

% case of Index miss:

go_through([NotYetIndex-Value|Rest],Index,InList,OutList) :-   
   NotYetIndex > Index,  % that should be the case
   InList  = [I|Rest],
   OutList = [I|More],
   succ(Index,NextIndex),
   go_through(Rest,NextIndex,Rest,More).

go_through([],_,L,L). % DONE

В качестве альтернативы вы может написать replace0, который заменяет по индексу в списке, и go через список L.

Приложение: рабочий код с использованием go_through

На самом деле содержит несколько тонкостей

another_vectorial_replace1(ListIn,ReplacePairs,ListOut) :-
   maplist([_,_]>>true,ListIn,ListOut),               % Bonus code: This "makes sure" (i.e. fails if not) 
                                                      % that ListIn and ListOut are the same length
   maplist([(A,B),A-B]>>true,ReplacePairs,RealPairs), % Transform all (1,b) into [1,b]
   maplist([K-_]>>integer(K),RealPairs),              % Make sure the RealPairs all have integers on first place   
   keysort(RealPairs,RealPairsSorted),                % Sorting by key, which are integers; dups are not removed!
   debug(topic,"ListIn: ~q",[ListIn]),
   debug(topic,"RealPairsSorted: ~q",[RealPairsSorted]),
   go_through(RealPairsSorted,1,ListIn,ListOut),
   debug(topic,"ListOut: ~q",[ListOut]).

% Case of Index hit, CurIndex is found in the first "Replacement Pair"

go_through([CurIndex-Value|RestPairs],CurIndex,ListIn,ListOut) :-
   !, % Commit to choice
   ListIn  = [_|Rest],
   ListOut = [Value|More],
   succ(CurIndex,NextIndex),
   go_through(RestPairs,NextIndex,Rest,More).

% Case of Index miss:

go_through([NotYetIndex-V|RestPairs],CurIndex,ListIn,ListOut) :-
   NotYetIndex > CurIndex,  % that should be the case because of sorting; fail if not
   !, % Commit to choice
   ListIn  = [X|Rest],
   ListOut = [X|More],
   succ(CurIndex,NextIndex),
   go_through([NotYetIndex-V|RestPairs],NextIndex,Rest,More).

% Case of DONE with list traversal
% Only succeed if there are not more pairs left (i.e. no out-of-bound replacements)

go_through([],_CurIndex,L,L).

% ===
% Tests
% ===

:- begin_tests(another_vectorial_replace1).

test(empty)  :- another_vectorial_replace1([],[],LO),
                LO=[].

test(nop_op) :- another_vectorial_replace1([a,b,c,d],[],LO),
                LO=[a,b,c,d].

test(one)    :- another_vectorial_replace1([a],[(1,xxx)],LO),        
                LO=[xxx].

test(two)    :- another_vectorial_replace1([a,b,c,d],[(4,y),(2,x)],LO),
                LO=[a,x,c,y].

test(full)   :- another_vectorial_replace1([a,b,c,d],[(1,e),(2,f),(3,g),(4,h)],LO),
                LO=[e,f,g,h].

test(duplicate_replacement,[fail]) :- another_vectorial_replace1([a],[(1,x),(1,y)],_). 
test(out_of_bounds_high,[fail])     :- another_vectorial_replace1([a],[(2,y)],_).
test(out_of_bounds_low,[fail])    :- another_vectorial_replace1([a],[(0,y)],_).

:- end_tests(another_vectorial_replace1).

rt :- debug(topic),run_tests(another_vectorial_replace1).

Приложение 2

Замена с использованием maplist/N, foldl/N и library(assoc)

За кулисами исчезают рекурсивные вызовы!

https://github.com/dtonhofer/prolog_notes/blob/master/code/vector_replace0.pl

Answer 3

(далее предполагается, что индексы в списке пар будут отсортированы в порядке возрастания, как показано в примере в вопросе.)

То, что вы сказали, может быть записано как одно соединение

  E=[A,B,C,D], L=[(1,a),(3,c)], solve(E,L), E=[a,B,c,D].

, которое вы собираетесь держать под правильным определением solve/2, которое вы хотите найти. Но разве это не похоже на слова

  E=[A|E2],    L=[(1,a)|L2], 
       E2=[B,C,D],      L2=[(3,c)],
                               solve(E2,L2),     E2=[B,c,D], 
                                            E=[a|E2].

? Хотя что-то здесь не совсем подходит. c в E2 появляется в секунде позиции, а не 3 rd, как указано ее записью в L2.

Но, естественно, L2 должен быть проиндексирован с 2 , так как это хвост L, который проиндексирован с 1 . Таким образом, мы должны сделать это явным:

  E=[A,B,C,D], L=[(1,a),(3,c)], solve(E,L), E=[a,B,c,D]
==
  E=[A,B,C,D], L=[(1,a),(3,c)], solve(E,1,L), E=[a,B,c,D]          % starting index 1
==
  E=[A|E2],    L=[(1,a)|L2], 
       E2=[B,C,D],      L2=[(3,c)],
                               solve(E2,2,L2), E2=[B,c,D], E=[a|E2]

must, и теперь может удерживать. Но откуда взялась a, в E? На самом деле мы имеем в виду

  E=[A|E2],    L=[(1,a)|L2],
               p( (1,a),                1,                    a),   % index match
       E2=[B,C,D],      L2=[(3,c)],
                               solve(E2,2,L2), E2=[B,c,D],          % starting index 2
                                                           E=[a|E2]

с p/3, определенным как

p( (I,A), I, A).

И поэтому также следует учитывать, что

       E2=[B|E3],       L2=[(3,c)],
                    \+ p(   (3,c),      2,         c),              % index mismatch
             E3=[C,D],     L3=L2,
                               solve(E3,3,L3), E3=[c,D], E2=[B|E3]

L2 не , пройденный на этом шаге (L3=L2), поскольку p( (3,c), 2, c) не не удерживается.

Видите ли вы, как рекурсивный определение solve/3 проявляется здесь? Не могли бы вы закончить sh это?