Find occurrence of predicate anywhere it exists in a nested, compound object?

Help!
1

Let’s say I have a really complicated term that is any combination of lists, atoms, predicates, etc. Worse, the items have child items themselves of the same nature. So I have a single term, but one that is composed of a completely free form nature of items, with child items containing child items, recursively with (possibly) interleaved lists, atomics, etc.

Is there an SWI-Prolog predicate that can take a desired predicate name, and scan the entire tree of a term and find occurences of the desried predicate anywhere it might exist in the parent term’s tree of items?

I think I can write such a function, but it will be messy and tricky given the interwined nature of the clauses needed to switch between lists, compound terms, and atomics as you descend recursively through the parent term’s structure. I’m hoping there might be something in SWI-Prolog or one of its packages that does this.

For example. Supposed I was looking for a predicate named my_pred_to_find in a complex term named parent_term:

Target = 
    parent_term(
        a, b, c, 
        child_predicate(
            [1, 2, 3, 
                my_pred_to_find(
                    [dog, nested_cat([fluffy, furry, paw(has_toes)])])])),
find_predicate_anywhere(my_pred_to_find, Target, PredFound).

The hypothetical function named find_predicate_anywhere would bind ValueOfPredFound to:

ValueOfPredFound = [dog, nested_cat([fluffy, furry, paw(has_toes)])].

Is there such a function/predicate in SWI-Prolog or one of its packages?

2

Maybe the word functor would be better here. I think of predicate as free standing clause(s).

1 Like
3

This can help you: compound_name_arguments/3 and nonvar.

You might also take a look at pprint in listing.pl, which processes all the subterms recursively.

1 Like
4

Hello again.

Here is the code that I came up with for find_functor_anywhere. Any comments would be welcome. It appears to work, but I have not exhaustively tested it yet:

% ----->>>>> find_functor_anywhere

    % ----->>>>> find_functor_anywhere_list

    % Failed to find the desired functor anywhere in the list.  This is
    %   an overall failure.
    find_functor_anywhere_list([], _, _) :- !, fail.

    % Test the head of the list for a match.
    find_functor_anywhere_list(DesiredFunctor, [H | _], ValueInTarget) :-
        find_functor_anywhere(DesiredFunctor, H, ValueInTarget),
        !.

    % Process the rest of the list.
    find_functor_anywhere_list(DesiredFunctor, [_ | T], ValueInTarget) :-
        find_functor_anywhere_list(DesiredFunctor, T, ValueInTarget),
        !.

    % ----->>>>> find_functor_anywhere_list

    % An atom is not a match.
    find_functor_anywhere_mux(_, Target, _) :-
        atom(Target),
        !,
        fail.

    % MATCH:  Found a compound term with the desired functor name.
    find_functor_anywhere_mux(DesiredFunctor, Target, ValueInTarget)  :-
        Target =.. [DesiredFunctor | ValueInTarget],
        !.

    % A list has to be iterated.
    find_functor_anywhere_mux(DesiredFunctor, Target, ValueInTarget) :-
        is_list(Target),
        !,
        find_functor_anywhere_list(DesiredFunctor, Target, ValueInTarget).

    % A compound term must have each argument inspected.  This is a
    %   compound term without the desired functor name.
    find_functor_anywhere_mux(DesiredFunctor, Target, ValueInTarget)  :-
        Target =.. [_ | Args],
        !,
        find_functor_anywhere_list(DesiredFunctor, Args, ValueInTarget).

% ----->>>>> find_functor_anywhere_list

% Find the first occurrence of a compound term whose functor matches the desired functor name.
%   Unify ValueInTarget with the arguments of that functor occurrence.
find_functor_anywhere(DesiredFunctor, Target, ValueInTarget) :-
    nonvar(DesiredFunctor),
    atom(DesiredFunctor),
    nonvar(Target),
    find_functor_anywhere_mux(DesiredFunctor, Target, ValueInTarget).

Sample query:

48 ?- find_functor_anywhere( cuddly, [dog, cat, cuddlyx(duck, [a,b,c], cuddly(frog, mog))], ValueInTarget).
ValueInTarget = [frog, mog].
5

You should consider variations that has parameters to choose the level or the in_order walk location. Currently you are defaulting to the first one it finds, but what if you are searching a tree where there are lots of functors with the same name e.g. leaf (leaf(1,leaf(2,nil,nil),leaf(3,(leaf(4,nil,nil),nil)))).

1 Like
6

Does this do what you want?

use_module(library(apply)).

find_in_term(Functor, Within, FoundArgs) :-
    Within =.. [Functor|FoundArgs].
find_in_term(Functor, Within, FoundArgs) :-
    Within =.. [_|WithinArgs],
    convlist(find_in_term(Functor), WithinArgs, FoundArgsList),
    member(FoundArgs, FoundArgsList).
3 Likes
7

(This is better code … no need for convlist/2).

find_in_term(FunctorName, Within, FoundArgs) :-
    Within =.. [FunctorName|FoundArgs].
find_in_term(FunctorName, Within, FoundArgs) :-
    Within =.. [_|WithinArgs],
    member(WithinArg, WithinArgs),
    find_in_term(FunctorName, WithinArg, FoundArgs).

The code can also be refactored to avoid doing =../2 twice, if the tiny bit of speed-up is important.

3 Likes
8

Thanks Peter. I fall so often into the habit of using list dissassembly and recursion ([H | T]) to inspect list elements, that I forget you can use member() with backtracking in a case like this where you don’t need to copy over the original list elements to an output variable. Your code is definitely more succinct and efficient.