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

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

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

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

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

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

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

[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. Соединение двух списков.

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

image001 image001

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

  • присоединение пустого списка [] к другому списку 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. Перестановки.

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

image002 

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).
  1. Дайте определение списку.
  2. Что означает запись:
    domains 
    k=integer
    p=k*
    r=p*
     
  3. Поясните работу предиката findall.
  4. Напишите программу, сортирующий список по методу пузырька.
  5. Дайте определение операции отсечения головы списку.
  6. Каким образом решить задачу, если необходимо в списке объединять разнородные объекты?
  7. Промоделировать массив 3*10 с помощью списка.
  8. Прочитайте декларативно и процедурно определение предиката member.
  9. Как будет описан в domains список, состоящий из букв и чисел?
  10. Определите  список через двоичное дерево.
  11. Сравните описание списка  в Prolog и Pascal.
  12. Сформулируйте алгоритм решения задачи со списками.
  13. Выделите в рекурсивном определении списка граничное условие, общее условие.
  14. Напишите программу, преобразующую список целых чисел в двоичное дерево.