Deep copy of a list in Prolog

Question

I am trying to copy a list so that the original list is not changed by whatever operations I perform on the new list. I have looked at prolog, copying lists and Prolog - copy a piece of list. However, neither of these options generates a list that is "independent" from its "parent".

Coming from an imperative background, some Prolog concepts are hard to grasp and I'm sure I'm missing something here. So my question is is it possible to create a deep copy of a list in Prolog?

Thank you in advance.

Did you try `copy_term/2`? Not sure why you'd need such a thing if you are new to Prolog. — Daniel Lyons, May 04 '19 at 05:05
You do not need a copy of a list that is _ground_. They are immutable anyway. You cannot perform any modifying "operations" on the list . (Well, you could, but this will take you deep into non-backtracking, non-logical territory.) Unless you describe a particular use case, it is difficult to even start answering your question. How are you going to use this "deep copy"? What problem are you solving and what algorithm are you using and how are you implementing it in Prolog? Then we have some realistic example to build upon. — User9213, May 04 '19 at 05:53

score 1 · Accepted Answer · answered May 07 '19 at 23:13

A list is just a term dressed in fancy clothing.

[] is a simple atom.
[a] is syntactic sugar for the term .(a,[])
[a,b] is syntactic sugar for the term .(a,.(b,[])).
[H|T] is syntactic sugar for the term .(H,T)

That's all there is to it. Conserves parentheses and periods, it does.

So what you're talking about really has nought to do with lists, but everything to do with terms. If the term in question is fully bound -- meaning it and, recursively, any sub-terms, do not contain any non-unified variables, the term is immutable. But if it contains any unbound variables, it's mutable.

So, what you're talking about is doing a recursive tree walk to clone a term, replacing any unbound variables with a fresh copy. The trick is that you need to map each variable encountered with its replacement. so something like [A,A,B,B,foo(A,B,C),C] comes out as [X,X,Y,Y,foo(X,Y,Z),Z] and not [V1,V2,V3,V4,foo(V5,V6,V7),V8].

Luckily, Prolog comes with build-in tooling for that: copy_term/2.

But I imagine your instructor is not looking for you to be using that.

Traversing an arbitrary term is not difficult. Something along these lines (don't have a Prolog convenient to hand at the moment):

clone_deep( T , C ) :- clone_deep( T, [], C, _ ).

% T: source term
% S: symbol table
% C: cloned term
% S1: [possibly] extended symbol table

clone_deep( T , S , C, S1 ) :-
  var(T),                       % term is a variable
  map_var(T,S,C,S1)             % fetch/add its mapping to the symbol table.
  .
clone_deep( T , S , T , S ) :-
  atomic(T)                     % term is atomic (number, atom, etc.)
  .
clone_deep( T , S , C, S1 ) :-
  compound(T),                  % term is a compound term  like foo() or foo(X,Y).
  T =.. [Functor|Args],         % decompose it into its functor and its argument list
  clone_deep(Args,S,Args1,S1),  % recursively clone its arguments
  C =.. [Functor|Args1]         % recompose the new compound term
  .

% recursively run down the list of symbol mappings to find the self-same variable
% add it if not found.

map_var( V , [ X:C | S ] , C , [ X:C | S ] ) :- X  == V, !. % V is the same ref as X -- already in symbol table
map_var( V , [ X:Y | S ] , C , [ X:Y | Z ] ) :- X \== V, !, % V and X are different refs
  fresh_symbol(V,S,C,Z).                                    %
map_var( V , []          , C , [ X:C     ] ).               % not yet mapped var.

Deep copy of a list in Prolog

1 Answers1