перестановка( L, L1),
внести( X, L1, P).
Другой вариант этой программы мог бы предусматривать удаление элемента X из первого списка, перестановку оставшейся его части — получение списка P, а затем добавление X в начало списка P. Соответствующая программа такова:
перестановка2( [], []).
перестановка2( L, [X | P] ) :-
удалить( X, L, L1),
перестановка2( L1, P).
Поучительно проделать несколько экспериментов с нашей программой перестановки. Ее нормальное использование могло бы быть примерно таким:
?- перестановка( [красный, голубой, зеленый], P).
Как и предполагалось, будут построены все шесть перестановок:
P = [ красный, голубой, зеленый];
P = [ красный, зеленый, голубой];
P = [ голубой, красный, зеленый];
P = [ голубой, зеленый, красный];
P = [ зеленый, красный, голубой];
P = [ зеленый, голубой, красный];
no (нет)
Приведем другой вариант использования процедуры перестановка:
?- перестановка( L, [а, b, с] ).
Наша первая версия, перестановка, произведет успешную конкретизацию L всеми шестью перестановками. Если пользователь потребует новых решений, он никогда не получит ответ "нет", поскольку программа войдет в бесконечный цикл, пытаясь отыскать новые несуществующие перестановки. Вторая версия, перестановка2, в этой ситуации найдет только первую (идентичную) перестановку, а затем сразу зациклится. Следовательно, при использовании этих отношений требуется соблюдать осторожность.
Упражнения
3.3. Определите два предиката
четнаядлина( Список) и нечетнаядлина( Список)
таким образом, чтобы они были истинными, если их аргументом является список четной или нечетной длины соответственно. Например, список [а, b, с, d] имеет четную длину, a [a, b, c] — нечетную.
3.4. Определите отношение
обращение( Список, ОбращенныйСписок),
которое обращает списки. Например,
обращение( [a, b, c, d], [d, c, b, a] ).
3.5. Определите предикат
палиндром( Список).
Список называется палиндромом, если он читается одинаково, как слева направо, так и справа налево. Например, [м, а, д, а, м].
3.6. Определите отношение
сдвиг( Список1, Список2)
таким образом, чтобы Список2 представлял собой Список1, "циклически сдвинутый" влево на один символ. Например,
?- сдвиг( [1, 2, 3, 4, 5], L1),
сдвиг1( LI, L2)
дает
L1 = [2, 3, 4, 5, 1]
L2 = [3, 4, 5, 1, 2]
3.7. Определите отношение
перевод( Список1, Список2)
для перевода списка чисел от 0 до 9 в список соответствующих слов. Например,
перевод( [3, 5, 1, 3], [три, пять, один, три] )
Используйте в качестве вспомогательных следующие отношения:
означает( 0, нуль).
означает( 1, один).
означает( 2, два).
...
3.8. Определите отношение
подмножество( Множество, Подмножество)
где Множество и Подмножество — два списка представляющие два множества. Желательно иметь возможность использовать это отношение не только для проверки включения одного множества в другое, но и для порождения всех возможных подмножеств заданного множества. Например:
?- подмножество( [а, b, с], S ).
S = [a, b, c];
S = [b, c];
S = [c];
S = [];
S = [a, c];
S = [a];
...
3.9. Определите отношение
разбиениесписка( Список, Список1, Список2)
так, чтобы оно распределяло элементы списка между двумя списками Список1 и Список2 и чтобы эти списки были примерно одинаковой длины. Например:
разбиениесписка( [а, b, с, d, e], [a, с, e], [b, d]).
3.10. Перепишите программу об обезьяне и бананах из главы 2 таким образом, чтобы отношение
можетзавладеть( Состояние, Действия)
давало не только положительный или отрицательный ответ, но и порождало последовательность действий обезьяны, приводящую ее к успеху. Пусть Действия будет такой последовательностью, представленной в виде списка ходов:
Действия = [ перейти( дверь, окно),
передвинуть( окно, середина),
залезть, схватить ]
3.11. Определите отношение
линеаризация( Список, ЛинейныйСписок)
где Список может быть списком списков, а ЛинейныйСписок — это тот же список, но "выровненный" таким образом, что элементы его подсписков составляют один линейный список. Например:
?- линеаризация( [а, d, [с, d], [], [[[e]]], f, L).
L = [a, b, c, d, e, f]
3.3. Операторная запись (нотация)
В математике мы привыкли записывать выражения в таком виде:
2*a + b*с
где + и * — это операторы, а 2, а, b, с — аргументы. В частности, + и * называют инфиксными операторами, поскольку они появляются между своими аргументами. Такие выражения могут быть представлены в виде деревьев, как это сделано на рис. 3.6, и записаны как прологовские термы с + и * в качестве функторов:
+( *( 2, а), *( b, с) )
Рис. 3.6. Представление выражения 2*а+b*с в виде дерева.
Поскольку мы обычно предпочитаем записывать такие выражения в привычной инфиксной форме операторов, Пролог обеспечивает такое удобство. Поэтому наше выражение, записанное просто как
2*а + b*с
будет воспринято правильно. Однако это лишь внешнее представление объекта, которое будет автоматически преобразовано в обычную форму прологовских термов. Такой терм выводится пользователю снова в своей внешней инфиксной форме.
Выражения рассматриваются Прологом просто как дополнительный способ записи, при котором не вводятся какие-либо новые принципы структуризации объектов данных. Если мы напишем а + b, Пролог поймет эту запись, как если бы написали +(а, b). Для того, чтобы Пролог правильно воспринимал выражения типа а + b*с, он должен знать, что * связывает сильнее, чем +. Будем говорить, что + имеет более низкий приоритет, чем *. Поэтому верная интерпретация выражений зависит от приоритетов операторов. Например, выражение а + b*с, в принципе можно понимать и как
+( а, *( b, с) )
и как
*( +( а, b), с)
Общее правило состоит в том, что оператор с самым низким приоритетом расценивается как главный функтор терма. Если мы хотим, чтобы выражения, содержащие + и *, понимались в соответствии с обычными соглашениями, то + должен иметь более низкий приоритет, чем *. Тогда выражение а + b*с означает то же, что и а + (b*с). Если имеется в виду другая интерпретация, то это надо указать явно с помощью скобок, например (а+b)*с.
Программист может вводить свои собственные операторы. Так, например, можно определить атомы имеет и поддерживает в качестве инфиксных операторов, а затем записывать в программе факты вида:
питер имеет информацию.
пол поддерживает стол.
Эти факты в точности эквивалентны следующим:
имеет( питер, информацию).
поддерживает( пол, стол).
Программист определяет новые операторы, вводя в программу особый вид предложений, которые иногда называют директивами. Такие предложения играют роль определений новых операторов. Определение оператора должно появиться в программе раньше, чем любое выражение, использующее этот оператор. Например, оператор имеет можно определить директивой
:- op( 600, xfx, имеет).
Такая запись сообщит Прологу, что мы хотим использовать "имеет" в качестве оператора с приоритетом 600 и типом 'xfx', обозначающий одну из разновидностей инфиксного оператора. Форма спецификатора 'xfx' указывает на то, что оператор, обозначенный через 'f', располагается между аргументами, обозначенными через 'х'.
Обратите внимание на то, что определения операторов не содержат описания каких-либо операций или действий. В соответствии с принципами языка ни с одним оператором не связывается каких-либо операций над данными (за исключением особых, редких случаев). Операторы обычно используются так же, как и функторы, только для объединения объектов в структуры и не вызывают действия над данными, хотя само слово "оператор", казалось бы, должно подразумевать какое-то действие.
