top-shop.ru
Estel Curex Therapy
Эффективная работа со списками

Встроенные предикаты для работы со списками

В предыдущих главах Вам уже встречалось практическое использование списков в программах на языке Пролог. GNU Prolog обладает набором встроенных предикатов, для работы со списками (списки - очень важная часть языков логического программирования). В списке могут быть выделены "голова" (первый элемент) и "хвост" - все остальное. Вообще - список, это перечисление некоторых элементов:
| ?- X = [1, b, 4], Y = [barra, borro, burro].

X = [1,b,4]
Y = [barra,borro,burro]

(10 ms) yes
| ?- [X|Y] = [2,5,8,9].

X = 2
Y = [5,8,9]

yes
| ?- 
"Дуальность предикатов": Если Вы задаете "входной" и "выходной" список, то предикат просто проверяет их на соответствие своему преобразованию. Если один из списков - неинициализированная переменная, то генерируется набор списков, соотв. заданному преобразованию.
  1. Предикат append(List1, List2, List12) является успешным, если выполняет конкатенацию списков List1 и List2 в список List12 (Успешен, если заданы списки соответствующие преобразованию).
    | ?- X = [1, b, 4], Y = [barra, borro, burro], append(X,Y,Z).
    
    X = [1,b,4]
    Y = [barra,borro,burro]
    Z = [1,b,4,barra,borro,burro]
    
    yes
    | ?- 
  2. Предикат member(Element, List) успешен, если Element есть в списке List. А также может использоваться для организации перебора.
    | ?- member(barra,[barra,burro,borro]). 
    
    true ? ;
    
    no
    | ?- X = [1, b, 4], member(1,X).
    
    X = [1,b,4] ? ;
    
    (10 ms) no
    | ?-
  3. Встроенный предикат reverse(List1, List2) порождает список List2 из элементов списка List1, переставленных в обратном порядке. Успешен, если заданы списки соответствующие преобразованию.
    | ?- X = [1, b, 4], reverse(X,Y).
    
    X = [1,b,4]
    Y = [4,b,1]
    
    yes
    | ?- 
  4. delete(List1, Element, List2) порождает список List2 из элементов списка List1 за исключением всех элементов Element. Успешен, если заданы списки соответствующие преобразованию.
    GNU Prolog 1.2.16
    By Daniel Diaz
    Copyright (C) 1999-2002 Daniel Diaz
    | ?- X = [1,1,2,2,3,3,4,4], delete(X,2,Y).
    
    X = [1,1,2,2,3,3,4,4]
    Y = [1,1,3,3,4,4]
    
    yes
    | ?- X = [1,2,3], Y=[1,3], delete(X,2,Y).
    
    X = [1,2,3]
    Y = [1,3]
    
    (10 ms) yes
    | ?- X = [1,2,3], Y=[1,3,2], delete(X,2,Y).
    
    no
    | ?- 
    
  5. select(Element, List1, List2) Удаляет одно вхождение элемента и порождает дочерний список. Может использоваться для перебора вариантов. Успешен, если заданы списки соответствующие преобразованию.
    | ?- X = [1,2,3,4,4,4,5,6], select(4,X,Y).
    
    X = [1,2,3,4,4,4,5,6]
    Y = [1,2,3,4,4,5,6] ? 
  6. permutation(List1, List2)Успешен, если List2 есть перестановка списка List1. Предикат может использоваться для генерации перестановок.
    | ?- X = [1,2,3], permutation(X,Y).
    
    X = [1,2,3]
    Y = [1,2,3] ? ;
    
    X = [1,2,3]
    Y = [1,3,2] ? ;
    
    X = [1,2,3]
    Y = [2,1,3] ? ;
    
    X = [1,2,3]
    Y = [2,3,1] ? ;
    
    X = [1,2,3]
    Y = [3,1,2] ? ;
    
    X = [1,2,3]
    Y = [3,2,1] ? ;
    
    no
    | ?- X = [1,2,3], Y = [3,2,1], permutation(X,Y).
    
    X = [1,2,3]
    Y = [3,2,1] ? ;
    
    no
    | ?- 
  7. prefix(Prefix, List) Успешен, если Prefix - начало списка List. Если Prefix - переменная, то генерируется набор префиксов (списков), включая "пустой список" и весь исходный список "целиком".
    GNU Prolog 1.2.16
    By Daniel Diaz
    Copyright (C) 1999-2002 Daniel Diaz
    | ?- X = [5,4,1,2,4],prefix(Y,X).
    
    X = [5,4,1,2,4]
    Y = [] ? ;
    
    X = [5,4,1,2,4]
    Y = [5] ? ;
    
    X = [5,4,1,2,4]
    Y = [5,4] ? ;
    
    X = [5,4,1,2,4]
    Y = [5,4,1] ? ;
    
    X = [5,4,1,2,4]
    Y = [5,4,1,2] ? ;
    
    X = [5,4,1,2,4]
    Y = [5,4,1,2,4] ? ;
    
    (30 ms) no
    | ?- 
  8. Аналогично, работает suffix(Suffix, List) (только работает с "концом" списка - суффиксом).
    GNU Prolog 1.2.16
    By Daniel Diaz
    Copyright (C) 1999-2002 Daniel Diaz
    | ?- X = [5,4,1,2,4], suffix(Y,X).
    
    X = [5,4,1,2,4]
    Y = [5,4,1,2,4] ? ;
    
    X = [5,4,1,2,4]
    Y = [4,1,2,4] ? ;
    
    X = [5,4,1,2,4]
    Y = [1,2,4] ? ;
    
    X = [5,4,1,2,4]
    Y = [2,4] ? ;
    
    X = [5,4,1,2,4]
    Y = [4] ? ;
    
    X = [5,4,1,2,4]
    Y = [] ? ;
    
    (10 ms) no
    | ?- 
  9. sublist(List1, List2) - успешен, если List2 есть суб-список List1. Если дать неконкретизированную переменную, сгенерирует набор подсписков.
  10. last(List,Element) - успешен, если заданный элемент последний в списке. Если дать непроинициализированную переменную - извлечет последний элемент:
    | ?- X = [1,3,4], last(X,Y).
    
    X = [1,3,4]
    Y = 4
    
    (10 ms) yes
    | ?- 
  11. length(List, Length) - успешен, если Length - длинна списка. Если дать не конкретезированную переменную, предикат вернет длинну списка.
    GNU Prolog 1.2.16
    By Daniel Diaz
    Copyright (C) 1999-2002 Daniel Diaz
    | ?- X = [1,2,3], length(X,3).
    
    X = [1,2,3]
    
    yes
    | ?- X = [1,2,3], length(X,Y).
    
    X = [1,2,3]
    Y = 3
    
    yes
    | ?-
  12. nth(N, List, Element) - работа с N - элементом списка. Успешен если он Element, если его дать не конкретизированной переменной - вернет заданный элемент списка:
    GNU Prolog 1.2.16
    By Daniel Diaz
    Copyright (C) 1999-2002 Daniel Diaz
    | ?- X = [fdasd, burro, barra, borro], nth(3,X,Y).
    
    X = [fdasd,burro,barra,borro]
    Y = barra
    
    yes
    | ?- X = [fdasd, burro, barra, borro], nth(3,X,barra).
    
    X = [fdasd,burro,barra,borro]
    
    yes
    | ?- 
  13. min_list(List, Min) успешен если Min наименьшее число в List.
    max_list(List, Max) успешен если Max наибольшее число в List.
    sum_list(List, Sum) успешен если Sum сумма всех элементов в List.

    Если дать не конкретизированную переменную - поиск искомой величины!

    | ?- A = [1,2,3,4], min_list(A,B), max_list(A,C), sum_list(A,D).
    
    A = [1,2,3,4]
    B = 1
    C = 4
    D = 10
    
    yes
    | ?- 
  14. sort(List1, List2) успешен, если List2 есть отсортированный по возрастанию список List1, причем дублирующиеся элементы объединяются в один! Если Вам не требуется объединение элементов - используйте sort0(List1, List2):
    GNU Prolog 1.2.16
    By Daniel Diaz
    Copyright (C) 1999-2002 Daniel Diaz
    | ?- X = [4,2,2,1,3],sort(X,Y).
    
    X = [4,2,2,1,3]
    Y = [1,2,3,4]
    
    yes
    | ?- X = [4,2,2,1,3],sort0(X,Y).
    
    X = [4,2,2,1,3]
    Y = [1,2,2,3,4]
    
    yes
    | ?- 
  15. keysort(List1, List2) succeeds if List2 is the sorted list of List1 according to the keys. The list List1 consists of items of the form Key-Value. These items are sorted according to the value of Key yielding the List2. Duplicate keys are not merged. This predicate is stable, i.e. if K-A occurs before K-B in the input, then K-A will occur before K-B in the output.
    GNU Prolog 1.2.16
    By Daniel Diaz
    Copyright (C) 1999-2002 Daniel Diaz
    | ?- X = [1-2,3-4,2-1,5-6],keysort(X,Y).
    
    X = [1-2,3-4,2-1,5-6]
    Y = [1-2,2-1,3-4,5-6]
    
    yes
    | ?- 

