Изменение порядка имен переменных

Как написать стандартным подходящим способом avs_term_rearranged(AVs, T, AVsR) с заданными AVs и T так, чтобы AVsR было перестановкой AVs с элементами, расположенными в том же порядке, что и их переменные в порядке слева направо в T.

AVs - это список элементов формы A = V, где A - атом, обозначающий имя переменной, например 'X', а V - соответствующая переменная. Такие списки создаются read_term/2,3 с опцией чтения variable_names/1 (7.10.3). Кроме того, точный порядок элементов не определен.

| ?- read_term(T,[variable_names(AVs)]).
A+B+A+_+C.

AVs = ['A'=A,'B'=B,'C'=C]
T = A+B+A+_+C

T - это термин, который содержит все переменные AVs плюс еще несколько.

Обратите внимание, что в стандартной соответствующей программе нельзя полагаться на порядок терминов для переменных (7.2.1):

7.2.1 Переменная

Если X и Y - переменные, которые не идентичны, то X term_precedes Y должен зависеть от реализации, за исключением того, что во время создания отсортированного списка (7.1.6.5, 8.10.3.1 j) порядок должен оставаться постоянным.

ПРИМЕЧАНИЕ. Если X и Y являются анонимными переменными, то они не являются идентичными терминами (см. 6.1.2 a).

Рассмотрим в качестве примера из 8.4.3.4:

sort([f(U),U,U,f(V),f(U),V],L).
   Succeeds, unifying L with [U,V,f(U),f(V)] or
   [V,U,f(V),f(U)].
   [The solution is implementation dependent.]

Итак, есть два возможных варианта работы sort/2, и нельзя даже полагаться на успех:

sort([f(U),U,U,f(V),f(U),V],L), sort(L, K), L == K.

Например:

?- avs_term_rearranged(['A'=A,'B'=B,'C'=C], A+C+F+B, AVsR).
   AVsR = ['A'=A,'C'=C,'B'=B].

prolog iso-prolog
person false    schedule 23.01.2014    source источник
comment
T произвольный термин или имеет ту же форму? это, например, также получено из read_term?   -  person Christian Fritz    schedule 25.01.2014
comment
Кстати, вы дважды используете T в своем вопросе с разными значениями. Может помочь переименовать один из них, чтобы избежать путаницы.   -  person Christian Fritz    schedule 25.01.2014
comment
@ChristianFritz: Я не вижу разницы. Один раз T используется в качестве аргумента для искомого предиката, а один раз он используется с read_term, который в этом случае производит T и AVs так, чтобы они соответствовали предикату.   -  person false    schedule 25.01.2014
comment
Не могли бы вы привести пример ввода и ожидаемого вывода? Вы это имеете в виду avs_term_rearranged(['A'=A,'B'=B,'C'=C], A+C+F+B, ['A'=A,'C'=C,'B'=B])?   -  person Christian Fritz    schedule 25.01.2014
comment
Кажется, что если вы можете понять, как использовать ream_term/3 для чтения из потока, который вы пишете, используя write_term/3, тогда вы можете получить представление переменных в T, которое соответствует таковому для AVs, и в этот момент это простой вопрос отбрасывания из T-переменных все те, которые не фигурируют в AVs переменных.   -  person Christian Fritz    schedule 25.01.2014
comment
@ChristianFritz: Не понимаю, что вы имеете в виду. Но на самом деле read_term/3 и write_term/3 используют один и тот же формат. И определение переменных void находится здесь: stackoverflow.com/questions/7947910/   -  person false    schedule 25.01.2014
comment
и просто для пояснения: мы согласны с тем, что если бы T был не термином, а атомом, например, 'A+C+F+B', тогда это было бы очень просто, не так ли? Итак, вы действительно ищете способ получить символы, используемые для несвязанных переменных в T. Правильный?   -  person Christian Fritz    schedule 27.01.2014
comment
Если T является атомом (что тоже является термином), то его AVs должно быть []. Я не уверен в используемой вами терминологии.   -  person false    schedule 27.01.2014
comment
Ответ Иоахима уже опровергает мою мысль. Но просто чтобы объяснить мою терминологию, если бы у вас был нужный вам термин в качестве атома (с сохраненными именами переменных), вы могли бы напечатать этот атом в потоке, а затем использовать read_term / 3 в этом потоке для восстановления имен переменных. Не знал, что term_variables их тоже сохраняет. Это, конечно, проще.   -  person Christian Fritz    schedule 27.01.2014
comment
@ChristianFritz: Опять же, у меня проблемы с вашей терминологией: как вы думаете, что делает term_variables/2? Его функциональность не зависит от имен переменных.   -  person false    schedule 27.01.2014
comment
Я подумываю о создании тега prolog-variable-names, связанного с темами о переименовании переменных с использованием предикатов, таких как numbervars / 3. Жду вашего отзыва.   -  person Guy Coder    schedule 01.02.2020
comment
numbervars / 3 - другое дело. Мне это не нравится, так как это источник многих ошибок.   -  person false    schedule 01.02.2020

