пролог - Подсписок списка - альтернативный подход

Question

Я реализовал функцию, чтобы получить подсписок списка, например:

sublist([1,2,4], [1,2,3,4,5,1,2,4,6]). 
true 

sublist([1,2,4], [1,2,3,4,5,1,2,6]). false взгляд на мое решение:

my_equals([], _). 
my_equals([H1|T1], [H1|T2]) :- my_equals(T1, T2). 

sublist([], _). 
sublist(L1, [H2|T2]) :- my_equals(L1, [H2|T2]); sublist(L1, T2). 

Не могли бы вы дать мне другое решение ? Может быть, существует предопределенный предикат как my_equals?

Answer 1

Там также DCG подход к проблеме:

substr(Sub) --> seq(_), seq(Sub), seq(_). 

seq([]) --> []. 
seq([Next|Rest]) --> [Next], seq(Rest). 

Что вы назвали бы с:

phrase(substr([1,2,4]), [1,2,3,4,5,1,2,4,6]). 

Вы можете определить:

sublist(Sub, List) :- 
    phrase(substr(Sub), List). 

Таким образом, вы могли бы назвать его , sublist([1,2,4], [1,2,3,4,5,1,2,4,6])..

---

За предложение @ мата:

substr(Sub) --> ..., seq(Sub), ... . 

... --> [] | [_], ... . 

Да, вы можете иметь предикат с именем .... :)

---

В предложениях от @repeat и @false я сменил имя с subseq (подпоследовательность) на substr (подстрока), поскольку значение «подпоследовательности» охватывает несмежные последовательности.

Answer 2

Вы можете объединить подсписок с помощью append/3, как это:.

sublist(SubList, List):- 
    append(_, Tail, List), 
    append(SubList, _, Tail). 

Первый вызов append/3 будет разделить список на две части (т.е. отклонить некоторые «ведущие» элементы из списка Второй вызов append/3 проверит подсписок сама подсписок хвоста.

Как @ ложно предполагает, что было бы лучше, по крайней мере, для наземных условий, для обмена целей,

sublist(SubList, List):- 
    append(SubList, _, Tail), 
    append(_, Tail, List). 

Answer 3

Может быть, есть существует некоторые предопределенные предикат

Если Пролог имеет добавление/2 из библиотеки (списки):

sublist(S, L) :- append([_,S,_], L). 

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

sublist(S, L) :- append(S, _, L). 
sublist(S, [_|L]) :- sublist(S, L). 

Answer 4

Это альтернативное решение чтобы Lurkers, что немного быстрее, предполагая, что S намного короче, чем L в длину и, таким образом, фраза/3 DCG время перевод незначителен:

sublist(S, L) :- 
    phrase((..., S), L, _). 

Если S = ​​[X1, .., Xn] его будет DCG перевести это в соответствие I = [X1, .., Xn | O] перед исполнением, тем самым делегируя my_equals/2 полностью в Prolog унификация. Вот пример запуска:

?- phrase((..., [a,b]), [a,c,a,b,a,c,a,b,a,c], X). 
X = [a, c, a, b, a, c] ; 
X = [a, c] ; 
false. 

Bye

P.S .: Работает также другие модели S, чем только терминалы.

Answer 5

Решение в исходном вопросе справедливо, как уже было сказано, замечание о том, что «my_equals» можно заменить циклом «добавить» и «поднять» другим добавлением, предоставляющим срезы исходного списка.

Однако пролог является (или это было) об искусственном интеллекте. Любой человек может ответить сразу «нет» на этот пример:

sublist([1,1,1,2], [1,1,1,1,1,1,1,1,1,1]). 

, потому что человек, с простым наблюдением в списке, выводит некоторую его характеристику, как и что не существует не «2».

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

Некоторые легкие изменения могут быть выполнены с целью взглянуть сначала на самое сильное условие. К примеру:

/* common(X, Y, C, QX, QY) => X=C+QX, Y=C+QY */ 
common([H|S2], [H|L2], [H|C2], DS, DL) :- !, 
    common(S2, L2, C2, DS, DL). 
common(S, L, [], S, L). 

sublist(S, L) :- 
    sublist([], S, L). 

sublist(P, Q, L) :- /* S=P+Q */ 
    writeln(Q), 
    length(P, N), 
    length(PD, N), /* PD is P with all unbound */ 
    append(PD, T, L), /* L=PD+T */ 
    common(Q, T, C, Q2, _DL), /* S=P+C+Q2; L=PD+C+_DL */ 
    analysis(L, P, PD, C, Q2). 

analysis(_L, P, P, _C, []) :- !. /* found sublist */ 

analysis([_|L2], P, _PD, C, []) :- !, 
    sublist(P, C, L2). 

analysis([_|L2], P, _PD, C, Q2) :- 
    append(P, C, P2), 
    sublist(P2, Q2, L2). 

Давайте попробуем это:

?- sublist([1,1,1,2], [1,1,1,1,1,1,1,1,1,1]). 
[1,1,1,2] 
[2] 
[2] 
[2] 
[2] 
[2] 
[2] 
[2] 
[2] 
false. 

посмотреть, как "анализ" решил, что лучше искать "2".

Очевидно, что это очень упрощенное решение, в реальной ситуации лучше провести «анализ», и найденные шаблоны должны быть более гибкими (предложение ограничено шаблонами в хвосте исходного шаблона S).