Листинг6.1.2. Определение длины списка
domains
list=integer*
predicates
length_of(list,integer)
clauses
length_of([],0).
length_of([_|T],L):-
length_of(T,TailLength),
L=TailLength+1.
Терминальный случай- длина пустого списка =0.
Нетерминальный случай-правило рекурсии – длина любого
другого списка равна 1+длина его хвоста.
Goal: clearwindow, length_of([5,7,1,4],L).
При нисходящем построении рекурсии решение откладывается до тех пор, пока не станет известен последнийчлен списка
Length_of([5,7,1,4]) L1=L2+1=4
length_of([7,1,4],L2) L2=L3+1=3
length_of([1,4],L3) L3=L4+1=2
length_of([4],L4) L4=0+1=1
length_of([],0) 0
Ответ: L=4 1 Solution
Замечание
Отличия от процедурных языков:
1. Вместо изменения значения переменной с помощью присваивания, повторно вызываем функцию с измененными значениями ее параметров
2. Вместо использования безусловного перехода и итерации применяем условное выражение и рекурсию.
3.Плохо то, что для организации рекурсии требуется большой стек, а механизм связывания, используемый для адресации позиции текущей переменной в этом стеке, может замедлить исполнение для фон-неймановских машин (сейчас, правда, это не так важно).
Листинг 6.1.3.Модификация списка (программа работает со списком и добавляет 1 к каждому элементу списка)
domains
list=integer*
predicates
add1(list,list)
clauses
add1([],[]).
add1([Head|Tail],[Head1|Tail1]):-
Head1=Head+1,
add1(Tail,Tail1).
goal
add1([10,21,3,74],NewList),
write(NewList).
(ответ-[11,22,4,75])
стек: 75 из стека идет обратная раскрутка
74 [74],[75]
4 [3,74],[4,75]
3 [21,3,75],[22,4,75]
22 [10,21,3,74],[11,22,4,75] и печать
Ответ: NewList=[11,22,4,75]
Объединение списов (конкатенация)
Особенность Пролога заключается в том, что задавая утверждения для предиката с логической точки зрения, эти утверждения могут быть выполнены с процедурной точки зрения.
То есть здесь присутствует двойственность, и эту двойственность надо увидеть и учесть. Воспользуемся рекурсией с процедурной точки зрения для объединения списков.
Определим предикат append с тремя аргументами
append(List1,List2,List3)
List1, List2 – исходные списки,
List3- список, получающийся при их объединении.
Например, append([1,2],[3,4],[1,2,3,4])-true
append([1,2],[3,4],[1,2,1,3,4])-false
Определим отношение append,как содержащее два случая в зависимости от вида List1:
1. Если List1-пуст, то второй и третий аргументы представляют собой один и тот же список (назовем его List2):
append([],List2,List2).
2. Если List1 –не пуст, то он имеет голову и хвост [H|L1], и можно объединить List1 и List2 для формирования List3,сделав голову List1 головой List3.
Хвост List3 состоит из объединения остатка List1 и всего List2:
append(H|L1],List2,[H|L3]:-
append(L1,List2,L3).
Листинг 6.1.4. Программа объединения списков
domains
list=integer*
predicates
append(list,list,list)
clauses
append([],List,List).
append([H|L1],List2,[H|L3]):-
append(L1,List2,L3).
Поставьте цели:
1.?append([1,2],[3,4,5],L).
Ответ:L=[1,2,3,4,5] 1Solution
2.?append([1,2],[3],L),append(L,L,LL).
Ответ: L=[1,2,3]
LL=[1,2,3,1,2,3] 1Solution
3.?append([1,2],L,[1,2,5,6]) –разность между списками
Ответ:L=[5,6] 1Solution
4.? append(L,[5,6],[1,2,5,6] –разность между списками
Ответ L=[1,2] 1Solution
Замечание для 3 и 4:
Первые два аргумента отношения append не симметричны, поэтому имеется два различных варианта нахождения разности между двумя списками.
Рассматривая append с декларативной точки зрения мы определяем отношение между тремя списками. Это отношение сохранится даже если List1 и List3 известны, а List2 –нет. Оно также справедливо, если известен только List3.
Таким образом, предикат append определяет отношение между входным набором и выходным набором таким образом, что отношение применимо в обоих направлениях Задавая отношения вы можете спросить систему
–Какой выход соответствует данному входу?
-Какой вход соответствует данному выходу?
Состояние аргументов при вызове предиката называется потоком параметров. Аргумент, который присваивается или назначается в момент вызова, называется входным аргументом и обозначается буквой”i”; а свободный аргумент – это выходной аргумент, и он обозначается буквой “o”.
У предиката append есть возможность работать с разными потоками параметров в зависимости от того, какие исходные данные ему зададут. Если утверждение Пролога может быть использовано с различными потоками параметров, оно называется обратимым утверждением. Обратимые утверждения имеют дополнительные преимущества, и их создание добавляет “мощности” предикатам.
Использование программы append в обратном направлении:
Goal: (L1,L2,[1,2,3,6]).
Ответ:
L1=[] L2=[1,2,3,6]
L1=[1] L2=[2,3,6]
L1=[1,2] L2=[3,6]
L1=[1,2,3] L2=[6]
L1=[1,2,3,6] L2=[] 5 Solutions
Если бы объекты были не числа, а дни недели,то:
domains
list=string*
Goal: append(Before,[friday|After],[monday,tuesday,wednesday,thursday,friday,saturday,sunday]).
Ответ:
Before=(“monday”,”tuesday”,’wednesday’,”thursday”]
After=[“saturday”,”sunday”]
1 solution
goal: append(L1,[b|_],[a,b,c])
ответ
L1=[“a”] 1Solution
goal: L1=[a,b,c,d,f,f,m],append(L2,[f|_],L1)
ответ:
L1=[a,b,c,d,f,f,m] L2=[a,b,c,d]
L1=[a,b,c,d,f,f,m] L2=[a,b,c,d,f]
2 solutions
(удаление всего, что стоит следом за f)
Замечание: логические программы не содержат алгоритма, для решения логической задачи достаточно точного логического описания. Так как в логической программе последовательность и способ выполнения программы не фиксируется, как при описании алгоритма, программы в принципе могут работать в обоих направлениях. Прологовская программа может на основе исходных данных вычислить результат, но с тем же успехом без дополнительного программирования на основе результата –вычислить исходные данные.
(В традиционных языках программирования данные обрабатываются в порядке, задаваемом описанием алгоритма. Это определяет несимметричность функции, то есть вычислить значения аргументов, исходя из значения функции нельзя!)
Ранее мы ввели предикат member.Такие предикаты как member, sublist, prefix могут быть определены в терминах предиката append, если последний использовать не для объединения, а для разделения(расщепления) списков.
Попробуем определить отношение принадлежности, используя конкатенацию.
member(X,L):-
append(L1,[X|L2],L).
X принадлежит L, если список L можно разбить на два списка L1 и L2 так, чтобы элемент X являлся головой списка L2. Поставим цель ? member(2,[1,3,2,5,7]). Предикат member будет просматривать список L элемент за элементом до тех пор, пока не встретит 2, или пока не кончится список. Ответ: yes –no
Листинг 6.1.5.Определение принадлежности через объединение
domains
list=integer*
predicates
member(integer,list)
return false">ссылка скрытаappend(list,list,list)
clauses
member(X,L):-
append(L1,[X|L2],L).
append([],L,L).
append([X|L1],L2,[X|L3]):-
append(L1,L2,L3).
Попытайтесь самостоятельно использовать предикат append для нахождения префиксов, суффиксов, подсписков.