Пролог; если и (остановка) рекурсия - PullRequest
Новая
       14

Пролог; если и (остановка) рекурсия

2 голосов
/ 07 марта 2011

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

Я определил правило: 

is_on(Item, [Ah|At]) :- Ah = Item; is_on(Item, At).

Это проверяет, есть ли «Элемент» в списке X или нет. Поэтому я подумал, что могу расширить это, чтобы определить предикат filter_double: 

filter_doubles([Ah|At], Result) :-
    (not(is_on(Ah, At)) ->
        Result = [Ah|Result]
    ;
        filter_doubles(At, Result)
    ).

Это имело для меня смысл: если Ah не встречается в остальной части списка (его хвост), то добавьте a в начало результата, используя построение списка, в противном случае выполните повторение по остальной части списка. Видимо Пролог думает иначе: 

47 ?- filter_doubles([1,2,3,3,4,2,1,1], Z).
Z = [3|**].

Думаю ли я об этом слишком настойчиво?

Ответы [ 2 ]

3 голосов
/ 07 марта 2011

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

Итак, ваше правило is_on (которое я переименовал contains) обычно пишется следующим образом: 

contains(Item, [Item | _]).
contains(Item, [_ | Tail]) :- contains(Item, Tail).

Предикат filter_double может подвергаться аналогичному переписыванию. Прежде всего, пустой список будет соответствовать пустому результату. 

filter_doubles([], []).

Затем, если Item встречается в Rest списка, вы повторяетесь по Rest списка, отбрасывая это вхождение Item. 

filter_doubles([Item | Rest], Result) :-
    contains(Item, Rest), !,
    filter_doubles(Rest, Result).

Наконец, если Item не встречается в Rest списка (поскольку предыдущее правило уже проверено для этого случая), вы можете поместить это Item в начало результата используя построение списка, и приступите к фильтрации Rest списка. 

filter_doubles([Item | Rest], [Item | Tail]) :- filter_doubles(Rest, Tail).

Обратите внимание, что при попытке выполнить накопление с помощью выражения, такого как Result = [Ah|Result], Prolog создает бесконечно рекурсивную структуру данных: Result объединяется со списком, в котором Ah в качестве заголовка и Result в качестве хвоста, который объединяется со списком, имеющим Ah в качестве головы и Result в качестве хвоста, который объединяется со списком, имеющим Ah в качестве головы и Result в качестве хвоста, и так далее, и так далее, и так далее.

2 голосов
/ 07 марта 2011

Вы нуждаетесь в рекурсии в обеих ветвях, и вам нужен базовый случай: 

filter_doubles([], []).
filter_doubles([X|L], Result) :-
    (memberchk(X,L) ->
        filter_doubles(L, Result)
    ;
        filter_doubles(L, Result0),
        Result = [X|Result0]
    ).

Result = [Ah|Result] действительно кажется случаем императивного мышления.Что в Прологе означает «объединить Result с термином, который имеет Result в качестве второго аргумента», который либо не срабатывает (в сочетании с проверкой происходит), либо создает «рациональное дерево» (графовая структура с циклом,в большинстве прологов).

Упражнение: сделать код, который я разместил, рекурсивным.

Обратите внимание, что это удаляет все элементы, кроме последнего, для каждого элемента.

...