Функция 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([_|_], [], []).
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 часто встречается соглашение (XY). Знак минус здесь не означает вычитание. Это просто не истолкованный термин.

Обычный способ реализовать это в Прологе - использовать 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) и обрабатывать этот случай отдельно.

Answer 3

Равной длины (но это дает некоторую "тонкую" ошибку)

      :- use_module(library(lambda)).
zip1(L1,L2,Z) :- scanl(\X^Y^_^[X,Y]^[X,Y],L1,L2,_,[_|Z]).
zip2(L1,L2,Z) :- maplist(\X^Y^[X,Y]^[X,Y],L1,L2,Z).

или лучше этот:

      ?- assertz(pair(X,Y,[X,Y])).
?- maplist(pair,[1,2,3],[4,5,6],Z).
Z = [[1, 4], [2, 5], [3, 6]].