Сопрограммирование в Прологе: когда аргумент представляет собой список (имеет фиксированную длину)

Вопрос

Можно ли запланировать выполнение цели, как только длина списка будет известна/фиксирована, или, как указано в комментариях @false, данный аргумент становится [правильным] списком? Что-то в этом роде:

when(fixed_length(L), ... some goal ...).

Когда-условия могут быть построены с использованием только ?=/2, nonvar/1, ground/1, ,/2 и ;/2, и кажется, что они не очень полезны, если смотреть на весь список.

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

Мотивация

Я думаю, что это условие может быть полезным, когда кто-то хочет использовать предикат p(L) для проверки свойства на наличие списка L, но без использования его генеративным способом.

Например. может случиться так, что [по соображениям эффективности или завершения] предпочтительнее выполнить следующую конъюнкцию p1(L), p2(L) в этом порядке, если L имеет фиксированную длину (т. список).

Это может быть достигнуто следующим образом:

when(fixed_length(L), p1(L)), p2(L).

Обновить

Я реализовал решение, но ему не хватает чистоты.


prolog prolog-coroutining logical-purity
person Tudor Berariu    schedule 19.01.2015    source источник
comment
Просто терминологический вопрос. Список [], [_], [_,_]. Но [_,_|_] — это не список, это частичный список. Для этого when(list(L), G) может быть лучшим именем.   -  person false    schedule 19.01.2015
comment
Есть ли имя, которое включает в себя как списки, так и частичные списки? Я думал, что все частичные списки также являются списками.   -  person Tudor Berariu    schedule 19.01.2015
comment
Вы можете сказать о списке типов. Терминология до ISO также была: правильный список (для списка, а не частичного списка) и неправильный список, скажем, [1|2]. Но если только правильные списки являются реальными, это в некоторой степени означает, что правильные необходимы и для других терминов, таких как целые числа.   -  person false    schedule 19.01.2015
comment
Обратите внимание, что Xs также является неполным списком. Таким образом, любой терм является частичным списком, который сам не является списком, но имеет экземпляры, которые являются списками.   -  person false    schedule 19.01.2015
comment
Я скоро отредактирую свой вопрос и отвечу с правильной терминологией. Теперь я понимаю, что мой вопрос на самом деле о том, что частичные списки становятся списками.   -  person Tudor Berariu    schedule 19.01.2015

Ответы (2)


arrow_upward
2
arrow_downward

Было бы неплохо, если бы when/2 поддерживал условие list/1. А пока подумайте:

list_ltruth(L, Bool) :-
   freeze(L, nvlist_ltruth(L, Bool)).

nvlist_ltruth(Xs0, Bool) :-
   (  Xs0 == [] -> Bool = true
   ;  Xs0 = [_|Xs1] -> freeze(Xs1, nvist_ltruth(Xs1, Bool))
   ;  Bool = false
   ).

when_list(L, Goal_0) :-
   nvlist_ltruth(L, Bool),
   when(nonvar(Bool),( Bool == true, Goal_0 )).

Таким образом, вы можете комбинировать это также с другими условиями.

Может возникнуть ошибка типа, если L не является списком.

   when(nonvar(Bool), ( Bool == true -> Goal_0 ; sort([], L) ).

Приведенный выше трюк будет работать только в системе Prolog, соответствующей ISO, такой как SICStus или GNU, которая создает type_error(list,[a|nonlist]) для sort([],[a|nonlist]), в противном случае замените ее на:

   when(nonvar(Bool),
      ( Bool == true -> Goal_0 ; throw(error(type_error(list,L), _)).

Многие системы содержат некоторые встроенные функции, такие как '$skip_list', для быстрого просмотра списков, вы можете использовать их здесь.

person false    schedule 19.01.2015

arrow_upward
1
arrow_downward

Мне удалось ответить на мой собственный вопрос, но не с чистым решением.

Некоторые наблюдения

Трудность, возникающая при написании программы, планирующей выполнение некоторой цели, когда длина списка точно известна, заключается в том, что фактическое условие может измениться. Учти это:

when(fixed_length(L), Goal)

Длина списка может измениться, если L не связан или если не связан последний конец. Скажем, у нас есть этот аргумент L = [_,_|Tail]. L имеет фиксированную ширину, только если Tail имеет фиксированную ширину (другими словами, L — это список, если T — это список). Таким образом, условие, которое проверяет Tail, может быть единственным, что нужно сделать вначале. Но если Tail становится [a|Tail2], требуется новое условие, которое проверяет, является ли Tail2 списком.

Решение

<сильный>1. Получение условия-когда

Я реализовал предикат, который связывает неполный список с условием «когда», которое сигнализирует, когда он может стать списком (например, nonvar(T), где T — это самый глубокий конец).

condition_fixed_length(List, Cond):-
    \+ (List = []),
    \+ \+ (List = [_|_]),
    List = [_|Tail],
    condition_fixed_length(Tail, Cond).
condition_fixed_length(List, Cond):-
    \+ \+ (List = []),
    \+ \+ (List = [_|_]),
    Cond = nonvar(List).

<сильный>2. Рекурсивно при условии

check_on_fixed_length(List, Goal):-
    (
         condition_fixed_length(List, Condition)
     ->
         when(Condition, check_on_fixed_length(List, Goal))
     ;
         call(Goal)
    ).

Примеры запросов

Предположим, мы хотим проверить, что все элементы L равны a, когда размер L фиксирован:

?- check_on_fixed_length(L, maplist(=(a), L)).
when(nonvar(L), check_on_fixed_length(L, maplist(=(a), L))).

... и затем L = [_,_|Tail]:

?- check_on_fixed_length(L, maplist(=(a), L)), L = [_,_|L1].
L = [_G2887, _G2890|L1],
when(nonvar(L1), check_on_fixed_length([_G2887, _G2890|L1], maplist(=(a), [_G2887, _G2890|L1]))).

?- check_on_fixed_length(L, maplist(=(a), L)), L = [_,_|L1], length(L1, 3).
L = [a, a, a, a, a],
L1 = [a, a, a].

примесь

conditon_fixed_length/2 является источником нечистоты, как видно из следующего запроса:

?- L = [X, Y|Tail], condition_fixed_length(L, Cond), L = [a,a].
L = [a, a],
X = Y, Y = a,
Tail = [],
Cond = nonvar([]).

?- L = [X, Y|Tail], L = [a, a], condition_fixed_length(L, Cond).
false.
person Tudor Berariu    schedule 19.01.2015