# "copy constructors" -- when are terms copied and when linked **URL:** \ **Category:** Help!\ **Created:** [January 18, 2020, 6:33pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760 "2020-01-18T18:33:49Z")\ **Posts on this page:** 16\ **Page:** 1
**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\ **Post date:** [January 18, 2020, 6:33pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/1 "2020-01-18T18:33:49Z")
Hello, I am wondering about space need and implicit copying of terms in my code. What are the rules in swi-prolog that help me determine when terms are copied and when linked. For example, I have a dictionary (assoc) that holds as value a list, to add an item to the list i first lookup the (Key, List), and the create a new list as so: NewList = [New Item | List] and then update the assoc with the New List (via add\_key). I am now wondering – do i actually create a brand new copy of the list – if yes, should i use difference lists instead, or something else.? Also, when i pass a composite term as argument – is this by “reference”, or is some copying happening as well. thanks, Dan ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [January 18, 2020, 6:53pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/2 "2020-01-18T18:53:32Z")
The nodes are “copied” (actually, new ones are created), but the contents remain the same. So, if you start with `[a,b,c]` and append `d`, then a new node is created for each item, but the contents (`a`, `b`, `c`) aren’t “copied”; the new nodes just point to them. The old nodes can often be garbage collected. You might want to use `library(assoc)` or `library(rbtrees)` – for them, a typical insert would copy _log N_ nodes… ---
**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\ **Post date:** [January 18, 2020, 6:56pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/3 "2020-01-18T18:56:17Z")
> [@peter.ludemann](#): > > , then a new node is created for each item That sounds very wasteful – suppose I have a very large list – i really only want to have one node added – just the delta … Would difference lists help ? Is this possible ? ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [January 18, 2020, 7:13pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/4 "2020-01-18T19:13:03Z")
If you append at the front, there’s no extra cost. Difference lists can be used to add at the end, but require a bit of care in setting up and using (DCGs can help with this). If you have keys, then I suggest using association lists; the cost is _O(log N)_ rather than _O(N)_. And, the “copied” nodes can be reclaimed if you’re not creating choicepoints. I have some code that does lots of inserting and lookup; when I last looked at the performance profile, the cost of insertions was ~5%. YMMV. (And my code uses SWI-Prolog’s “dicts”; if I switched to red-black trees, it would be considerably faster.) ---
**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\ **Post date:** [January 18, 2020, 7:16pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/5 "2020-01-18T19:16:17Z")
> [@peter.ludemann](#): > > If you append at the front, there’s no extra cost. Yes, that is what i tried to do with the code: NewList = [Item | OldList] Dan p.s. since i am only pre-prending one item i thought append/3 is not needed. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [January 18, 2020, 8:32pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/6 "2020-01-18T20:32:27Z")
> [@grossdan](#): > > since i am only pre-prending one item i thought append/3 is not needed That is correct – only one node is created. Although `append/3` won’t be expensive in that situation either: `append([Item], OldList, NewList)` becomes `NewList = [Item|OldList]`. And when your computation is finished, you can use `reverse/2` to put the list in insertion order, if that’s what you want. `append(OldList, [Item], NewList)` will create _N_ new nodes when creating `NewList` from `OldList` (but the contents of the nodes won’t be copied). `put_assoc(Key, OldAssoc, Value, NewAssoc)` or `rb_insert(OldTree, Key, Value, NewTree)` will create _O(log N)_ new nodes. Note that the typical Prolog idiom of generating a new list from an old one, is an _O(N)_ algorithm; but if you use `append/3` it becomes _O(N)_. The following code illustrates some of the options (I haven’t tested any of this, so there could be typos): ```prolog % O(N) algorithm: transform([], []). transform([X|Xs], [Y|Ys]) :- pred(X, Y), transform(Xs, Ys). % O(N): transform(Xs, Ys) :- maplist(pred, Xs, Ys). % O(N^2) algorithm: transform(Xs, Ys) :- transform(Xs, [], Ys). transform([], Result, Result). transform([X|Xs], SoFar, Ys) :- pred(X, Y), append(SoFar, [X], SoFar2), transform(Xs, SoFar2, Ys). % O(N) algorithm: transform(Xs, Ys) :- transform(Xs, [], YsReverse), reverse(YsReverse, Ys). transform([], Result, Result). transform([X|Xs], SoFar, Ys) :- pred(X, Y), transform(Xs, [Y|SoFar, Ys). % O(N) algorithm: transform(Xs, Ys) :- phrase(transform(Xs), Ys). transform([]) --> []. transform([X|Xs]) --> { pred(X, Y) }, [Y], transform(Xs). % O(M + log N) algorithm for K-V pairs (see also `map_assoc/3): transform([], Assoc, Assoc). transform([K|Ks], Assoc0, Assoc) :- get_assoc(K, Assoc0, V0) pred(K, V0, V1), put_assoc(K, Assoc0, V1, Assoc1), transform(KVs, Assoc1, Assoc). ``` ---
**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\ **Post date:** [January 18, 2020, 8:41pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/7 "2020-01-18T20:41:12Z")
> [@peter.ludemann](#): > > That is correct – only one node is created. and > [@peter.ludemann](#): > > `append(OldList, [Item], NewList)` will create _N_ new nodes when creating `NewList` from `OldList` isnt this a contradiction … I am also unclear what the distinction between contents and node – the contents is an atom which essentially is a symbol - presumably in a symbol table pointed at – so adding an atom to a list should create another pointer (cons?) to the atom in the symbol table, and link it to the list. There would also be some need to handle the choice point and that the append could be removed during backtracking. But, for all this, is there a need to actually copy nodes? ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [January 18, 2020, 10:35pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/8 "2020-01-18T22:35:43Z")
`[a, b, c]` is represented like this: ```prolog +----+----+ +----+----+ +----+----+ +------+ | | ----->| | ----->| | ----->| nil | +--|-+----+ +--|-+----+ +--|-+----+ +------+ | | | | | | V V V +------+ +------+ +------+ + atom | + atom | + atom | + 'a' | + 'b' | + 'c' | +------+ +------+ +------+ ``` If you make a copy of the list with `d` at the end, you get this: ```prolog +----+----+ +----+----+ +----+----+ +------+ | | ----->| | ----->| | ----->| nil | +--|-+----+ +--|-+----+ +--|-+----+ +------+ | | | | | | V V V +------+ +------+ +------+ +------+ + atom | + atom | + atom | + atom | + 'a' | + 'b' | + 'c' | + 'd' | +------+ +------+ +------+ +------+ A A A A | | | | | | | | +--|-+----+ +--|-+----+ +--|-+----+ +--|-+----+ +------+ | | ----->| | ----->| | ----->| | ----->| nil | +----+----+ +----+----+ +----+----+ +----+----+ +------+ ``` There are _N_ new nodes created during the copying; each node can point at arbitrarily complex things, but there’s no need to copy any of what they point to. This is similar to “shallow copy” in imperative programming languages like C++ or Python. There’s no need for “deep copy” in Prolog because everything is immutable; in C++ or Python, deep copy is often used in case the original values are changed. After copying the list, if you garbage collect the first list, the atoms remain the same but they’re only pointed at by the second list of nodes. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [January 18, 2020, 10:43pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/9 "2020-01-18T22:43:36Z")
If you put `d` at the head of the list (`OldList=[a,b,c], NewList = [d|OldList]`), you end up with this: ```prolog NewList OldList | | | | V V +----+----+ +----+----+ +----+----+ +--|-+----+ +------+ | | ----->| | ----->| | ----->| | ---->| nil | +--|-+----+ +--|-+----+ +--|-+----+ +--|-+----+ +------+ | | | | | | | | V V V V +------+ +------+ +------+ +------+ + atom | + atom | + atom | + atom | + 'd' | + 'a' | + 'b' | + 'c' | +------+ +------+ +------+ +------+ ``` The `[a,b,c]` part is “shared” between the new list and the old list. Because it’s immutable, nothing more needs to be done. You don’t have to think about whether something is shared or copied; in fact, there are so-called “structure-sharing” and “structure-copying” implementations of Prolog that are identical from the programming point of view but that do different things when unifying. (There are no logical variables in the diagrams I’ve drawn, so I haven’t shown this distinction.) ---
**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\ **Post date:** [January 19, 2020, 4:58am UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/10 "2020-01-19T04:58:01Z")
Hi Peter, Many thanks for the helpful visualization and explanation > [@peter.ludemann](#): > > ou don’t have to think about whether something is shared or copied; I am very concerned about the runtime cost and whether its shared or copied would mean different runtime costs for an append operation (either via append or via the list construction i used). To make the point in the extreme, if for example I have a list of 100K items and add an item, I surely don’t want an internal copying of 100K pointer cells (cons cells in lisp jargon) happening just because i am adding another item. > [@peter.ludemann](#): > > here are _N_ new nodes created during the copying; > [@peter.ludemann](#): > > After copying the list, At the level I am currently working, I am appending a list – so, i am not deciding to copy or to share – I am “at the mercy” of the append implementation … But, if the append implementation is copying the current list’s cons cells just to add another item to a list, then I better look for an implementation that does not copy but merely adds a one of those “cons” cells. Edit: I would also not understand why cons cells would be copied in an append – what is the rationale for that – if merely adding a cons cell seems to suffice. ---
**Author:** ![michaelby](https://avatars.discourse-cdn.com/v4/letter/m/b3f665/32.png) [@michaelby](https://swi-prolog.discourse.group/u/michaelby)\ **Post date:** [January 19, 2020, 7:01am UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/11 "2020-01-19T07:01:33Z")
> [@grossdan](#): > > Edit: I would also not understand why cons cells would be copied in an append – what is the rationale for that – if merely adding a cons cell seems to suffice. This is what @peter.ludemann has explained: cons cells are only copied if necessary. **Consing to the front of a list will not copy the list.** ---
**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\ **Post date:** [January 19, 2020, 7:18am UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/12 "2020-01-19T07:18:43Z")
ok. good. thanks for clarifying further. Dan ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [January 19, 2020, 7:54pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/13 "2020-01-19T19:54:57Z")
> [@grossdan](#): > > I have a list of 100K items and add an item If you’re dealing with 100K items, then lists are probably not an appropriate data structure for you – they have _O(N)_ behaviour for almost all operations (prepending on the front is one exception, as is splitting the list into the first element and the rest – both of these are _O(1)_ but are not for languages such as Python). Without understanding your problem and your software design background, it’s difficult for me to give more advice than I’ve already done. If you could provide some more details (DM if you want it to remain private), then perhaps I can be more helpful. ---
**Author:** ![grossdan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/grossdan/32/23_2.png) [@grossdan](https://swi-prolog.discourse.group/u/grossdan)\ **Post date:** [January 19, 2020, 8:12pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/14 "2020-01-19T20:12:13Z")
HI Peter, Thank you for your comment and offer to PM. I said 100K just to give an extreme example – i don’t expect that many, but, the number of items could end up being large. Right now, the purpose of the list is to collect, during a search, items for which a condition holds – no additional processing is done on “my” side of the system. But, with your comment in mind, perhaps it could be useful to provide the list of items embodied in a more convenient data structure that could support a client in doing some additional processing – the cost from “my” side would be minimal, while the convenience provided to client code could be significant. Perhaps, in the future I could provide an option for a client to choose which data structure to use for providing the list. Dan ---
**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\ **Post date:** [January 19, 2020, 8:16pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/15 "2020-01-19T20:16:58Z")
Have you seen: [Does SWI-Prolog have N+K-trees?](https://swi-prolog.discourse.group/t/does-swi-prolog-have-n-k-trees/1310) Take a look at this [post](https://swi-prolog.discourse.group/t/does-swi-prolog-have-n-k-trees/1310/5) by Jan W. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [January 19, 2020, 8:33pm UTC](https://swi-prolog.discourse.group/t/copy-constructors-when-are-terms-copied-and-when-linked/1760/16 "2020-01-19T20:33:17Z")
If all you’re doing is collecting results, then I would suggest simply prepending each new result onto the list. If you need to get this in order of results, then use `reverse/2` before outputting; to remove duplicates, use `sort/2`. This is probably the simplest way and uses the least memory. The choice of any other data structure depends on how you want to access the contents. If by index, then something like N+K trees could be good; if by a key, then perhaps `library(assoc)` or `library(rbtrees)` (SWI-Prolog’s dicts, while convenient, are probably not appropriate for large amounts of data). In some cases, using `assertz/1` makes sense (with some appropriate provisos). Etc., etc.