Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Застосування append

Member

Списки

По елементне введення-виведення списку

Введення-виведення списку, як терма

Довжина списку

Reverse

Застосування append

Append

Member

Списки

4.1.1. Представлення списку діаграмою

4.1.2. Виділення голови і хвоста списку

4.1.3. Шаблони списків

4.1.4. Визначення відношень через cons форму списку

4.2. Процедури обробки списків

4.3. Вбудовані предикати

4.3.1. Пості вбудовані предикати вводу-виводу

4.3.2. Процедурний зміст вбудованих предикатів вводу-виводу

4.4. Введення-виведення списків

Списки - така ж важлива структура даних у Пролозі, як і в Ліспі.

Список у Ліспі (a b c d) (1 2 (3)) записується на Пролозі [a,b,c,d] [1,2,[3]]

тобто елементи записуються в квадратних дужках через кому.

Елементами списку можуть бути будь-як терми.

Порожній список - не nil , а [ ].

4.1.1 Представлення списку діаграмою.

Список у ліспі можна представити через функцію cons

У Пролозі функції cons відповідає функтор "." (крапка).

.(a,[]) відповідає [a] , це інша форма запису або

Відповідно список [a,b,c] представляється як структура .(а ,.(b,.(c,[]) або у вигляді дерева, або діаграмою "виноградна лоза"

У ліспі:

Для вкладених списків [a,b,[c,d]]

- на верхньому рівні три елементи

- на другому рівні два елементи.

4.1.2 Виділення голови і хвоста списку

Головною операцією при роботі зі списками є розщеплення списку на голову і хвіст.

В Ліспі для цього використовуються функції car і cdr.

У Пролозі мається спеціальна форма представлення списку, називана cons-формою запису:

[Head|Tail] або [H|T] [a|[]] = [а]

При конкретизації форми списком H зіставляється з головою списку, а Т - із хвостом.

Наприклад

У такий спосіб виділяються одночасно голова списку і хвіст.

Розглянемо зіставлення двох списків:

Список 1	Список 2 [Н\|Т]
	Н	Т
[[a,b],c]	[a,b]	[c]
[1,[2,3]]		[[2,3]]
[a(c),b(d)]	a(c)	[b(d)]
[A is 2+3, B is 1+1]	A is 2+3	[B is 1+1]
	Рішення немає

Список 1	Список 2
[a,b,c,d]	[X,H,I,T]	X=a
		H=b
		T=[c,d]
[a,X\|b]	[Y,b\| _]	X=a
		Y=a
[a,b,c]	[X,Y]	Немає рішень

4.1.3 Шаблони списків.

Шаблон (зразок) списку - це форма опису безлічі (сімейства)списків, що володіють визначеними властивостями.

Наприклад:

Шаблон списку [X|Y] описує будь-який список, що складається не менш ніж з одного елемента.

Шаблон [X,Y|Z] - список, що складається не менш ніж із двох елементів.

Шаблон [b|Z] - список, першим елементом якого є b.

Шаблон [Y,X,Z] - список із трьох елементів.

Шаблони списку використовуються при описі процедур роботи зі списками.

4.1.4 Визначення відносин через cons форму списку

Задача 1: Визначити відношення replace_first, що заміняє перший елемент списку новим

Наприклад

?-replace_first([a,b,з],w,X).

X=[w,b,c]

Це відношення:

replace_first([H|T],A,[A|T]). Або

replace_first([_|T],A,[A|T]).

Що буде відповіддю для наступного питання?

?-replace_first([_|T],A,[a,b,c]).

4.2 Процедури обробки списків

Процедура в пролозі - це сукупність пропозицій з головами, представленими однаковими термами.

Для обробки списків використовуються типові процедури, аналогічні функціям ліспу.

Перевіряє приналежність елемента списку.

member(X, L)

Якщо X належить L, то істина і неправда в протилежному випадку.

З погляду декларативного змісту:

X належить списку, якщо X збігається з головою списку.

X належить списку, якщо X належить хвосту списку.

Можна записати:

member(X, [X|T]).

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

З погляду процедурного змісту - це рекурсивна процедура.

Перша пропозиція термінальна умова.

Коли хвіст буде дорівнює [] перевірка зупинитися.

Друга пропозиція рекурсивне.

Скорочення списку відбувається за рахунок узяття хвоста (cdr-рекурсія).

Приклади застосування

?-member(a, [a, b, з]).

Yes

?-member(X, [a, b, з]).

Yes

X = a

X = b

X = c

Відповісти на запитання:

?-member(a, X).

4.2.2 append

Використовується для з'єднання двох списків. тобто

append (L1, L2, L3)

L1 і L2 - списки, а L3 - їхнє з'єднання.

?-append ([a, b], [c], [a,b,c]).

Yes

Для визначення процедури append використовуємо дві пропозиції:

Якщо приєднати порожній список [] до списку L, то одержимо список L.

append([], L, L).

append([X|L1], L2, [X|L3]):- append(L1, L2, L3).

Якщо приєднати не порожній список [X|L1] до списку L2, то результатом буде список [X|L3], де L3 виходить з'єднанням L1 до L2:

|X| L1 | L2 |

----------------------------------------

|X| L3 |

З погляду процедурної семантики перша пропозиція - термінальна умова, друга - рекурсивна з хвостовою рекурсією.

Розглянемо приклади застосування

?-append([a], [b, c], L).

L=[a, b, c]

?-append([a], L, [a, b, c]).

L=[b, c]

?-append(L, [b, c], [a, b, c]).

L=[a]

Можна використовувати для розбивки

?-append(L1, L2, [a, b, c]).

L1=[]

L2=[a, b, c];

L1=[a]

L2=[b, c];

L1=[a, b]

L2=[c];

L1=[a, b, c]

L2=[]

Процедуру арреnd можна використовувати для пошуку комбінацій елементів.

Наприклад можна виділити списки ліворуч і праворуч від елемента

?-append(L, [3|R], [1, 2, 3, 4, 5]).

L=[1, 2]

R=[4, 5]

Можна видалити усе, що випливає за даним елементом і цей елемент теж:

?-L1=[a, b, c, d, e], append(L2, [c|_], L1).

L1=[a, b, c, d, e]

L2=[a, b]

Можна визначити процедуру , що виділяє останній елемент у списку:

last(X, L):-append(_, [X], L).

4.2.4 reverse

Процедура reverse звертає список.

Порожній список після звертання - порожній.

reverse([], []).

Звернути список [X|L1] і одержати список L2 можна, якщо звернути список L1 у L3 і в хвіст йому додати X

reverse([X|L1], L2):-reverse(L1, L3),

append( L3, [X], L2).

reverse([X|L1], L2):-reverse(L1, L3),

append( L3, [X], L2).

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

<== попередня сторінка	\|	наступна сторінка ==>
І ВІДМІНА	\|	Довжина списку

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.008 сек.