Prolog 对列表进行成员资格操作，返回找到的元素的索引

Question

Prolog 对列表进行成员资格操作，返回找到的元素的索引

Dav*_*ell 7 functional-programming prolog

我目前已经开始使用 PROLOG，我想编写一个谓词来检查给定对象是否在此列表中。如果对象在列表中，谓词应返回元素的索引。如果未找到该元素，则应返回 0。

它应该像这样工作：find(3,[1,4,5,3,2,3],N). -> yes. N / 4 find(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).

Run Code Online (Sandbox Code Playgroud)

它适用于基本情况：

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.

Run Code Online (Sandbox Code Playgroud)

但是当它开始递归时它就不再工作了，我不明白出了什么问题。

对于递归情况，它给了我这个： 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 的第一次出现。

Answer 1

gus*_*bro 5

注意：此解决方案产生回溯时找到项目的每个索引，并且仅当没有项目与目标项目统一时才与目标项目统一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).

Run Code Online (Sandbox Code Playgroud)

解释：

这个答案通过不同的过程来维持是否已经找到任何解决方案的状态。所以在遍历列表的时候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.

Run Code Online (Sandbox Code Playgroud)

Answer 2

bre*_*ebs 1

使用参数顺序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)).

Run Code Online (Sandbox Code Playgroud)

使用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 Code Online (Sandbox Code Playgroud)

结果：

?- run_tests.
% All 34 tests passed

Run Code Online (Sandbox Code Playgroud)

归档时间：	3 年，2 月前
查看次数：	381 次
最近记录：	3 年，2 月前