Ответы (4)


arrow_upward
15
arrow_downward

Используйте term_variables/2 на T, чтобы получить список Xs с переменными в желаемом порядке. Затем создайте список с элементами AVs, но в указанном порядке.

avs_term_rearranged(AVs, T, AVRs) :-
    term_variables(T, Xs),
    pick_in_order(AVs, Xs, AVRs).

pick_in_order([], [], []).
pick_in_order(AVs, [X|Xs], AVRs) :-
    ( pick(AVs, X, AV, AVs1) ->
        AVRs = [AV|AVRs1],
        pick_in_order(AVs1, Xs, AVRs1)
    ;
        pick_in_order(AVs, Xs, AVRs)
    ).

pick([AV|AVs], X, AX, DAVs) :-
    (_=V) = AV,
    ( V==X ->
        AX = AV,
        DAVs = AVs
    ;
        DAVs = [AV|DAVs1],
        pick(AVs, X, AX, DAVs1)
    ).

Примечания:

  • это квадратично, потому что pick/4 линейно
  • term_variables/2 не является строго необходимым, вы можете пройти T напрямую
person jschimpf    schedule 26.01.2014

arrow_upward
13
arrow_downward

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

Как и раньше, мы в основном перестраиваем список AVs таким образом, чтобы его элементы имели тот же порядок, что и переменные в списке Xs (полученном из term_variables/2). Новая идея здесь состоит в том, чтобы сначала вычислить (основное) описание требуемой перестановки (APs), а затем построить перестановку AV, используя это описание.

avs_term_rearranged(AVs, T, AVRs) :-
    term_variables(T, Xs),
    copy_term(AVs-Xs, APs-Ps),
    ints(Ps, 0, N),
    functor(Array, a, N),
    distribute(AVs, APs, Array),
    gather(1, N, Array, AVRs).

ints([], N, N).
ints([I|Is], I0, N) :- I is I0+1, ints(Is, I, N).

distribute([], [], _).
distribute([AV|AVs], [_=P|APs], Array) :-
    nonvar(P),
    arg(P, Array, AV),
    distribute(AVs, APs, Array).

gather(I, N, Array, AVRs) :-
    ( I > N ->
        AVRs = []
    ;
        arg(I, Array, AV),
        I1 is I+1,
        ( var(AV) -> AVRs=AVRs1 ; AVRs = [AV|AVRs1] ),
        gather(I1, N, Array, AVRs1)
    ).
