Prolog: Using =../2 (Univ) in a recursive way

Question

I'm having quite a simple problem in Prolog (SWI-Prolog) but I can't figure it out.

What I want is to create a recursive predicate which is able to swap any nested list into a compound term.

I want to swap between these two representation because I'm using a substitute algorithm which works on the list representation and I want the compound representation as output.

So I would like:

list_2_compound(List,Compound).

which for example works like

list_2_compound([seq, [seq, [if, p1, p2], p2], p1, p3], Compound).

Compound = seq(seq(if(p1, p2), p2), p1, p3)

So I typically want to use the =.. operator:

Compound =.. [if, p1, p2] 
Compound = if(p1,p2)

But now in a recursive way to transverse to the nested list.

Answer 1

a bit more tricky than I thought at first glance.

list_2_compound(L, T) :-
    var(T)
    ->  L = [F|Fs], maplist(list_2_compound, Fs, Ts), T =.. [F|Ts]
    ;   atomic(T)
    ->  L = T
    ;   L = [F|Fs], T =.. [F|Ts], maplist(list_2_compound, Fs, Ts).
list_2_compound(T, T).

(my previous post produced too much nested list on the reverse case). Test:

1 ?- list_2_compound([seq, [seq, [if, p1, p2], p2], p1, p3], Compound).
Compound = seq(seq(if(p1, p2), p2), p1, p3) 
.

2 ?- list_2_compound(S, $Compound).
S = [seq, [seq, [if, p1, p2], p2], p1, p3] 
.

edit

After @damianodamiano comment, it's clear there is a bug, but it's not

the same solution an infinite number of times

since we have

?- aggregate(count,L^list_2_compound(L, seq(seq(if(p1, p2), p2), p1, p3)),N).
N = 45.

In the end, it's just that the 'catch all' clause overlaps - uselessly - with the already handled cases above. But to avoid confusion, and make better use of the declarative properties of this snippet, I'll rename the predicate to list_compound:

list_compound(L, T) :-
    (   var(T)
    ->  L = [F|Fs], maplist(list_compound, Fs, Ts), T =.. [F|Ts]
    ;   atomic(T)
    ->  L = T
    ;   L = [F|Fs], T =.. [F|Ts], maplist(list_compound, Fs, Ts)
    ),
    !.
list_compound(T, T).

and now we have a deterministic computation:

?- list_compound(L, seq(seq(if(p1, p2), p2), p1, p3)).
L = [seq, [seq, [if, p1, p2], p2], p1, p3].

?- list_compound($L, C).
C = seq(seq(if(p1, p2), p2), p1, p3),
L = [seq, [seq, [if, p1, p2], p2], p1, p3].

So, this is the same solution @patta1986 explained in its comment back in 2013...

Answer 2

If you want to be fully lazy and pure, you can use when/2 (coroutining) to delay computation until you have a nonvar head functor. This way the predicate (named =... below) works in all modes.

:- op(700, xfx, =...).
Term =... [Functor|Sublists] :-
    when((nonvar(Term) ; nonvar(Functor)),
         (var(Term)
         -> maplist(=..., Subterms, Sublists),
            Term =.. [Functor|Subterms]
         ;  Term =.. [Functor|Subterms],
            maplist(=..., Subterms, Sublists))).

?- f(X, g(Y)) =... L, X=1, Y=2.  % Mostly forwards
X = 1,
Y = 2,
L = [f, [1], [g, [2]]].

?- T =...  [f, [X], [g, [Y]]], X=1, Y=2.  % Mostly backwards
T = f(1, g(2)),
X = 1,
Y = 2.

?- Term =... List.  % Most general query
List = [_954|_956],
when((nonvar(Term);nonvar(_954)),  (var(Term)->maplist(=..., _1016, _956), Term=..[_954|_1016];Term=..[_954|_1016], maplist(=..., _1016, _956))).

This solution works with fully nested lists, which I think are easier to interface with.