функция zip в прологе

Question

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

Напишите предикат Пролога zip(L1,L2,L3), который будет верным, если список L3 получен путем архивированиятасование «или перемежение») элементов списков L1 и L2.Обновление: списки L1 и L2 могут иметь разную длину.Например, когда вы закончите, вы должны получить следующее поведение:

?- zip([1,2],[a,b],[1,a,2,b]).
true.
?- zip([1,2],[a,b],X).
X = [1, 2, a, b] ;
X = [1, 2, a, b] ;
X = [1, a, 2, b] ;
X = [1, a, b, 2] ;
X = [a, 1, 2, b] ;
X = [a, 1, b, 2] ;
X = [a, b, 1, 2] ;
X = [a, b, 1, 2] ;
false.
?- zip([1,2],[a,b],[1,2,a,b]).
true.
?- zip(X,[a,b],[1,a,2,b]).
X = [1,2]
true.
?- zip([1,2],X,[1,a,2,b]).
X = [a,b]
true.

Я думаю о создании списка, который содержит элементы из L1 и L2, а затем сравнит список с L3.Но я не знаком с синтаксисом и циклами в Прологе.

Answer 1

На самом деле у меня есть три ответа для вас. Вы, вероятно, хотите третий. Но все равно пройдитесь по остальным.

1 Другая проблема

Я не уверен, что вы хотите описать отношение, которое вы описываете. Вы также изучать OCaml и Python одновременно и на этих языках что-то другое. Это означает что-то вроде:

zip([], [], []).
zip([], [_|_], []).
zip([_|_], [], []).
zip([X|Xs], [Y|Ys], [X-Y|XYs]) :-
   zip(Xs, Ys, XYs).

?- zip([1,2],[3,4],XYs).
XYs = [1-3,2-4].

Обратите внимание на другое соглашение в Прологе. В то время как OCaml, Python, но также и Haskell используют (X, Y) для обозначения кортежа, в Prolog принято использовать (X-Y). Знак минус здесь не означает вычитание. Это просто не истолкованный термин.

Обычный способ реализовать это в Прологе - использовать maplist. maplist требует, чтобы все списки были одинаковой длины.

2 Чередование

(Правка) Другая интерпретация заключается в следующем. Имя как interlace/3 или shuffle/3 было бы идеально здесь. Недавно @salva показала нам очень красивое решение этот. Не забудьте +1 это! Позвольте мне показать только несколько классных способов, как вы можете использовать это:

?- shuffle([1,2],[3,4],Zs).
Zs = [1,3,2,4].

Это ты уже знаешь. Но зачем нам давать оба списка [1,2] и [3,4] Прологу? Это не простой язык программирования, который заставляет тебя все рассказывать. Если вам лень вводить сложный список или другой термин, просто поместите переменную и посмотрите, как Пролог это выяснит. Итак, давайте заменим второй список переменная.

?- shuffle([1,2],Ys,Zs).
Ys = [],
Zs = [1,2] ;
Ys = [_G607],
Zs = [1,_G607,2] ;
Ys = [_G607,_G616|_G617],
Zs = [1,_G607,2,_G616|_G617].

Таким образом, мы спрашиваем: как Ys и Zs должны выглядеть так, чтобы shuffle / 3 был истинным? На самом деле, есть 3 ответа для Ys:

• [] - пустой список. Zs - это тогда [1,2]. Так что это одно решение.

• [_G607] - список с ровно одним элементом. Zs это [1,_G607,2]. _G607 является свободной переменной. У него может быть более приятное имя, но дело в том, что эта переменная встречается и в пределах Ys и в Zs. Этот ответ говорит: Все термины, которые входят в эту переменную, являются решениями. Таким образом, мы имеем здесь бесконечно много решений, выраженных в одном ответе.

• [_G607,_G616|_G617] означает список, содержащий не менее двух элементов.

Вот еще более интересный запрос:

?- shuffle(Xs,Xs,Zs).
Xs = Zs, Zs = [] ;
Xs = [_G592],
Zs = [_G592,_G592] ;
Xs = [_G592,_G601],
Zs = [_G592,_G592,_G601,_G601] ;
Xs = [_G592,_G601,_G610],
Zs = [_G592,_G592,_G601,_G601,_G610,_G610]
...

Посмотрите, как теперь есть дубликаты одной и той же переменной в Zs!

3 переплетение

Может быть, это то, что вы на самом деле хотите:

intertwine([], [], []).
intertwine([E|Es], Fs, [E|Gs]) :-
   intertwine(Es, Fs, Gs).
intertwine(Es, [F|Fs], [F|Gs]) :-
   intertwine(Es, Fs, Gs).

В следующем запросе мы спрашиваем о списках, которые можно переплетать, чтобы получить список из трех элементов в результате!

?- length(Zs,3), intertwine(Xs,Ys,Zs).
Zs = Xs, Xs = [_G648,_G651,_G654],
Ys = [] ;
Zs = [_G648,_G651,_G654],
Xs = [_G648,_G651],
Ys = [_G654] ;
Zs = [_G648,_G651,_G654],
Xs = [_G648,_G654],
Ys = [_G651] ;
Zs = [_G648,_G651,_G654],
Xs = [_G648],
Ys = [_G651,_G654] ;
Zs = [_G648,_G651,_G654],
Xs = [_G651,_G654],
Ys = [_G648] ;
Zs = [_G648,_G651,_G654],
Xs = [_G651],
Ys = [_G648,_G654] ;
Zs = [_G648,_G651,_G654],
Xs = [_G654],
Ys = [_G648,_G651] ;
Zs = [_G648,_G651,_G654],
Xs = [],
Ys = [_G648,_G651,_G654].

Answer 2

Ваша программа должна каким-то образом перебирать списки, чтобы чередовать L1 и L2 в L3 или разбирать L3 в L1 и L2. Когда вы пишете «петли» в своем посте, вы подразумеваете эту итерацию. В Прологе вы используете рекурсивные предикаты для реализации циклического поведения. Каждый рекурсивный предикат нуждается в некотором якоре. В вашей программе один из якорей, вероятно, будет выглядеть так:

zip([], L, L) :- !.

Т.е., когда L1 - пустой список, тогда L3 будет просто состоять из L2.

Обратите внимание на вырез (!/0) в конце предложения. Он сообщает Prolog, что как только вызов предиката был успешно объединен с главой этого предложения, ему не нужно искать альтернативы. Это позволяет избежать лишних точек выбора.

Этого якоря недостаточно. Найти остальное не должно быть сложно.

Теперь, когда у вас есть якоря, вы можете думать о рекурсии. Поведение должно быть примерно таким: следующий элемент L3 («голова») может быть следующим элементом L1 или следующим элементом L2 (т. Е. Здесь есть выбор, следовательно, «точка выбора»). Каждый случай, вероятно, входит в свое собственное предложение.

Независимо от выбора, вы затем снова вызываете zip-предикат рекурсивно с остальными ("хвостом") L1 (или L2) и остальной частью L3.

Теперь это должно быть легко реализовать.

Однако есть небольшой улов: у вас все еще слишком много вариантов выбора, например, например. этот запрос:

?- zip([1,2],X,[1,a,2,b]).

не закончится простым «да», но скажет вам, что может быть больше решений (которых нет). Чтобы удалить лишнюю точку выбора, вам нужно проверить, полностью ли создан экземпляр L3 (используйте ground/1), и обработать этот случай отдельно.