Подтвердить что ты не робот

Найти, если число является элементом элемента в списке

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

Пример:

?- where_is_it( [ [1,2,3] , [1,2,7] , [4,5] , [8] ] , 7 , X ).

X=[1,2,7].

Я - относительно новый пролог-программист, так что это мой код:

where_is_it([],_,[]). 
where_is_it([H|T],Num,H):-
    member([Num],H),!,
    where_is_it(T,Num,[]).

Большое спасибо

4b9b3361

ОТВЕТЫ

Ответ 1

where_is_it(Xss, X, Xs) :-
   member(Xs, Xss),
   member(X, Xs).

Ответ 2

Вы можете использовать if_/3 и memberd_t/2 из модуля reif, чтобы быть более детерминированным:

where_is_it([H|T], X, L) :-
  if_(memberd_t(X,H), L=H, where_is_it(T, X, L)).

Ответ 3

Вот реализация с использованием tmember/2:

where_is_it(InList, X, L):- tmember(check(X,L),InList).

check(X,L,L1,T):- if_( memberd_t(X,L1), (T = true, L = L1), T = false).

Ответ 4

Вот версия, использующая только tmember/2 и (=)/3 без какой-либо явной рекурсии

where_is_it(Xss,X,Xs) :-
   tmember(=(Xs),Xss),
   tmember(=(X),Xs).

Запрос, заданный OP, работает как ожидалось:

   ?- where_is_it([[1,2,3],[1,2,7],[4,5],[8]],7,X).
X = [1,2,7] ? ;
no

Некоторые функции этой версии: Если элемент встречается в нескольких списках (отличается от версии с if_/3 и memberd_t):

   ?- where_is_it([[1,2,3],[1,2,7],[4,5],[8]],1,X).
X = [1,2,3] ? ;
X = [1,2,7] ? ;
no

Несколько вхождений элемента в один список сопоставляются только один раз (отличается от версии с элементом /2):

   ?- where_is_it([[1,2,3,1],[4,5],[8]],1,X).
X = [1,2,3,1] ? ;
no

Несколько вхождений одного и того же списка сопоставляются только один раз (отличается от версии с элементом /2):

   ?- where_is_it([[1,2,3],[1,2,3],[4,5],[8]],1,X).
X = [1,2,3] ? ;
no

Даже с открытым списком (отличается от версии с членом /2, а также с версией if_/3 и memberd_t):

   ?- where_is_it([[1,2,3],[1,2,7],[4,5],[8],[1|_]],1,X).
X = [1,2,3] ? ;
X = [1,2,7] ? ;
X = [1|_A],
dif([1|_A],[1,2,3]),
dif([1|_A],[1,2,7]) ? ;
no

Если фактический элемент является переменным:

   ?- where_is_it([[1,2,3],[8]],Y,X).
X = [1,2,3],
Y = 1 ? ;
X = [1,2,3],
Y = 2 ? ;
X = [1,2,3],
Y = 3 ? ;
X = [8],
Y = 8 ? ;
no

Самый общий запрос (отличается от версии с членом /2 (только немного), а также с версией if_/3 и memberd_t):

   ?- where_is_it(Xss,X,Xs).
Xs = [X|_A],
Xss = [[X|_A]|_B] ? ;
Xs = [_A,X|_B],
Xss = [[_A,X|_B]|_C],
dif(X,_A) ? ;
Xs = [_A,_B,X|_C],
Xss = [[_A,_B,X|_C]|_D],
dif(X,_B),
dif(X,_A) ? ;
...

С некоторыми ограничениями (отличается от версии с членом /2 (только слегка), а также с версией if_/3 и memberd_t):

   ?- Xss=[_,_],Xs=[_,_],where_is_it(Xss,X,Xs).
Xs = [X,_A],
Xss = [[X,_A],_B] ? ;
Xs = [_A,X],
Xss = [[_A,X],_B],
dif(X,_A) ? ;
Xs = [X,_A],
Xss = [_B,[X,_A]],
dif([X,_A],_B) ? ;
Xs = [_A,X],
Xss = [_B,[_A,X]],
dif(X,_A) ? ;
no

Ответ 5

Вы должны, возможно, прочитать, что говорят ваши предложения? Вам нужно, может быть, одно предложение, которое гласит: "Если X является членом H, то H является решением":

where_is_it([H|_], X, H) :-
    member(X, H).

а затем вам еще нужно другое предложение, в котором говорится, что, возможно, у вас есть решение в остальной части списка:

where_is_it([_|T], X, H) :-
    where_is_it(T, X, H).

Может быть, этого достаточно для начала?

Ответ 6

Хорошо, давайте посмотрим на ваш код. Первое предложение прекрасно, все, что мы ищем, не находится в пустом списке.

where_is_it([],_,[]).

Это ваше второе предложение:

where_is_it([H|T],Num,H):-
    member([Num],H),!,
    where_is_it(T,Num,[]).

Здесь у нас есть несколько проблем:

Во-первых, вместо member([Num],H) вам, вероятно, понадобится member(Num,H), выражая, что Num является элементом списка H.

