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

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

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

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

Это проверяет, находится ли «Item» в списке 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|**].

Неужели я считаю это слишком настоятельным?


list if-statement recursion prolog construction
person Oxymoron    schedule 07.03.2011    source источник
comment
Я полагаю, вы имеете в виду is_on(Item, [H|T]) :- Item = H; is_on(Item, T). или is_on(X,L) :- memberchk(X,L).   -  person Fred Foo    schedule 07.03.2011
comment
Да, именно так, поспешил написать этот пост, не думая об этом хе-хе   -  person Oxymoron    schedule 07.03.2011
comment
Также имеется синтаксическая ошибка (отсутствует скобка), и называется ли предикат filter_double или filter_doubles?   -  person Fred Foo    schedule 07.03.2011

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

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

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

person Fred Foo    schedule 07.03.2011

arrow_upward
3
arrow_downward

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

Итак, ваше 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 в качестве хвоста, и так далее, и так далее, и так далее.

person Giulio Piancastelli    schedule 07.03.2011
comment
Я еще даже не заметил Result = [Ah|Result]. Дополнил свой ответ некоторыми комментариями по этому поводу. +1 вам. - person Fred Foo; 07.03.2011
comment
Да, в конце концов я решил попытаться объяснить это сам. - person Giulio Piancastelli; 07.03.2011