Существует книга о языке Lisp, в которой говорится: список – это упорядоченная последовательность элементов, где слово упорядоченная означает, что порядок перечисления элементов имеет значение. В Prolog список заключается в квадратные скобки и обычно имеет голову (head) и хвост (tail):

Список Тип Голова Хвост
[3, 4, 5, 6, 7] Integer 3 [4, 5, 6, 7]
["wo3", "ni3", "ta1"] String "wo3" ["ni3", "ta1"]
[4] Integer 4 []
[3.4, 5.6, 2.3] Real 3.4 [5.6, 2.3]

Вы можете соотнести образец переменных со списком. Например, если вы соотнесете шаблон [X|Xs] со списком [3.4, 5.6, 2.3], вы получите, что X = 3.4 и Xs = [5.6, 2.3], то есть, что переменная X соответствует голове списка, а переменная Xs соответствует хвосту. Конечно, вы можете использовать другую пару переменных вместо X и Xs в шаблоне [X|Xs]. Так, шаблоны [A|B], [X|L], [Head|Tail], [First|Rest] и [P|Q] являются эквивалентными шаблонами. Вот ещё несколько примеров соответствий для шаблона [X|Xs]:

Шаблон Список X Xs
[X|Xs] [3.4, 5.6, 2.3] 3.4 [5.6, 2.3]
[X|Xs] [5.6, 2.3] 5.6 [2.3]
[X|Xs] [2.3] 2.3 []
[X|Xs] [] Не соответствуют

Как вы можете видеть, шаблон [X|Xs] соответствует списку, содержащему как минимум один элемент. Вот шаблон, который соответствует спискам, содержащим по крайней мере два элемента:
Шаблон Список X1, X2 Xs
[X1, X2|Xs] [3, 5, 2, 7] X1 = 3, X2 = 5 [2, 7]
[X1, X2|Xs] [2, 7] X1 = 2, X2 = 7 []
[X1, X2|Xs] [7] Не соответствуют
[X1, X2|Xs] [] Не соответствуют

Теперь создадим новый консольный проект и рассмотрим пример, который будет проверять наличие числа в списке чисел. В файл main.pro добавим следующий код:
implement main

open core, console

clauses
	member(Number, [Number | _ ]).
	member(Number, [ _ | Tail]) :- member(Number,Tail).
 
	run():-
		init(),
		write("Введите список в квадратных скобках с запятыми"), nl,nl,
		write("Список -> "),
		List = read(), nl, % Список чисел
		write("Число -> "),
		Chislo = read(), nl,
		member(Chislo,List), !, % Проверка наличия числа в списке
		write(Chislo, " есть в списке ", List), nl, nl,
		_ = readchar(),
		write("Конец. Нажмите любую клавишу "),
		_ = readchar().
	run() :-
		write("Числа в списке нет "),
		_= readchar(), nl, nl,
		write("Конец. Нажмите Enter"),
		_= readchar().
end implement main

goal
	mainExe::run(main::run).
В приведенном выше коде используется предикат объекта member. Его нужно задавать в файле класса main.cl:
class main

open core

predicates
	member : (integer, integer*) nondeterm (i,i) (o,i).
	run : core::runnable.

end class main
Рассмотрим два правила, которые отвечают за поиск введенного числа в списке:
member(Number, [Number | _ ]).
member(Number, [ _ | Tail]) :- member(Number,Tail).
Словами это можно описать так:
• переменная Number принадлежит списку, если голова списка есть Number (первое правило);
• иначе Number принадлежит списку, если данная переменная принадлежит хвосту (второе правило).

Приведем еще несколько предикатов, которые реализуют различные операции над списками:

class predicates
	append:(integer*,integer*,integer*) procedure (i, i, o).
	sort:(integer*,integer*) procedure (i, o).
	insert:(integer,integer*,integer*) procedure (i, i, o).
	asc_order:(integer,integer) determ (i, i).

clauses
	/* Слияние списков: все три аргумента списки, третий список результат слияния первых двух списков */
	append([],L,L).
	append([N|L1],L2,[N|L3]):- append(L1,L2,L3).

	/* Сортировка списков: первый аргумент исходный список, второй аргумент отсортированный по возрастанию список.*/
	/*Реализована сортировка вставкой.*/
	sort([],[]).
	sort([X|T],L):-sort(T,L1), insert(X,L1,L).
	insert(X,[Y|L],[Y|L1]):- asc_order(X,Y),!, insert(X,L,L1).

	/* вставляет первый аргумент в список, заданный в качестве второго аргумента, результат третий аргумент */
	insert(X,L,[X|L]).
	/* вспомогательный предикат */
	asc_order(X,Y):- X>Y. 