person jschimpf    schedule 28.01.2014
comment
Красиво, но не переносимо, поскольку требует, чтобы Array был составным термином с неограниченной арностью. Меньшая проблема заключается в том, что для этого требуются целые числа произвольного размера. - person Per Mildner; 28.01.2014
comment
@Per, честно говоря, я думаю, что по прошествии 30 лет пора положить конец ограничениям на арность составных терминов. - person jschimpf; 01.02.2014
comment
@Per, я не понимаю вашего комментария о целых числах произвольного размера. В этом коде не больше требований к большим целым числам, чем к любому коду, использующему длину / 2. Фактически, это один из немногих типов программ, в которых целые числа строго ограничены (примерно до 2 ^ 30 на 32-битных или 2 ^ 61 на 64-битных машинах). - person jschimpf; 01.02.2014
comment
Вопрос был конкретно о стандартном соответствующем решении. В стандарте нет ничего, что требовало бы произвольной арности составных терминов или целых чисел, достаточно больших, чтобы представлять длину представимого списка. На практике целочисленный размер вряд ли будет проблемой, поэтому я написал, что его размер - меньшая проблема. - person Per Mildner; 02.02.2014
comment
Позвольте мне подвести итог и пояснить: (1) это программа, полностью соответствующая стандартам; (2) он не требует целых чисел произвольного размера; (3) Реализации ISO-Prolog различаются по размеру поддерживаемых ими экземпляров проблем; (4) Решение Пера с меньшей вероятностью столкнется с такими ограничениями реализации и в целом более элегантно, поэтому я проголосовал за него и аплодировал. - person jschimpf; 03.02.2014

arrow_upward
11
arrow_downward

Эта версия очень короткая, в ней используется member/2 (из Пролог пролог) для поиска. Он имеет очень низкое потребление вспомогательной памяти. Создается только список AVsR. Никакие временные heap-термины не создаются (в текущих реализациях). Однако у него есть квадратичные накладные расходы длиной AVs.

avs_term_rearranged(AVs, T, AVsR) :-
   term_variables(T, Vs),
   rearrange(Vs, AVs, AVsR).

rearrange([], _, []).
rearrange([V|Vs], AVs, AVsR0) :-
   ( member(AV, AVs),
     AV = (_=Var), V == Var ->
      AVsR0 = [AV|AVsR]
   ;  AVsR0 = AVsR
   ),
   rearrange(Vs, AVs, AVsR).

Другой аспект состоит в том, что цель member(AV, AVs) по своей сути недетерминирована, даже если задействован только относительно неглубокий недетерминизм, тогда как (первая) версия @ jschimpf действительно создает точку выбора только для (;)/2 реализации if-then-else. Обе версии не оставляют после себя ни одного очка выбора.

Вот версия, более точно воспроизводящая идею @ jschimpf. Это, однако, теперь создает вспомогательные термины, которые остаются в куче.

rearrange_js([], _, []).
rearrange_js([V|Vs], AVs0, AVsR0) :-
   ( select(AV, AVs0, AVs),
     AV = (_=Var), V == Var ->
      AVsR0 = [AV|AVsR]
   ;  AVsR0 = AVsR,
      AVs0 = AVs
   ),
   rearrange_js(Vs, AVs, AVsR).
person false    schedule 28.01.2014

arrow_upward

arrow_downward

person    schedule
comment
Уносит мой ум. Я мог бы поклясться, что нужно либо что-то похожее на версию @JSchimpf (ограниченную max_arity и max_integer), либо sort/2 потребуется для связывания переменных и их порядка. В любом случае, я рад, что спросил, я бы никогда не нашел такого решения. Может быть, ментальный блок заключался в том, что я надеялся переставить существующие (=)/2, в то время как вы реконструируете их, говоря процедурно. - person false; 31.01.2014
comment
Пошаговая инструкция: После copy_term/2: AVs можно вернуть. После bind_names/2: AVs1 можно вернуть. До build_vn_list: присутствуют только два списка: вообще нет пар !! - person false; 31.01.2014
comment
Блестяще! Мне было интересно, есть ли у нас название для этой техники использования двудольной структуры данных с парами соответствующих переменных в качестве средства отображения. - person jschimpf; 01.02.2014