Во-вторых, если это предложение для случаев, когда Num является членом H, ваша рекурсия должна быть следующей:

 where_is_it([H|T],Num,[H|Found]):-
     member(Num,H),!,
     where_is_it(T,Num,Found).

Теперь этот пункт выражает, что всякий раз, когда Num является членом H, H принадлежит к нашему списку решений, и мы должны искать дальнейшие решения в хвосте нашего списка (то есть в T) и собирать их в Found.

Вам понадобится дополнительное предложение для случая, когда Num не является членом H:

 where_is_it([H|T],Num,Found):-
     where_is_it(T,Num,Found).

Этот раздел не изменяет список найденных решений.

Следовательно, полный код:

where_is_it([],_,[]).

where_is_it([H|T],Num,[H|Found]):-
     member(Num,H),!,
     where_is_it(T,Num,Found).

 where_is_it([_H|T],Num,Found):-
     where_is_it(T,Num,Found).

Ответ 7

Я не вижу никакого преимущества reif, за исключением замедления:-(, возьмите эти решения:

Традиционные решения:

/* variant 1 */
where_is_it(Xss, X, Xs) :-
   member(Xs, Xss),
   member(X, Xs).

/* variant 2 */
where_is_it2(Xss, X, Xs) :-
   member(Xs, Xss),
   memberchk(X, Xs), !.

/* variant 3 */
where_is_it3([H|T], X, R) :-
   (memberchk(X, H) -> R=H; where_is_it3(T, X, R)).

reif solutions:

/* variant 1 */
where_is_it(Xss, X, Xs) :-
   tmember(=(Xs), Xss),
   tmember(=(X), Xs).

/* variant 2 */
where_is_it2(InList, X, L):- 
   tmember(check(X,L),InList).
check(X,L,L1,T):- 
   if_( memberd_t(X,L1), (T = true, L = L1), T = false).

/* variant 3 */
where_is_it3([H|T], X, L) :-
   if_(memberd_t(X,H), L=H, where_is_it3(T, X, L)).

Тайминги выглядят следующим образом:

Традиционное решение:

/* variant 1 */
?- where_is_it([[4,5],[1,2,3],[8],[1,2,7]],1,X).
X = [1, 2, 3] ;
X = [1, 2, 7] ;
false.

/* variant 2 */
?- where_is_it2([[4,5],[1,2,3],[8],[1,2,7]],1,X).
X = [1, 2, 3].

/* variant 3 */
?- where_is_it3([[4,5],[1,2,3],[8],[1,2,7]],1,X).
X = [1, 2, 3].

/* variant 1 */
?- time((between(1,1_000_000,_), 
         where_is_it([[4,5],[1,2,3],[8],[1,2,7]],1,_), 
         fail; true)).
% 20,000,001 inferences, 1.031 CPU in 1.031 seconds (100% CPU, 19393940 Lips)
true.

/* variant 2 */
?- time((between(1,1_000_000,_), 
         where_is_it2([[4,5],[1,2,3],[8],[1,2,7]],1,_), 
         fail; true)).
% 7,000,000 inferences, 0.422 CPU in 0.422 seconds (100% CPU, 16592593 Lips)
true.

/* variant 3 */
time((between(1,1_000_000,_), 
         where_is_it3([[4,5],[1,2,3],[8],[1,2,7]],1,_), 
         fail; true)).
% 6,000,000 inferences, 0.297 CPU in 0.297 seconds (100% CPU, 20210526 Lips)
true.

reif solution:

/* variant 1 */
?- where_is_it([[4,5],[1,2,3],[8],[1,2,7]],1,X).
X = [1, 2, 3] ;
X = [1, 2, 7] ;
false.

/* variant 2 */
?- where_is_it2([[4,5],[1,2,3],[8],[1,2,7]],1,X).
X = [1, 2, 3].

/* variant 3 */
?- where_is_it3([[4,5],[1,2,3],[8],[1,2,7]],1,X).
X = [1, 2, 3].

/* variant 1 */
?- time((between(1,1_000_000,_), 
         where_is_it([[4,5],[1,2,3],[8],[1,2,7]],1,_), 
         fail; true)).
% 400,000,001 inferences, 18.688 CPU in 18.674 seconds (100% CPU, 21404682 Lips)
true.

/* variant 2 */
?- time((between(1,1_000_000,_), 
         where_is_it2([[4,5],[1,2,3],[8],[1,2,7]],1,_), 
         fail; true)).
% 18,000,000 inferences, 1.203 CPU in 1.203 seconds (100% CPU, 14961039 Lips)
true.

/* variant 3 */
?- time((between(1,1_000_000,_), 
         where_is_it3([[4,5],[1,2,3],[8],[1,2,7]],1,_), 
         fail; true)).
% 13,000,000 inferences, 0.688 CPU in 0.687 seconds (100% CPU, 18909091 Lips)
true.

В основном решение reif составляет ок. 18 раз, ок. 3-кратный соответствующий ок. В 2 раза медленнее.