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

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

Напишите предикат 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. Но я не знаком с синтаксисом и циклами в Прологе.


list prolog
person pew007    schedule 30.11.2011    source источник
comment
Мне жаль, что я не могу помочь, но мне действительно любопытно. В какой школе преподают Пролог в наши дни? Это факультатив? Класс бакалавриата или магистратуры?   -  person Bill    schedule 30.11.2011
comment
да, это начальный курс, который знакомит с различными языками программирования, такими как Python, Ocaml и Prolog. это довольно интересно, но я не понимаю, зачем это нужно ...   -  person pew007    schedule 30.11.2011
comment
Это классно. Знакомство с разными языками делает вас лучшим программистом. Удачи!   -  person Bill    schedule 30.11.2011
comment
ну, с циклами в Прологе лучше не разбираться; циклы в прологе - это плохо: b Попытайтесь реализовать свою идею, в любом случае ознакомление с синтаксисом пролога является целью упражнения.   -  person Thanos Tintinidis    schedule 30.11.2011
comment
@thanosQR: Немного не по теме, но я не согласен с циклами в Прологе. Каждый рекурсивный предикат в некотором роде реализует цикл, что является важным моментом для понимания Prolog как студента. А в ECLiPSe вы можете использовать логические циклы в качестве синтаксического сахара, которые переводятся в рекурсивные предикаты.   -  person twinterer    schedule 30.11.2011
comment
@twinterer в основном я имел в виду циклы, в которых не удалось выполнить рекурсию; Я согласен, что вы можете рассматривать рекурсию как цикл   -  person Thanos Tintinidis    schedule 30.11.2011

Ответы (2)


arrow_upward
7
arrow_downward

Собственно, у меня есть три ответа. Вы, наверное, захотите третьего. Но все равно пройдите через другие.

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 - использовать (X-Y). Знак минус здесь не означает вычитание. Это просто непонятный термин.

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

2 чересстрочная развертка

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

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

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

?- 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 должны выглядеть так, чтобы случайное / 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].
person false    schedule 30.11.2011

arrow_upward
3
arrow_downward

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

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), и обработать этот случай отдельно.

person twinterer    schedule 30.11.2011