Цель: Изучить механизм рекурсивной обработки списков.

Теоретические сведения:

Список - структура данных, которая включает последовательность элементов произвольной длины.
Элементы списка - константы, переменные, структуры. Список может быть пустым. Пустой список обозначается []. Если список задается перечислением термов Пролога, то он имеет вид [а,б,сб,мама]. В списке можно выделить хвост и голову.
Например: [X|Y] - список, где X - голова списка, а Y - хвост списка.
Списки могут содержать другие списки.
Например: [а,б,с,[м,м]].
Ниже приведены примеры сопоставления двух списков с целью конкретизации переменных.

Вся работа со списками основана на расщеплении списка на голову и хвост, которое используется при построении различных рекурсивных формул предикатов.

Пример 1.

/* Вхождение элемента в тот или иной список символов. */
domains
list=symbol*
predicates
member(symbol,list)
clauses
member(X,[X|_]):-!. /* правило 1 */
member(X,[_|Y]):-member(X,Y). /* правило 2 */
goal
member(a,[p,a,o,l]).
/* Yes -входит. No -не входит.*/

где [X|_] - список с головой Х, а в качестве хвоста используется анонимная переменная.
[_|Y] - список с хвостом Y, а в качестве головы может быть любой терм.
Рекурсивный процесс поиска элемента Х в списке закончится, когда Х становиться головой списка и будет выполнено правило 1.
Goal member(f,[g,h,j,f,y,y]) начнет реализовываться с выборки второго предиката, а завершиться выполнением 1-го предиката.

Пример 2.

/* Соединение списков. */
domains
word=char*
list=symbol*
predicates
append(list,list,list)
clauses
append([],L,L):-!.
append([H|L1],L2,[H|L3]):-append(L1,L2,L3).
/* ваpианты целей */
goal
append([],[a,b],X).
/* append([a,b,c],[w,z],X). */
/* append(X,Y,[a,b,c]). */

Пример 3.

/* Опpеделение длины списка. */
domains
list=symbol*
predicates
listln(list,integer)
clauses
listln([],0):-!.
listln([_|X],N):-listln(X,N1),N=N1+1.
/* Ваpиант цели */
goal listln([a,b,de],X),write(X).

Пример 4.

/* Выбоp элемента с заданным номеpом из списка. */
domains
list=symbol*
predicates
index(string,integer,list)
clauses
index(X,1,[X|_]).
index(X,N,[_|Z]):-N>1,N1=N-1,index(X,N1,Z).
/* Вариант цели */
goal index(X,5,[g,r,o,b,c,d]),write(X).

Пример 5.

/* Удалить элемент из списка. */
domains
list=symbol*
predicates
delete(string,list,list)
clauses
delete(X,[X|Y],Y):-!.
delete(X,[H|Y],[H|Z]):-delete(X,Y,Z).
/* Варианты цели */
goal delete(d,[t,v,o,l,d],X).

Пример 6.

/* Пpеобpазование стpоки в список. */
domains
list=symbol*
predicates
scan(string,list)
clauses
scan(Str,[T|L]):-fronttoken(Str,S1,S2),!,
upper_lower(S1,T),scan(S2,L).
scan(_,[]).

/* Вариант цели */
goal scan("I am do it",X).

Пример 7.

/* Сортировка списка символов. */
domains
list= symbol*
predicates
insort(list,list)
insert(symbol,list,list)
before(symbol,symbol)
clauses
insort([],[]).
insort([H|T],Ans):-insort(T,ST),
insert(H,ST,Ans).
insert(X,[H|T],[H|XT]):-before(H,X),!,
insert(X,T,XT).
insert(X,L,[X|L]).
before(A,B):- A < B.

/* Нахождение максимума в списке целых */
domains
list=integer*
predicates
max(list,integer)
maximum(list,integer,integer)
clauses
/* вариант А */
/* отсечение */
max([X|Xs],M):-maximum(Xs,X,M),!.
maximum([X|Xs],Y,M):-X<=Y,maximum(Xs,Y,M).
maximum([X|Xs],Y,M):-maximum(Xs,X,M).
maximum([],M,M):-!.
/* вариант В */
/* отсечение отсутствует */
/* max([X|Xs],M):-maximum(Xs,X,M).
maximum([X|Xs],Y,M):-X<=Y,maximum(Xs,Y,M).
maximum([X|Xs],Y,M):-maximum(Xs,X,M).
maximum([],M,M):-!. */
/* вариант цели */
/* goal max([1,2,5,17,4,0],Max) */

Порядок выполнения:

1. Рассмотреть примеры 1-7. Выполнить в режиме трассировки два примера, на выбор. Рассмотреть реализацию рекурсии в примерах.
2. Реализовать один из предложенных вариантов задания (Таблица 1).
3. Разработать правила:
   - сканирования строки и преобразование ее в список слов;
   - преобразования выражения из базиса И, ИЛИ, НЕ в базис И-НЕ.

Таблица 1 примеры заданий к лабораторной работе №2

1. Написать правило определения длинны списка.
2. Написать правило определеия номера элемента в списке.
3. Написать правило обьединения списков.
4. Написать правило подтверждения факта вхождения элемента в список.
5. Написать правило нахождения суммы элементов списка целых.
6. Написать правило нахождения максимума в списке целых.
7. Написать правило нахождения минимума в списке целых
8. Написать правило разбиения списка на N списков.
9. Написать правило вставки элемента в список с определенной позиции.
10. Написать правило преобразования списка в список, состоящий из каждого N-го элемента исходного списка.

Контрольные вопросы:

1. Назначение и использование списков. Представление cписков.
2. Особенности построения рекурсивных правил на Прологе и условия выхода из рекурсии.
3. Использование отсечения внутри рекурсивного правила.
4. Влияние порядка расположения предикатов на выполнение правила.