CODEWITHSUNDEEP
prolog
pii_ke
pii_ke

Reputation: 2881

How do I determine if a prolog `compund term` has a particular `atom` inside?

I want a predicate to tell whether a particular atom (say x) appears inside a compound term, however deeply nested.

I tried to read about predicates given at https://www.swi-prolog.org/pldoc/man?section=manipterm. I think it will involve walking down the compound term using functor/3 and ../2 recusively. Is there a simpler approach, or some library that does this?

Upvotes: 2

Views: 261

Answers (2)

CapelliC
CapelliC

Reputation: 60004

Ignoring cyclic terms, I would use ==/2,compound/1 and arg/3

haystack_needle(H,N) :- H==N.
haystack_needle(H,N) :- compound(H),arg(_,H,A),haystack_needle(A,N).

haystack_needle/2 will succeed multiple times, then will allow for counting occurrences:

?- aggregate(count, haystack_needle(t(a,x,b,[x,x,x]),x), C).
C = 4.

Note, the needle does not need to be an atom...

You can use once/1 to tell if needle appears in haystack:

?- once(haystack_needle(t(a,x,b,[x,x,x]),x)).
true.

?- once(haystack_needle(t(a,x,b,[x,x,x]),z)).
false.

As noted by Paulo, arg/3 could not act appropriately in ISO compliant Prologs. A portable alternative (with arguments swapped without other purpose than avoiding confusion) could be

needle_haystack(N,H) :- N==H.
needle_haystack(N,H) :- H=..[_|As],member(A,As),needle_haystack(N,A).

Of course, if member/2 is available :)

Upvotes: 4

Paulo Moura
Paulo Moura

Reputation: 18663

Carlo's elegant answer works on SWI-Prolog but is not portable as the ISO Prolog standard specification for the arg/3 predicate (which most Prolog systems implement) requires its first argument to be bound to an integer, preventing using it as a backtracable generator of compound term arguments. A more portable alternative would be:

haystack_needle(H, N) :-
    H == N.
haystack_needle(H, N) :-
    functor(H, _, A),
    between(1, A, I),
    arg(I, H, A),
    haystack_needle(A, N).

The between/3 predicate is not specified in the ISO Prolog standard but it's a de facto standard predicate usually provided as either a built-in predicate or a library predicate.

Upvotes: 5

Related Questions