我目前已经开始使用PROLOG，我想写一个谓词，检查一个给定的对象是否在这个列表中。如果对象在列表中，谓词应该返回元素的索引。如果未找到该元素，则返回0。
它应该这样工作:find(3,[1,4,5,3,2,3],N). -> yes. N / 4find(2,[1,3,4,5,6,7],N). -> yes. N / 0
但是我在计算索引N方面有问题，也许这里有人可以帮助我。我看过很多遍历列表的不同方法，但我发现的方法太多了，我无法理解它们是如何工作的。如果有人能提供一个解决方案，并解释它是如何工作的，我将非常高兴。
这是我目前为止写的:
find(X, [X|TAIL], N) :- N is 1, write(N).
find(X, [], N) :- N is 0, write(N).
find(X, [_|TAIL], N) :- find(X, TAIL, N + 1).
基本情况
find(a, [a, b, c, d, e, f, g], N) -> yes. N / 1.
find(j, [a, b, c, d, e, f, g], N) -> yes. N / 0.
但是当它开始递归时，它不再工作了，我不明白出了什么问题。
对于递归的情况，它给了我这个:find(b, [a, b, c, d, e, f, g], N) -> no.
我感谢每一个回答和每一个评论!
要求:
- 如果一个元素不在列表中，它应该输出
yes. N = 0.示例:?- find(a, [], N) -> yes. N = 0.和?- find(a, [b,c,d], N) -> yes. N = 0. - 如果一个元素在列表中，它应该输出该元素的索引(从1开始计数)。示例:
?- find(a, [a, b, c], N) -> yes. N = 1和?- find(a, [b,c,a,d], N) -> yes. N = 3. - 如果元素不止一次出现，它应该只输出该元素第一次出现的索引。示例:
?- find(a, [a,b,c,a], N) -> yes. N = 1. - 应该只给出一个答案
- 如果可能，不应该使用库。
- 查询
?- find(a, [a, b,c], 0)和?- find(a, [b, a, c], 0)以及列表中a的所有其他查询都应该用no回答。 - 查询
?- find(a, [a, b, c, a], 4)应该用no回答，因为索引为4的a不是a的第一次出现。
备注:此解决方案生成回溯时发现Item的每个索引，并在没有项目与目标项目统一时仅将Index与0统一，并且不完全是OP现在在其要求中明确声明的内容。
item_index(Item, L, Index):-
item_index(L, Item, 1, Index).
item_index([], _, _, 0).
item_index([Item|L], Item, CurIndex, Index):-
item_index1(L, Item, CurIndex, Index).
item_index([CurItem|L], Item, CurIndex, Index):-
dif(CurItem, Item),
succ(CurIndex, CurIndex1),
item_index(L, Item, CurIndex1, Index).
item_index1(_, _, Index, Index).
item_index1(L, Item, CurIndex, Index):-
succ(CurIndex, CurIndex1),
item_index2(L, Item, CurIndex1, Index).
item_index2([Item|L], Item, CurIndex, Index):-
item_index1(L, Item, CurIndex, Index).
item_index2([CurItem|L], Item, CurIndex, Index):-
dif(CurItem, Item),
succ(CurIndex, CurIndex1),
item_index2(L, Item, CurIndex1, Index).
解释:
这个答案经过不同的过程来维持是否已经找到任何解决方案的状态。因此，当遍历item_index/4中的列表时，没有匹配。在第一次匹配之后(以及以后的每一次匹配之后)调用item_index1/4，它将把Index与当前索引统一起来，并在回溯时继续遍历item_index2/4中的列表。
当没有更多的项目要遍历时，只有在之前没有匹配的情况下，它才会将Index统一为0(这在item_index/4的第一个子句中完成)。
样本:
?- item_index(A, [a,b,c,d,a,b,c], X).
A = a,
X = 1 ;
A = a,
X = 5 ;
A = b,
X = 2 ;
A = b,
X = 6 ;
A = c,
X = 3 ;
A = c,
X = 7 ;
A = d,
X = 4 ;
X = 0,
dif(A, a),
dif(A, c),
dif(A, b),
dif(A, a),
dif(A, d),
dif(A, c),
dif(A, b).
?- item_index(d, [a,b,c], X).
X = 0.
?- item_index(A, [a,b,a], X).
A = a,
X = 1 ;
A = a,
X = 3 ;
A = b,
X = 2 ;
X = 0,
dif(A, a),
dif(A, a),
dif(A, b).
?- item_index(a, [a,b,C], X).
X = 1 ;
C = a,
X = 3 ;
false.
使用库reif的两个纯解:
first_index(E0, Es, N) :-
first_index_(E0, Es, 0, N).
first_index_(_, [], _, none).
first_index_(E0, [E|Es], I0, N) :-
if_(
E0 = E,
N = some(I0),
( succ(I0, I),
first_index_(E0, Es, I, N)
)
).
index(E0, Es, none) :-
maplist(dif(E0), Es).
index(E0, Es, some(I)) :-
nth0(I, Es, E0).
查询确定成功:
?- L = [a,a], N = some(0), first_index(a, L, N).
L = "aa", N = some(0).
这个查询失败:
?- L = [a,a], N = some(1), first_index(a, L, N).
false.
与index/3:
?- L = [a,a], index(a, L, some(0)), index(a, L, some(1)).
L = "aa".
问题:
find_first(E, Es, N) :-
first_index(E, Es, I),
conversion(I, N).
find(E, Es, N) :-
index(E, Es, I),
conversion(I, N).
conversion(none, 0).
conversion(some(I), N) :-
succ(I, N).
目前我没有更好的名字
使用nth1/3的参数顺序
nth1_once_else_0(Nth1, Lst, Elem) :-
nth1_once_else_0_when_(Lst, Elem, 1, Nth1).
nth1_once_else_0_thaw_([H|_], Elem, Upto, Nth1) :-
Upto == Nth1,
!,
H = Elem.
nth1_once_else_0_thaw_(L, _Elem, _Upto, Nth1) :-
L == [],
!,
Nth1 = 0.
nth1_once_else_0_thaw_(L, Elem, _Upto, Nth1) :-
Nth1 == 0,
!,
nth1_once_else_0_thaw_0_(L, Elem).
nth1_once_else_0_thaw_(_L, _Elem, Upto, Nth1) :-
% If gone past Nth1, fail
nonvar(Nth1),
Nth1 =< Upto,
!,
fail.
nth1_once_else_0_thaw_([H|T], Elem, Upto, Nth1) :-
( nonvar(Nth1),
Nth1 > Upto -> true
; H = Elem
),
!,
% Elements must be different
dif(H, Elem),
Upto1 is Upto + 1,
nth1_once_else_0_when_(T, Elem, Upto1, Nth1).
nth1_once_else_0_thaw_([H|_], Elem, Upto, Nth1) :-
?=(H, Elem),
% Able to compare
H = Elem,
!,
% Elements match
Upto = Nth1.
nth1_once_else_0_thaw_([H|T], Elem, Upto, Nth1) :-
% Wait for possible comparison
when(
(?=(H, Elem) ; nonvar(Nth1)),
nth1_once_else_0_thaw_([H|T], Elem, Upto, Nth1)
).
nth1_once_else_0_when_(L, Elem, Upto, Nth1) :-
var(L),
!,
when(
(nonvar(L), nonvar(Elem) ; nonvar(Nth1)),
nth1_once_else_0_thaw_(L, Elem, Upto, Nth1)
).
nth1_once_else_0_when_([], _Elem, _Upto, 0).
nth1_once_else_0_when_([H|T], Elem, Upto, Nth1) :-
when(
(nonvar(H), nonvar(Elem) ; nonvar(Nth1)),
nth1_once_else_0_thaw_([H|T], Elem, Upto, Nth1)
).
% Remainder of list does not match
nth1_once_else_0_thaw_0_(L, Elem) :-
var(L),
!,
freeze(L, nth1_once_else_0_thaw_0_(L, Elem)).
nth1_once_else_0_thaw_0_([], _Elem).
nth1_once_else_0_thaw_0_([H|T], Elem) :-
dif(H, Elem),
freeze(T, nth1_once_else_0_thaw_0_(T, Elem)).
使用swi-prolog的单元测试能力:
:- begin_tests(nth1_once_else_0).
test(1) :-
nth1_once_else_0(2, [a, b], B), B == b.
test(2) :-
nth1_once_else_0(N, [a, b, c, d, e, f, g], a), N == 1.
test(3) :-
nth1_once_else_0(N, [a, b, c, d, e, f, g], j), N == 0.
test(4) :-
nth1_once_else_0(N, [a, b, c, d, e, f, g], b), N == 2.
test(5) :-
nth1_once_else_0(N, [], a), N == 0.
test(6) :-
nth1_once_else_0(N, [], _), N == 0.
test(7) :-
nth1_once_else_0(N, [a, b, c, a, b, c], a), N == 1.
test(8) :-
+ nth1_once_else_0(6, [a, b, c, a, b, c], c).
test(9) :-
nth1_once_else_0(N, L, b), L = [a, b], N == 2.
test(10) :-
+ nth1_once_else_0(0, [a, b], b).
test(11) :-
nth1_once_else_0(N, [a, b, c, a], a), N == 1.
test(12) :-
nth1_once_else_0(N, [a, b, c], d), N == 0.
test(13) :-
nth1_once_else_0(N, [a, b], X), X = b, N == 2.
test(14) :-
nth1_once_else_0(N, L, X), L = [a, b|_], X = b, N == 2.
test(15) :-
nth1_once_else_0(N, L, X), L = [a, b|_], N = 2, X == b.
test(16) :-
nth1_once_else_0(N, L, X), L = [a, b|_], X = z, N = 0.
test(17) :-
L = [a, a], nth1_once_else_0(1, L, a), + nth1_once_else_0(2, L, a).
test(18) :-
nth1_once_else_0(N, L, X), L = [a, b|_], L = [a,b,c], N = 0, + X = a.
test(19) :-
nth1_once_else_0(N, L, X), L = [a, b|_], X = z, L = [a, b], N == 0.
test(20) :-
nth1_once_else_0(N, L, X), nth1(2, L, b), nth1(1, L, a), X = z, L = [a, b], N == 0.
test(21) :-
nth1_once_else_0(N, L, X), nth1(2, L, b), nth1(1, L, a), L = [a, b], X = a, N == 1.
test(22) :-
nth1_once_else_0(N, L, X), X = a, nth1(2, L, b), nth1(1, L, a), N == 1.
test(23) :-
nth1_once_else_0(N, L, X), X = b, nth1(2, L, b), nth1(1, L, a), N == 2.
test(24) :-
nth1_once_else_0(3, L, c), nth1(3, L, C), C == c.
test(25) :-
nth1_once_else_0(3, L, C), C = c, nth1(3, L, Z), Z == c.
test(26) :-
nth1_once_else_0(N, L, c), N = 3, nth1(N, L, C), C == c.
test(27) :-
nth1_once_else_0(N, L, C), C = c, N = 3, nth1(N, L, Z), Z == c.
test(28) :-
nth1_once_else_0(N, [a, b, c|_], c), N == 3.
test(29) :-
+ nth1_once_else_0(3, [_, _], z).
test(30) :-
nth1_once_else_0(N, [-_, -_], +_), N == 0.
test(31) :-
nth1_once_else_0(N, L, X), nth1(2, L, b), nth1(1, L, a), X = a, N == 1.
test(32) :-
nth1_once_else_0(N, L, f(b)), L = [f(Z)|T], Z = g(_), T = [f(B)|_], B = b, N == 2.
test(33) :-
nth1_once_else_0(N, L, f(a)), L = [f(A)|_], A = a, N == 1.
test(34) :-
nth1_once_else_0(N, L, f(b)), L = [f(_)|_], N = 2, nth1(2, L, B), B == f(b).
:- end_tests(nth1_once_else_0).
结果:
?- run_tests.
% All 34 tests passed
使用描述性谓词名称:
nth1_once_else_0(Elem, Lst, Nth1) :-
% Start at element 1
nth1_once_else_0_(Lst, Elem, 1, Nth1),
% Stop after finding 1 solution
!.
% Otherwise, succeed with 0
nth1_once_else_0(_Elem, _Lst, 0).
% Using Upto and Nth1 arguments, rather than unnecessary & slow recursion
nth1_once_else_0_([Elem|_], Elem, Nth1, Nth1).
nth1_once_else_0_([_|T], Elem, Upto, Nth1) :-
% Loop through the list elements
Upto1 is Upto + 1,
nth1_once_else_0_(T, Elem, Upto1, Nth1).
swi-prolog结果:
?- nth1_once_else_0(c, [a, b, c, a, b, c], Nth1).
Nth1 = 3.
?- nth1_once_else_0(z, [a, b, c, a, b, c], Nth1).
Nth1 = 0.
?- nth1_once_else_0(Char, [a, b, c, a, b, c], Nth1).
Char = a,
Nth1 = 1.
?- nth1_once_else_0(Char, [a, b, c, a, b, c], 2).
Char = b.
?- nth1_once_else_0(b, [a, b, c, a, b, c], 3).
false.
下面是改进后的版本:
nth1_once_else_0(Elem, Lst, Nth1) :-
% Start at element 1
nth1_once_else_0_(Lst, Elem, 1, Nth1),
% Stop after finding 1 solution
!.
% Otherwise, succeed with 0
nth1_once_else_0(_Elem, _Lst, 0).
% Using Upto and Nth1 arguments, rather than unnecessary & slow recursion
nth1_once_else_0_([Elem|_], Elem, Upto, Nth1) :-
% Found first match on element
!,
Upto = Nth1.
nth1_once_else_0_([_|T], Elem, Upto, Nth1) :-
% Loop through the list elements
Upto1 is Upto + 1,
nth1_once_else_0_(T, Elem, Upto1, Nth1).
…要防止超过第一个元素match:
?- nth1_once_else_0(c, [a, b, c, a, b, c], 6).
false.
?- nth1_once_else_0(c, [a, b, c, a, b, c], Nth1).
Nth1 = 3.
?- nth1_once_else_0(z, [a, b, c, a, b, c], Nth1).
Nth1 = 0.