Объекты данных

Для отображения объектов применяются разнообразные структуры. Простые объекты программируются стандартными типами данных. Структура считается более сложной единицей. Она состоит из функтора и аргументов. Функтор есть имя связи, в которую включены аргументы. Например, структура

have(john,computer)

определяет, что Джон имеет компьютер. Функтором здесь служит have, а двумя аргументами — john и computer. Аргументами функтора могут быть константы, переменные и другие структуры. В частности, мы можем создать более сложную и более определенную структуру, например:

have(john,computer(dell,386))

Вторым аргументом мы сделали структуру со своими вариантами. Эта структура описывает конкретный компьютер. Функтором здесь является computer, а аргументами — dell и 386.

Prolog позволяет использовать объекты, содержащие другие объ­ек­ты.

Например, факты:

1) owns  (john,   book   ("From Here to Eternity", "James Jones")).

имеет (джон, книга ("Взгляд в будущее", "Джеймс Джоунс")).

2) owns (john,   horse (blackly )).

имеет(джон, лошадь(черная)).

Здесь используются сложные объекты:

book ("From Here to Eternity", "James Jones")

и

horse(blackly).

Если записать два факта:

owns (john, "From Here to Eternity").

owns (john,  blacky).

то непонятно: "blacky" — это название книги или имя лошади. Для различения объектов используется функтор. Функтор — первый элемент сложного объекта.

Рассмотрим объявление сложных объектов.

В общем случае объявление области типов объектов будет следующим:

domains

domain=alternative1(D,D...);alternative2(D,D...);

где «alternative1» и «alternative2» — равноправные, но различные функторы; (D, D...) — список типов объектов, стандартных или определяемых поль­зо­ва­те­лем.

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

domains

point=pset(real, real)

line=line(point, point)

predicates

vert(line)

horiz(line)

clauses

vert (line(pset(X, Y), pset(X, Y1))).

horiz (line(pset(X1,Y), pset(X1,Y))).

goal vert(line(pset(1,1), pset(1,2))).

yes

goal horiz(line(pset(1,1), pset(2,Y))).

Y=1

Cоставим программу, позволяющую заполнить структуру с по­мощью предикатов ввода .

domains

person = p(name, age, telno, job)

age = integer

telno, name, job = string

predicates

readperson(person)

run

goal run.

clauses

readperson(p(Name, Age, Telno, Job)) :-

write("Ваше имя ? "), readln(Name),

write("Работа ?"), readln(Job),

write("Возраст ?"), readint(Age),

write("Номер телефона ?"),readln(Telno).

run :-readperson(P), nl, write(P), nl, nl,

write("закончить ввод (д/н) "),

readchar(Ch), Ch='д' .

run :-nl, nl, write("повторите снова"), nl, nl,

run.

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

Например, определить объект, который определяет имена всех  уче­ни­ков в классе, если заранее  не известно   количество учеников в классе. Следует пошагово объявить объекты, описывающие класс.

Начнем с описания пустого класса:

classlist = empty

Далее добавим рекурсивное описание:

classlist = class (name, classelist)

Таким образом, описание объекта будет следующим:

class(peter, X).

Это означает, что «peter» будет первым элементом в «classlist». X соответствует оставшейся группе учеников без «peter». Класс из двух учеников может быть описан следующим образом:

class(peter, class(james, empty))

Класс из трех учеников:

class(andrew, class(peter, class (james, empty)))

Сложный объект:

class(name, classlist)

содержит функтор «class» и аргументы:

• name     – имя ученика в классе;
• classlist – оставшиеся ученики в классе.

Итак, область объявления будет иметь вид:

domains

classlist = class(name,classlist);empty

Для числовых данных можно задать следующую область определения:

integerlist = list(integer,integerlist);empty

Рассмотрим представление двоичных деревьев.

Двоичное дерево либо пусто, либо состоит из трех частей:

• корень;
• левое поддерево;
• правое поддерево.

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

domains

type = integer

tree = tree(type,tree,tree); nil

Рис. 12.3. Двоичное дерево

Дерево, представленное на рис. 13, выглядит как

tree(2,tree(1,nil,nil),tree(4,tree(3,nil,nil),nil)).

Определим отношение принадлежности элементу  двоичному дереву. Отношение member_tree можно определить при помощи следующих правил:

Х есть вершина дерева T, если

1) корень дерева T совпадает с Х, или

2) Х — это вершина из левого поддерева, или

3) Х — это вершина из правого поддерева.

predicates

member_tree(type,tree)

clauses

member_tree(X,tree(X,_,_)).

member_tree(X,tree(_,L,_)) :-

member_tree(X,L).

member_tree(X,tree(_,_,R)):-

member_tree(X,R).

Будем говорить, что непустое дерево упорядочено слева направо, если

• все вершины левого поддерева L меньше Х;
• все вершины правого поддерева R больше Х;
• все поддеревья упорядочены.

Улучшим процедуру поиска элемента в дереве. Чтобы найти элемент Х в дереве Т, необходимо:

1) если Х — это корень Т, то считать, что Х уже найден, иначе

2) если Х меньше, чем корень дерева Т, то искать Х в левом поддереве, иначе

3) искать Х в правом поддереве;

4) если дерево Т пусто, то поиск терпит неудачу.

domains

id=integer

tree=tree(id, tree, tree); nil

predicates

lookup(id, tree)

clauses

lookup(X, tree(X,_,_)).

lookup(X, tree(K,L,R)) :- X < K,

lookup(X,L).

lookup(X, tree(K,L,R)) :- lookup(X,R).

Покажем, как использовать lookup.

predicates

a(tree)

clauses

a(tree(2,tree(1,nil,nil),tree(4,tree(3,nil,nil),nil))).

goal a(T), lookup(1, T).

T=tree(2,tree(1,nil,nil),tree(4,tree(3,nil, nil),nil))

1 Solution

Определим отношение, позволяющее добавлять элементы в дерево. Реализуется при помощи правил:

1)    результат добавления элемента Х к пустому дереву есть дерево tree(X, nil, nil);

2)    если Х совпадает с корнем дерева Т, то Т1=Т (не допускается дублирования);

3)    если корень дерева Т больше, чем Х, то Х вносится в левое поддерево Т;

4)    если корень дерева Т меньше, чем Х, то Х вносится в правое поддерево Т.

domains

id=integer

tree=tree(id,tree,tree); nil

predicates

add(id,tree,tree)

clauses

add(X, nil, tree(X, nil, nil)).

add(X, tree(X,L,R),tree(X,L,R)).

add(X, tree(K,L,R),tree(K,L1,R)) :- K>X,

add(X,L,L1).

add(X, tree(K,L,R),tree(K,L,R1)) :- K<X,

add(X,R,R1).

goal T1=nil, add(1, T1, T2), add(2, T2, T3), add(3, T3,T4), add(5, T4, T5).

T1=nil,

T2=tree(1,nil,nil),

T3=tree(1,nil,tree(2,nil,nil)),

T4=tree(1,nil,tree(2,nil,tree(3,nil,nil))),

T5=tree(1,nil,tree(2,nil,tree(3,nil,tree(5,nil,nil))))

1 Solution