РАЗДЕЛЕНИЕ СПИСКА НА ДВА

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

Рассмотрим предикат div1, аргументами которого являются элемент данных и три списка:

div1(Middle,L,L1,L2)

Элемент Middle здесь является разделителем, L — это исходный список, а L1 и L2 — подсписки, получающиеся в результате деления списка L. Если элемент исходного списка меньше или равен Middle, то он помещается в список L1; если больше, то в список L2.

Предположим, что вначале значением переменной Middle является число 40, переменной L присвоен список [30,50,20,25,65,95], а переменные L1 и L2 свободные.

div1(40,[30,50,20,25,65,95],L1,L2)

Идея разделения следующая:

1. Извлекаем из списка голову H, а потом сравнивается с элементом Middle.

2. Если значение H меньше или равно значению Middle, то элемент помещается в список L1, в противном случае — в список L2.

3. Повторяем эту последовательность действий для хвоста.

В результате применения правила к списку [30,50,20,25,65,95] значениями списков L1 и L2 станут соответственно [30,20,25] и [50,65,95].

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

div1(_,[],[],[]):-!.

div1(Middle,[H|T],[H|T1],L2) :-

H <= Middle,!,

div1(Middle,T,T1,L2).

div1(Middle,[H|T],L1,[H|T2]) :-

div1(Middle,T,L1,T2).

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

Приведенное правило годится для любых базовых типов данных. Если список состоит из символических имен, то разделение будет происходить исходя из старшинства ASCII кодов.

/* Программа 7.1 «Деление списка». */

/* Назначение: Разделение списка на два. */

domains

list = integer *

predicates

div1(integer,list,list,list)

clauses

div1(_,[],[],[]):-!.

div1(Middle,[H|T],[H|T1],L2) :-

H <= Middle,

div1(Middle,T,T1,L2).

div1(Middle,[H|T],L1,[H|T2]) :-

div1(Middle,T,L1,T2).

/* Конец программы */