Разрыв между / 3-ориентированной «петлей» в SWI-Prolog при сохранении точек выбора, следующих за ней - PullRequest
Новая
       28

Разрыв между / 3-ориентированной «петлей» в SWI-Prolog при сохранении точек выбора, следующих за ней

0 голосов
/ 20 ноября 2018

Мне нужно перебрать диапазон чисел (например, используя between/3) от 1 до Length, где Length - длина заданного списка.Повторное число, скажем, N, затем применяется к предикату, скажем, do_something, пока оно не перестанет работать.То есть do_something ищет правильный N, после чего все точки выбора between/3 должны быть отброшены.Однако все точки выбора do_something с соответствующим N должны быть выполнены.

Попытка кулака была примерно такой: 

% main(+InputList, -N, -OutputList)
main(InputList, N, OutputList) :-
  length(InputList, Length),
  between(1, Length, N),

  % cut all between/3 choice points as soon as Num is instantiated
  freeze(Num, !),

  do_something(InputList, N, OutputList),
  Num is N.

Это не сработало, поскольку freeze/2 неbetween/3 выбор очков.Версия с when/2 тоже не работала.Я понимаю, это потому, что оба freeze/2 и when/2 выполняются в отдельном потоке и не влияют на основной поток, где between/3.

Через некоторое время я получил следующий код, которыйделает то, что нужно, но неэффективно: 

main(InputList, N, OutputList) :-
  length (InputList, Length),
  between(1, Length, N),
  do_something(InputList, N, _),

  % cut all prior choice points as soon as proper N is found
  !,

  % start do_something over!
  do_something(InputList, N, OutputList).

Неэффективность в том, что точка выбора do_something с правильным N выполняется дважды.Сначала непосредственно перед резкой, а затем еще раз сразу после нее.

Хотя это решение работает в моем случае, оно не применимо к универсальному случаю, когда все do_something точки выбора должны выполняться только один раз.

Обратите внимание, что N должен быть минимальным из диапазона 1..Length и заранее не известен.Следовательно, ищите его с помощью do_something.

Есть ли лучшее решение для этого?Есть ли способ реализовать предикат, похожий на between/3, который может прекратиться при сигнале?Может ли быть специализированный встроенный предикат, который делает то, что нужно?Любые плодотворные идеи высоко ценятся.

Ответы [ 3 ]

0 голосов
/ 21 ноября 2018

Существует еще одна возможность использования * -> / 2 , которая является вариантом -> / 2, которая не убивает точку выбора условия.Теперь нас нет, мы хотим убить более старую точку выбора.Я не знаю, существуют ли системы Prolog, которые могут это сделать.У большинства есть условия, чтобы убить все точки выбора с некоторой отметки, но я не знаю ни одной, которая убивает определенную.Итак, мы должны вставить немного кода, чтобы условно остановить дальнейшую обработку.Это приводит к: 

main(InputList, N, OutputList) :-
    length(InputList, Length),
    State = state(cont),
    between(1, Length, N),
    (   State = state(cont)
    ->  true
    ;   !,
        fail
    ),
    (   do_something(InputList, N, OutputList)
    *-> nb_setarg(1, State, stop)
    ;   fail
    ).

Это абсолютно непереносимо, хотя многие системы имеют * -> (иногда называемый if / 3), и многие имеют некоторую форму невыпускаемого назначения, в то время как если вы отчаялись, выдля этого можно использовать assert / retract.

См. онлайн на SWISH

Ответ Пауло, безусловно, более переносимый.Это должно быть намного быстрее, хотя и не оценивает все решения do_something перед возвратом первого, и при этом оно не оценивает do_something дважды.

0 голосов
/ 21 ноября 2018

Оказывается, between/3 отвлекает.Нам это не требуется, и поэтому возможно простое, эффективное и портативное решение: 

main(InputList, N, OutputList) :-
    length(InputList, Length),
    Length >= 1,
    main(1, Length, InputList, OutputList).

main(N, Length, InputList, OutputList) :-
    (   do_something(InputList, N, OutputList) *->
        true
    ;   N < Length,
        M is N + 1,
        main(M, Length, InputList, OutputList)
    ).

Как и в решении Яна, оно не оценивает все решения do_something/3 перед возвратом первого, такжеон оценивает предикат дважды.Но для этого также не требуются неприятные и непереносимые приемы предикатов nb_setarg/2.

Обратите внимание, что, как заметил Ян, управляющая конструкция soft-cut , *->/2 илиего if/3 мета-предикатный вариант может быть найден в нескольких системах Prolog (включая, в той или иной форме, CxProlog, Ciao Prolog, ECLiPSe, GNU Prolog, JIProlog, SICStus Prolog, SWI-Prolog и YAP).

PS Я держу свой первый ответ, так как он более переносим и иллюстрирует шаблон, который может быть полезен для других проблем.

0 голосов
/ 20 ноября 2018

Надеюсь, что я понял описание вашей проблемы: 

main(InputList, N, OutputList) :-
    length(InputList, Length),
    between(1, Length, N),
    findall(
        OutputList0,
        do_something(InputList,N,OutputList0),
        OutputLists
    ),
    % cut all prior choice points as soon as proper N is found
    OutputLists = [_|_],
    !,
    member(OutputList, OutputLists).

Вызов findall/3 вернет Solutions = [] до тех пор, пока предикат do_something/3 не будет успешным.Когда это происходит, вызов findall/3 гарантирует, что для этого значения N все точки выбора do_something(InputList, N, OutputList) будут посещены.Следующее сокращение затем фиксирует значение N, и вы можете перейти оттуда.

PS Обновлено с изменением, которое вы опишите в своем комментарии, чтобы оно работало для вашего случая.Есть несколько непереносимых хаков, которые могут найти только определенное количество решений, если вы не хотите собирать их все.

...