Рассмотрим теперь, как подсчитать число элементов в списке, или какова длина списка. Логично определить:
• длина пустого списка [] есть 0;
• длина любого другого списка есть 1 плюс длина его хвоста.
Для реализации этого на языке Prolog создадим новый проект и в файле main.pro объявим предикат len в разделе class predicates:
len:(integer*, ;integer) procedure (i, o).
А также добавим правила, описывающие вышесказанное:
len([], 0) :- !.
len([_X|Xs], 1+S) :- len(Xs, S).
Строго говоря, [_X|Xs] сопоставляется с любым непустым списком, связывая Xs с хвостом списка. Значение головы неважно, если она есть, она может быть учтена как один элемент.

Модифицируем нашу программу добавив в неё возможность нахождения суммы и произведения элементов списка. Таким образом, код будет иметь вид:

implement main

open core, console

class predicates
	len:(integer*, integer) procedure (i, o).
	sum:(integer*, integer) procedure (i, o).
	prod:(integer*, integer) procedure (i, o).

clauses
	len([], 0) :- !.
	len([_X|Xs], 1+S) :- len(Xs, S).

	sum([], 0) :- !.
	sum([X|Xs], S+X) :- sum(Xs, S).

	prod([], 1) :- !.
	prod([X|Xs], P*X) :- prod(Xs, P).

	run():-
		init(),
		write("Введите список в квадратных скобках с запятыми"), nl,nl,
		write("Список -> "),
		List = read(), nl, % Список чисел
		_ = readchar(),
		len(List, A),
		write("Длинна списка: ", A), nl, nl,
		sum(List, S),
		write("Сумма элементов списка: ", S), nl, nl,
		prod(List, P),
		write("Произведение элементов списка: ", P), nl, nl,
		write("Конец. Нажмите любую клавишу "),
		_ = readchar().

end implement main

goal
	mainExe::run(main::run).
Давайте посмотрим, что произойдёт, если вызвать sum([3, 5, 2], S).
1. Вызов sum([3, 5, 2], S) соответствует предложению sum([X|Xs], S+X) :- sum(Xs, S), где X = 3, Xs = [5, 2], возвращая sum([3, 5, 2], S[5, 2]+3) :- sum([5, 2], S[5, 2])
2. Вызов sum([5, 2], S[5, 2]) соответствует предложению sum([X|Xs], S+X) :- sum(Xs, S), где X = 5, Xs = [2], возвращая sum([5, 2], S[2]+5) :- sum([2], S[2])
3. Вызов sum([2], S[2]) соответствует предложению sum([X|Xs], S+X) :- sum(Xs, S), где X = 2, Xs = [], возвращая sum([2], S[]+2) :- sum([], S[])
4. Вызов sum([], S[]), соответствует предложению sum([], 0) :- !, возвращая S[]=0.
Достигнув конца списка, компьютер должен откатиться к началу вычислений. Что еще хуже, он должен сохранить каждое значение переменной X, которое он найдет по пути, чтобы произвести сложение S+X во время возвращения. Традиционный путь предотвращения этого – использование накопителя. Вот определение, которое использует накопитель для суммирования элементов списка:
add([], A, A).
    add([X|Xs], A, S) :- add(Xs, X+A, S).
Давайте посмотрим, как компьютер использует второй вариант суммирования элементов списка.
1. add([3, 5, 2], 0, S) соответствует предложению add([X|Xs], A, S) :- add(Xs, X+A, S), возвращая add([5, 2], 0+3, S)
2. add([5, 2], 0+3, S) соответствует предложению add([X|Xs], A, S) :- add(Xs, X+A, S) возвращая add([2], 0+3+5, S)
3. add([2], 0+3+5, S) соответствует предложению add([X|Xs], A, S) :- add(Xs, X+A, S) возвращая add([], 0+3+5+2, S), что соответствует предложению add([], A, A), возвращая S = 10.
Предикат add можно использовать для вычисления среднего арифметического значений элементов списка чисел, задав дополнительно такое правило:

avg(Xs, A/L) :- sum(Xs, A), len(Xs, L).

                                                                       << предыдущий | следующий >>


2016-06-06 • Просмотров [ 232 ]