Search code examples
recursionprolognested-lists

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


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.


Solution

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