Предикат, который принимает список и повторяет каждый элемент X количество раз - Пролог

Question

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

repeat(L,N,Result):-
    rHelp(L,N,[],Result).

rHelp(_,_,Result,Result).
rHelp([H|T],N,L1,L2):-
    dupe(H,N,[],L3),
    append(L1,L3,L4),
    rHelp(T,N,L4,L2).

dupe(_,0,L,L).
dupe(H,N,L,Result):-
    N1 is N-1,
    append(L,[H],L1),
    dupe(H,N1,L1,Result).

Пример теста:

repeat( [a, b, c], 2, [a, a, b, b, c, c] )
repeat( [1, a, 2, b], 0, [ ] )
repeat( [1, 1, 2], 3, [1, 1, 1, 1, 1, 1, 2, 2, 2] )

Все это правда. Я просто пытаюсь получить ложный результат.

Answer 1

Одна из причин, по которой ваша программа не справляется с трудностями, состоит в том, что в ней описывается слишком много неверных решений:

?- repeat([a, b, c], 2, Result).
Result = [] ;
Result = [a, a] ;
Result = [a, a, b, b] ;
Result = [a, a, b, b, c, c] ;
% nontermination

Причина, по которой вы принимаете слишком много решений, заключается в первом предложении rHelp/4:

rHelp(_,_,Result,Result).

Здесь вы говорите, что для любого списка ввода в любой точке вычисления, где у вас есть промежуточный результат Result, это правильное решение. Но это не так. Промежуточный результат является только полным результатом, когда вы исчерпали весь входной список. Этот пункт должен быть:

rHelp([], N, Result, Result).

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

foo(_, Bar).
foo([H|T], Bar) :- ...

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

После исправления мы можем повторить тест:

?- repeat([a, b, c], 2, Result).
Result = [a, a, b, b, c, c] ;
% nontermination

Лучше! Но он все еще идет в поисках новых решений, хотя их нет. Это также случай, когда пункты не являются взаимоисключающими:

dupe(_,0,L,L).
dupe(H,N,L,Result):-
    N1 is N-1,
    ...

Если второй аргумент не 0, применяется второе предложение. Если вторым аргументом является 0, применяется первое предложение ... но также и второе! После нахождения решения с использованием первого предложения Prolog откатится назад и выполнит второе предложение с помощью N = 0. Тогда N1 станет -1, и ваша программа рекурсивно отключится в поисках отрицательной бесконечности.

Исправлено добавление охранника N > 0 во втором предложении. И с этими двумя изменениями тест работает как нужно:

?- repeat([a, b, c], 2, Result).
Result = [a, a, b, b, c, c] ;
false.

Один общий момент, который следует здесь отметить, заключается в том, что было проще понять поведение вашего предиката, используя менее конкретные запросы. Нет необходимости указывать фиксированный список для аргумента Result: оставьте его свободным и посмотрите, что дает вам Пролог!