bagof, setof и findall

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

Однако, есть возможность, собрать все решения в список. Встроенные предикаты bagof (набор) и setof (множество) обеспечивают такую возможность. Вместо них иногда используют findall (найти все).

Например, у нас есть набор следующих фактов:
GNU Prolog 1.2.16
By Daniel Diaz
Copyright (C) 1999-2002 Daniel Diaz
| ?- [user].
compiling user for byte code...
pol(smit,man).
pol(jhon,man).
pol(barbara,woman).
pol(helen, woman).

user compiled, 5 lines read - 515 bytes written, 54734 ms

(1469 ms) yes
| ?- bagof(X,pol(X,man),C).

C = [smit,jhon]

yes
| ?- bagof(X,pol(X,woman),C).

C = [barbara,helen]

yes
| ?- bagof(X,pol(X,Y),C).

C = [smit,jhon]
Y = man ? ;

C = [barbara,helen]
Y = woman

yes
| ?- 
Таким образом, цель bagof(X,p,C) порождает список L всех объектов X, удовлетворяющих цели p. Если ни одного решения нет, то цель просто терпит неуспех. Если один и тот же X, найден многократно, то все его экземпляры будут занесены в список L (повторяющиеся элементы списка).

setof(X,p,C) порождает отсортированный (упорядоченный) список решений, в котором повторяющиеся решения объединены в один элемент. Упорядочение происхлдит по алфавиту, или по отношению '<', если элементы списка - числа. Если элементы списка - структуры, то они упорядочиваются по своим главным функторам.

