Список Голова Хвост

[1,2,3,4,5] 1 [2,3,4,5]

[6.9,4.3,8.4,1.2] 6.9 [4.3,8.4,1.2]

[cat,dog,horse] cat [dog,horse]

['S','K','Y'] 'S' ['K','Y']

["PIG"] "PIG" []

[] не определена не определен

_____________________________________________________________

Операции над списками.

Рассмотрим основные предикаты для обработки списков.

Вывод элементов списка.

Необходимо описать предикат, который позволял бы выводить последовательно все элементы списка, по одному в каждой строке. Применим для этого рекурсию. Пусть writelist(L) - предикат, реализующий вывод списка, L - список:

writelist([]).

writelist([H|T]):- write(H), nl, writelist(T).

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

Второе предложение задает вывод головы списка, переход к новой строке
(nl -стандартный предикат перевода строки) и рекурсивный вызов предиката, выводящего хвост списка.

Проверка принадлежности элемента списку (member).

Отношение принадлежности записывается в виде двух предложений:

member(X,[X|Tail]).

member(X,[_|Tail]) :- member(X,Tail).

Оно основано на следующих соображениях: либо X - голова списка, либо X принадлежит хвосту этого списка.

Например запишем предикат

member(X,L).

Здесь L - некоторый список, Х - объект того же типа, что и элементы списка L. Составление предиката может быть основано на следующих соображениях: X есть либо голова списка L, либо X принадлежит хвосту. Это может быть записано в виде двух предложений, первое из которых есть простой факт, ограничивающий вычисления, а второй - рекурсивное правило:

member(X, [X|_]).

member(X, [_|T]):- member(X,T).

Напомним, что знаком подчерка здесь обозначена анонимная переменная, значение которой в данном предложении неважно.

Работа предиката следующая: при каждом рекурсивном вызове список будет короче, т.к. аргументом заголовка является структура[_|T], а в рекурсивном вызове - список Т. Рекурсивные вызовы продолжаются до тех пор, пока не будет достигнуто совпадение значения переменной X с головой списка Т, или если окажется пустой список, тогда предикат завершается ложно, так как для пустого списка нет своего правила.

Обычно этот предикат используют в двух вариантах:

1) Переменная X неконкретизирована, а список L конкретизирован. В этом случае в результате работы предиката переменная X конкретизируется элементом списка L. Используя механизм возвратов, можно переменной X последовательно придавать значения всех элементов списка L.

2) Переменная X и список L конкретизированы. Значением предиката будет “истина”, если X совпадает с одним из элементов списка, и "ложь" в противном случае.