Find if a number is a member of an element in a list

Question

i´m trying to create a predicate that returns me the element of a list that contains a certain number given by me.

Example:

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

X=[1,2,7].

I am a relatively new prolog programmer so this is my code:

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

Thank you very much

[`tmember/2`](http://stackoverflow.com/a/33456560) is also available in `library(reif)` for [SICStus](http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/sicstus/reif.pl)|[SWI](http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/swi/reif.pl). — false, May 08 '17 at 21:02

score 8 · Answer 1 · answered May 06 '17 at 14:35

8

You could use if_/3 and memberd_t/2 from module reif in order to be more deterministic:

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

answered May 06 '17 at 14:35

coder

12,832
5
39
53

1

Can you express this with `tmember/2`? – false May 09 '17 at 10:58
Benchmarking is here: https://stackoverflow.com/a/44373916/502187 . See variant 3. – Jun 06 '17 at 19:00

coder · Answer 2 · 2017-05-09T22:44:32.787

7

Here is an implementation using 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).

edited May 09 '17 at 22:44

answered May 09 '17 at 18:05

coder

12,832
5
39
53

I use SWI but it does't recognize library(reif). – coder May 09 '17 at 21:35
1

http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/swi/reif.pl and say `use_module(reif)` – false May 09 '17 at 21:39
3

The definite solution that you mentioned is not as efficient ...the bounty was given for reif answers in order to be more efficient, also all these answers are complementary and do not contain anything false...there are just some other solutions for the problem!! – coder Jun 05 '17 at 16:33
4

@ j4n bur53 , Because it leaves choice points and also the fact that an answer is correct does not exclude other answers!! – coder Jun 05 '17 at 16:35
4

@ j4n bur53 , Even the most simple query in the question leaves choice points where do you not see the non deterministic!! – coder Jun 05 '17 at 16:37
4

@ j4n bur53 , See the last comment!! – coder Jun 05 '17 at 16:38
4

@ j4n bur53 , What you are expecting for a mathematical proof?? Can you prove that it isn't more efficient?? As I said you could easily see that `where_is_it( [ [1,2,3] , [1,2,7] , [4,5] , [8] ] , 7 , X ).` leaves choice points where this answer does not!! – coder Jun 05 '17 at 16:41
3

@ j4n bur53 , this was not asked from OP nor from false so I will not provide it, but as i said just test with the above query my solution is deterministic while the other is not!!! I don't claim it is perfect but in most cases does not leave choice points. – coder Jun 05 '17 at 16:45
Benchmarking is here: https://stackoverflow.com/a/44373916/502187 . See variant 2. – Jun 06 '17 at 19:01
2

Say `listing(where_is_it3)`. It should not contain `call/2`-goals. – false Jun 07 '17 at 10:31
2

A more systematic comparison, as in https://stackoverflow.com/a/36701487/772868 would help – false Jun 07 '17 at 10:31

score 6 · Answer 3 · answered May 06 '17 at 13:53

6

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

answered May 06 '17 at 13:53

false

10,264
13
101
209

4

Downside: Many redundant solutions for `X`. [This](http://stackoverflow.com/a/43821691/772868) and [that](http://stackoverflow.com/a/43876945/772868) avoid this altogether. – false May 10 '17 at 13:09
5

@j4n bur53, is there any particular reason for downvoting all of my posts and many as others as well?? Did you found something wrong or unhelpful? Such behavior does not help stack overflow...even if you didn't like something you could first make a comment to improve it... – coder Jun 05 '17 at 15:21

score 5 · Answer 4 · edited May 23 '17 at 12:02

Here is a version using only tmember/2 and (=)/3 without any explicit recursion:

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

The query given by the OP works as expected:

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

Some of the features of this version: If the element occurs in more than one list (differs from version with if_/3 and 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

Multiple occurrences of the element in one list are matched only once (differs from version with member/2):

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

Multiple occurrences of the same list are matched only once (differs from version with member/2):

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

Even with an open list (differs from version with member/2 as well as from version with if_/3 and 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

If the actual element is variable:

   ?- 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

The most general query (differs from version with member/2 (only slightly) as well as from version with if_/3 and 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) ? ;
...

With some constraints (differs from version with member/2 (only slightly) as well as from version with if_/3 and 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

Mnmnmn: To my understanding, `where_is_it([[1,7],[7]],7,[7]).` should rather fail — false, May 09 '17 at 10:55
`tmember(=(X),Xs)` boils down to `memberd(X, Xs)`. Actually, I intended some scoping as [@coders](http://stackoverflow.com/a/43821691/772868) did. s(X), anyway. — false, May 09 '17 at 10:57
Benchmarking is here: https://stackoverflow.com/a/44373916/502187 . See variant 1. — , Jun 06 '17 at 19:00

score 2 · Answer 5 · answered May 06 '17 at 13:40

You should maybe read what your clauses say? You need maybe one clause which says, "If X is member of H, then H is solution":

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

and then you still need another clause that says that maybe you have a solution in the rest of the list:

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

Maybe this is enough for beginning?

score 1 · Answer 6 · answered May 09 '17 at 21:55

Ok, let us look at your code. The first clause is fine, whatever we are looking for it is not in the empty list.

where_is_it([],_,[]).

This is your second clause:

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

Here we have several problems:

First, instead of member([Num],H) you probably need member(Num,H) expressing that Num is an element of the list H.

Second, If this is the clause for the cases where Num is a member of H, your recursion should be as follows:

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

This clause now expresses that whenever Num is a member of H, H belongs to our solution list and we have to look for further solutions in the tail of our list (that is in T) and collect them in Found.

You need an additional clause for the case that Num is not a member of H:

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

This clause does not change your list of found solutions.

Hence the full code is:

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).

Find if a number is a member of an element in a list

6 Answers6