| ?- setof(X,pol(X,man),C).

C = [jhon,smit]

yes
| ?- 
Еще одним предикатом этого семейства, аналогичным bagof, является findall. Он отличается от bagof тем, что собирает в список все объекты X, не обращая внимание на отличающиеся для них конкретизации других элементов:
| ?- findall(X,pol(X,Y),C).

C = [smit,jhon,barbara,helen]

yes
| ?- 
Если не существует ни одного объекта X, удовлетворяющего p, то findall, все равно имеет успех, и возвращает пустой список.

Представление множеств

Списки можно применять для представления множеств, хотя и существует некоторое различие между этими понятиями: порядок элементов множества не существенен, в то время как для списка этот порядок имеет значение; кроме того, один и тот же объект может встретиться в списке несколько раз. Однако, наиболее часто используемые операции над списками аналогичны операциям над множествами.

Работа с головой и хвостом списка

Список можно рассматривать как структуру, состоящую из двух частей:
  1. Первый элемент, называемый головой списка;
  2. Остальная часть списка, называемая хвостом;
Голова соединяется с хвостом с помощью специального функтора - точки.
| ?- findall(X,pol(X,Y),C), Z = .(fray,C).

C = [smit,jhon,barbara,helen]
Z = [fray,smit,jhon,barbara,helen]

yes
| ?- findall(X,pol(X,Y),C), Z = .(fray,C), L = [pek|Z].

C = [smit,jhon,barbara,helen]
L = [pek,fray,smit,jhon,barbara,helen]
Z = [fray,smit,jhon,barbara,helen]

yes
| ?- 
Блог изучающего Пролог

содержание