Листинг 6.1.6.Деление списка

 

domains

middle=integer

list=integer*

predicates

split(middle,list,list,list)

clauses

split(_,[],[],[]).

Split(Middle,[Head|Tail],[Head|L1],L2):-

Head<=Middle,

Split(Middle,Tail,L1,L2).

Split(Middle,[Head|Tail],L1,[Head|L2]):-

Head>Middle,

Split(Middle,Tail,L1,L2).

Middle-компаратор-элемент данных

L-исходный список

L1,L2 – подсписки, получающиеся в результате деления

списка L.

Алгоритм

Очередной элемент извлекается из списка при помощи метода разделения списка на голову и хвост, а потом голова сравнивается с компаратором Middle.Если значение этого элемента <= Middle,то элемент помещается в список L1,иначе - в список L2. Элементы и компаратор должны быть одного типа.

Goal: split(12,[96,2,8],L1,L2)

Ответ:L1=[2,8]

L2=[96]

 

Листинг 6.1.7. Удаление элемента из списка

 

domains

list=integer*

predicates

delete(integer,list,list)

clauses

(1) delete(X,[X|Tail],Tail).

(2) delete(X,[Y|Tail],[Y|Tail1]):-

delete(X,Tail,Tail1).

 

(1) Если X – голова списка, то результат –хвост этого списка.

(2) Если X – в хвосте, то его надо удалить оттуда.

Отношение delete по своей природе – недетерминировано и обратимо.

Цели:

? delete(5,[1,8,5,7,5],L)

Ответ L=[1,8,7,5] -удаление первой 5

L=[1,8,5,7] –удаление последней 5

 

Если в списке содержится несколько вхождений элемента X, то delete может исключить их все при помощи возврата и дать нам различные варианты удалений, каждый раз удаляя лишь одно вхождение X.Остальные вхождения остаются в неприкосновенности (недетерминированность). При попытке исключить элемент, отсутствующий в списке, отношение delete потерпит неудачу

 

? delete(5,L,[1,8,7]) – используем для вставки элемента (обратимость)

Ответ L=[5,1,8,7]

L=[1,5,8,7]

L=[1,8,5,7]

L=[1,8,7,5] 4Solution

Отношение delete – обратимое, его можно использовать в обратном направлении для того, чтобы добавить элементы в список, вставляя их в произвольные места списка. Для этого зададим вопрос:”Каким должен быть список L,чтобы после удаления из него элемента “5” получить список [1,8,7] ”?

Отношение delete можно использовать для проверки на принадлежность списку.

Идея:X принадлежит списку, если этот X можно из списка удалить:

member(X,List):-

delete(X,List,_).

Delete можно использовать для построения всех возможных перестановок списка .Для этого надо включить отношение change с двумя аргументами

Листинг 6.1.8 Перестанова элементов списка с помощью удаления

domains

list=integer*

predicates

delete(integer,list,list)

change(list,list)

clauses

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

delete(X,[Y|Tail],[Y|Tail1]):-

delete(X,Tail,Tail1).

change([],[]).

change(L,[X|P]):-

delete(X,L,L1),

change(L1,P).

? (change([3,5,6],L)---L=[3,5,6] L=[3,6,5] L=[5,3,6] L=[5,6,3]

L=[6,3,5] L=6,5,3] 6 Solutions

Но надо быть осторожным ( при change(L,[3,5,6])—произойдет зацикливание)