Поскольку вы не указали код для other_pred/2, будет использоваться member/2.
mypred([H1|T1], L2, [H1|R]) :-
member(H1,L2),
mypred(T1,L2,R).
mypred([H1|T1], L2, R) :-
\+ member(H1,L2),
mypred(T1,L2,R).
mypred([],_,[]).
Пример выполнения:
?- mypred([1,3,5], [1,2,4,5], R).
R = [1, 5] ;
false.
?- mypred([], [1,2,4,5], R).
R = [].
?- mypred([1,3,5], [], R).
R = [].
?- mypred([1,3,5], [2,4,6], R).
R = [].
?- mypred([1,3,5], [1,3,5], R).
R = [1, 3, 5] ;
false.
В то время как вы можете использовать nth0/3, используяКонструктор списка |/2 намного лучше, см .: Списки
В этом коде [H1|T1] и [H1|R] используется конструктор списка.
Этот код также использует рекурсию.
Рекурсивные предложения:
mypred([H1|T1], L2, [H1|R]) :-
member(H1,L2),
mypred(T1,L2,R).
mypred([H1|T1], L2, R) :-
\+ member(H1,L2),
mypred(T1,L2,R).
, поскольку в предложении вызывается предикат mypred/3.Кроме того, поскольку вызов mypred/3 является последним вызовом в предложении, это хвостовая рекурсия .
Базовый случай для рекурсивного предиката:
mypred([],_,[]).
Как это работает для
mypred([1,3,5], [1,2,5], R).
: список [1,3,5] для первого параметра сопоставляется с первым предикатом
mypred([H1|T1], L2, [H1|R]) :-
member(H1,L2),
mypred(T1,L2,R).
Это успешно выполняется при следующем объединении
H1 = 1
T1 = [3,5]
L2 = [1,2,5]
R = _
Следующая строка в предложении выполняется:
member(H1,L2)
Это успешно.
Последняя строка в предложении выполняется:
mypred(T1,L2,R)
Thisсоответствует первому предикату
mypred([H1|T1], L2, [H1|R]) :-
member(H1,L2),
mypred(T1,L2,R).
Это успешно выполняется при следующем объединении
H1 = 3
T1 = [5]
L2 = [1,2,5]
R = _
Следующая строка в предложении выполняется:
member(H1,L2)
Это происходит с ошибками и возвращается.
Так как есть еще одно предложение для my_pred/3, оно пробуется.
mypred([H1|T1], L2, R) :-
\+ member(H1,L2),
mypred(T1,L2,R).
Это завершается следующим объединением
H1 = 3
T1 = [5]
L2 = [1,2,5]
R = _
Следующая строка в предложениивыполняется:
\+ member(H1,L2)
Это успешно.
Этот шаблон попытки различныхпункты для предиката продолжаются.На этом этапе детали будут пропущены до тех пор, пока не будет использовано третье предложение.
Когда список первых параметров равен [], используется третье предложение,
mypred([],_,[]).
Теперь можно начать возврат.
Поскольку единственные строки, которые могут вызывать третье предложение, похожи на
mypred(T1,L2,R).
в первом и втором предложениях, R объединяется с [].
Теперь в зависимости от того, какие из предложенных предложений, вызывающих список, в третьем параметре будут построены по-разному.
Если было использовано второе предложение, третий параметр будет создан с использованием
mypred([H1|T1], L2, R)
Таким образом, список просто возвращается без изменений.
Однако, если использовалось первое предложение, третий параметр будет создан с использованием
mypred([H1|T1], L2, [H1|R])
, но на этот раз результаттретьим параметром будет значение H1 при выполнении предложения в сочетании со значением R.Поэтому, если H1 равно 5 и R равно [], то [H1|R] равно [5|[]], что [5].
Вот трассировка для
mypred([1,3,5], [1,2,5], R).
так что вы звоните, посмотрите на все детали.
?- trace.
[trace] ?- mypred([1,3,5], [1,2,5], R).
Call: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
Unify: (8) mypred([1, 3, 5], [1, 2, 5], [1|_2090])
Call: (9) lists:member(1, [1, 2, 5])
Unify: (9) lists:member(1, [1, 2, 5])
Exit: (9) lists:member(1, [1, 2, 5])
Call: (9) mypred([3, 5], [1, 2, 5], _2090)
Unify: (9) mypred([3, 5], [1, 2, 5], [3|_2096])
Call: (10) lists:member(3, [1, 2, 5])
Unify: (10) lists:member(3, [1, 2, 5])
Fail: (10) lists:member(3, [1, 2, 5])
Redo: (9) mypred([3, 5], [1, 2, 5], _2090)
Unify: (9) mypred([3, 5], [1, 2, 5], _2090)
Call: (10) lists:member(3, [1, 2, 5])
Unify: (10) lists:member(3, [1, 2, 5])
Fail: (10) lists:member(3, [1, 2, 5])
Redo: (9) mypred([3, 5], [1, 2, 5], _2090)
Call: (10) mypred([5], [1, 2, 5], _2090)
Unify: (10) mypred([5], [1, 2, 5], [5|_2096])
Call: (11) lists:member(5, [1, 2, 5])
Unify: (11) lists:member(5, [1, 2, 5])
Exit: (11) lists:member(5, [1, 2, 5])
Call: (11) mypred([], [1, 2, 5], _2096)
Unify: (11) mypred([], [1, 2, 5], [])
Exit: (11) mypred([], [1, 2, 5], [])
Exit: (10) mypred([5], [1, 2, 5], [5])
Exit: (9) mypred([3, 5], [1, 2, 5], [5])
Exit: (8) mypred([1, 3, 5], [1, 2, 5], [1, 5])
R = [1, 5] ;
Redo: (10) mypred([5], [1, 2, 5], _2090)
Unify: (10) mypred([5], [1, 2, 5], _2090)
Call: (11) lists:member(5, [1, 2, 5])
Unify: (11) lists:member(5, [1, 2, 5])
Exit: (11) lists:member(5, [1, 2, 5])
Fail: (10) mypred([5], [1, 2, 5], _2090)
Fail: (9) mypred([3, 5], [1, 2, 5], _2090)
Redo: (9) lists:member(1, [1, 2, 5])
Fail: (9) lists:member(1, [1, 2, 5])
Redo: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
Unify: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
Call: (9) lists:member(1, [1, 2, 5])
Unify: (9) lists:member(1, [1, 2, 5])
Exit: (9) lists:member(1, [1, 2, 5])
Fail: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
false.
Если вы используете SWI-Prolog, то выполните эту комбинацию запросов, чтобы вызвать трассировщик GUI, который лучшедля обучения.
?- gtrace.
[trace] ?- mypred([1,3,5], [1,2,5], R).
За предложение в комментарии
Вот некоторые другие небольшие изменения кода и показатели производительности.
mypred_01([H1|T1], L2, [H1|R]) :-
member(H1,L2),
mypred_01(T1,L2,R).
mypred_01([H1|T1], L2, R) :-
\+ member(H1,L2),
mypred_01(T1,L2,R).
mypred_01([],_,[]).
mypred_02(L1,L2,R) :-
mypred_02_helper(L1,L2,[],R).
mypred_02_helper([H1|T1],L2,R0,R) :-
(
member(H1,L2)
->
mypred_02_helper(T1,L2,[H1|R0],R)
;
mypred_02_helper(T1,L2,R0,R)
).
mypred_02_helper([],_,R,R).
mypred_03(L1,L2,R) :-
mypred_03_helper(L1,L2,[],R0),
reverse(R0,R).
mypred_03_helper([H1|T1],L2,R0,R) :-
(
member(H1,L2)
->
mypred_03_helper(T1,L2,[H1|R0],R)
;
mypred_03_helper(T1,L2,R0,R)
).
mypred_03_helper([],_,R,R).
mypred_04(L1,L2,R) :-
mypred_04_helper(L1,L2,[],R).
mypred_04_helper([H1|T1],L2,R0,R) :-
(
memberchk(H1,L2)
->
mypred_04_helper(T1,L2,[H1|R0],R)
;
mypred_04_helper(T1,L2,R0,R)
).
mypred_04_helper([],_,R,R).
mypred_05(L1,L2,R) :-
mypred_05_helper(L1,L2,[],R0),
reverse(R0,R).
mypred_05_helper([H1|T1],L2,R0,R) :-
(
memberchk(H1,L2)
->
mypred_05_helper(T1,L2,[H1|R0],R)
;
mypred_05_helper(T1,L2,R0,R)
).
mypred_05_helper([],_,R,R).
Вот результаты производительности.
?- findall(N, between(1,100000,N), L1),time(mypred_01(L1,[1,10,100,10000,100000],R)).
% 1,400,020 inferences, 0.109 CPU in 0.103 seconds (106% CPU, 12800183 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [1, 10, 100, 10000, 100000] ;
% 36 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
false.
?- findall(N, between(1,100000,N), L1),time(mypred_02(L1,[1,10,100,10000,100000],R)).
% 799,988 inferences, 0.063 CPU in 0.062 seconds (101% CPU, 12799808 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [100000, 10000, 100, 10, 1].
?- findall(N, between(1,100000,N), L1),time(mypred_03(L1,[1,10,100,10000,100000],R)).
% 800,059 inferences, 0.047 CPU in 0.053 seconds (88% CPU, 17067925 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [1, 10, 100, 10000, 100000].
?- findall(N, between(1,100000,N), L1),time(mypred_04(L1,[1,10,100,10000,100000],R)).
% 299,999 inferences, 0.031 CPU in 0.041 seconds (77% CPU, 9599968 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [100000, 10000, 100, 10, 1].
?- findall(N, between(1,100000,N), L1),time(mypred_05(L1,[1,10,100,10000,100000],R)).
% 300,005 inferences, 0.031 CPU in 0.032 seconds (98% CPU, 9600160 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [1, 10, 100, 10000, 100000].