Программирование списков

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

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

Например, перечисление объектов: Мери, Джон, Том, Анн можно записать так:

["Мери", "Джон", "Том", "Анн"]

Элементами списка могут быть любые структуры.

Первый элемент называется головой списка, остальная часть — хвостом. Например, для списка

[a, b, c, d, e]

a — это голова, а хвостом является список [b, c, d, e]. Для представления пустого списка используется [].

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

L=[a|[b, с]]=[a, b|[c]]=[a, b, c|[]]

Можно определить список рекурсивно.

Список — это структура данных, определяемая следующим образом:

• список является пустым,
• либо состоящим из двух компонентов, называемых головой и хвостом списка. Головой списка может быть элемент любого типа, а хвост должен быть, в свою очередь, списком.

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

• из факта, ограничивающего рекурсию и описывающего операцию для пусто­го списка;
• из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста (в голове правила), через операцию над хвостом (в подцели).

Перед использованием списка в программе его необходимо описать.

domains

element= integer % тип данных элементов списка

list= element*

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

domains

list1=integer*

list2=string*

predicates

member (integer, list1)

member (string,  list2)

Предположим, что есть база данных с фактами о разных людях, и каждый факт связывает имя человека и его массу. Если необходимо объединить данные о массе всех людей в единой списковой переменной L, то  используется стандартный предикат findall.

domains

list=integer*

predicates

person(string,integer)

clauses

person(dan,70).

person(ann,80).

person(ben,77).

goal findall (X, person(_,X), L), write(L).

[70,80,77] L=[70,80,77]

1 Solution

Пример 1. Принадлежность элемента списку.

Составление программы для отношения принадлежности может быть основано на следующих соображениях:

а) X есть голова L, либо

б) X принадлежит хвосту L

predicates

member (type, list)

clauses

member (H,[H|T]).

member (H,[Y|T]):- member (H,T).

Применять member можно в двух направлениях

goal member (1,[2,3,1,2]).

yes

goal member (X,[1,2,3]).

X=1

X=2

X=3

3 Solutions

Пример 2. Соединение двух списков.

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

Необходимо рассмотреть два случая:

• присоединение пустого списка [] к другому списку L есть тот же самый список L.
• присоединение к списку [H|T] списка P есть присоединение хвоста T к списку P и к результату добавить голову H.

predicates

append (list, list, list)

clauses

append ([],L,L).

append ([H|T],P,[H|Y]): - append (T,P,Y).

goal append ([1,2],[3,4],X).

X=[1,2,3,4]

goal append (X,[3|Y],[1,2,3,4,5]).

X=[1,2]

Y=[4,5]

goal append (_,[X,3,Y|_],[1,2,3,4,5,6]).

X=2

Y=4

goal append (X,[3,4,5|_],[1,2,3,4,5,6,7]).

X=[1,2]

Пример 3. Удаление элемента из списка.

predicates

delete(type, list, list)

Отношение delete можно определить аналогично принадлежности:

• если Х является головой списка, тогда результатом удаления будет хвост этого списка;
• если Х находится в хвосте списка, тогда его нужно удалить оттуда.

clauses

delete (X,[X|T],T).

delete (X,[Y|T],[Y|T1]): -

delete (X,T,T1).

Отношение delete недетерминированно.

goal  delete (1,[1,2,1,1],L).

L=[2,1,1]

L=[1,2,1]

L=[1,2,1]

3 Solutions

Пример 4. Перестановки.

Иногда бывает полезно построить все перестановки некоторого заданного списка. Для решения удобно воспользоваться графическим представлением:

predicates

reverse (list, list)

insert (type, list, list)

clauses

reverse ([],[]).

reverse ([X|L],P): - reverse (L,L1),

insert (X,L1,P).

insert (X,List,Biglist): -

delete (X,Biglist,List).

goal reverse ([1,2,3],L).

L=[1,2,3]

L=[1,3,2]

L=[2,1,3]

L=[2,3,1]

L=[3,1,2]

L=[3,2,1]

6 Solutions

Пример 5. Печать элементов списка.

predicates

write_list (list)

clauses

write_list ([]).

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

write_list (T).

Предыдущая - Следующая >>

Tweet

Читайте также:

• Основные понятия представления знаний
• Логическая модель представления знаний
• Продукционная модель представления знаний
• Сетевая модель представления знаний

Добавить комментарий

Имя (обязательное)

E-Mail (обязательное)

Подписаться на уведомления о новых комментариях

Обновить

Отправить

Отменить