# Del\_dict/4 behaviour and dict iteration **URL:** \ **Category:** Predicate\ **Created:** [July 3, 2021, 11:23am UTC](https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135 "2021-07-03T11:23:11Z")\ **Posts on this page:** 6\ **Page:** 1
**Author:** ![oskardrums](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/oskardrums/32/3594_2.png) [@oskardrums](https://swi-prolog.discourse.group/u/oskardrums)\ **Post date:** [July 3, 2021, 11:23am UTC](https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135/1 "2021-07-03T11:23:11Z")
Hey all, I want to iterate over a possibly nested dict and apply some transformation on it’s atomic members, so I tried something along these lines: ```prolog transformed(D0, D) :- del_dict(Key, D0, Value0, D1), ( atomic(Value0) -> foo(Value0, Value) ; transformed(Value0, Value) ), transformed(D1, D2), put_dict(Key, D2, Value, D). ``` But, this approach doesn’t work as del\_dict/4 throws an instantiation error: ```prolog Welcome to SWI-Prolog (threaded, 64 bits, version 8.3.26) SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software. Please run ?- license. for legal details. For online help and background, visit https://www.swi-prolog.org For built-in help, use ?- help(Topic). or ?- apropos(Word). ?- D0 = dict{a:b}, del_dict(A, D0, B, D). ERROR: Arguments are not sufficiently instantiated ERROR: In: ERROR: [11] del_dict(_26520,dict{a:b},_26524,_26526) ERROR: [10] ''(user:user: ...) ERROR: [9] toplevel_call(user:user: ...) at /opt/local/lib/swipl/boot/toplevel.pl:1115 ?- ``` Is this the behavior of del\_dict/4 intended? Compare to get\_dict/3, which doesn’t throw and instead unifies A with some key: ```prolog ?- D = dict{a:b}, get_dict(A, D, B). D = dict{a:b}, A = a, B = b. ``` What would be the recommended way to perform such a dict transformation? Thanks. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [July 3, 2021, 12:02pm UTC](https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135/2 "2021-07-03T12:02:41Z")
There is no need to delete first, is there? So you can use get\_dict/3 and put\_dict/3 together. This suggests however that you want to use some _failure driven_ loop. That is not going to work. Dicts are subject to the normal Prolog backtracking. You **can** use nb\_set\_dict/3 for non-backtrackble destructive assignment. Not sure I’d recommend that 🙂 Quite often dict transformation use dict\_pairs/3 and than manipulate the pair list to call dict\_pairs/3 again and create a new dict. ---
**Author:** ![oskardrums](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/oskardrums/32/3594_2.png) [@oskardrums](https://swi-prolog.discourse.group/u/oskardrums)\ **Post date:** [July 3, 2021, 12:34pm UTC](https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135/3 "2021-07-03T12:34:48Z")
Thank you for the quick response. I’ve neglected in the above snippet the termination condition, should’ve been: ```prolog transformed(Tag{}, Tag{}). transformed(D0, D) :- ... ``` So my thinking was that deletion is needed in order to get to the termination condition, otherwise I get an infinite loop: ```prolog transformed(Tag{}, Tag{}). transformed(D0, D) :- get_dict(Key, D0, Value0), ( atomic(Value0) -> foo(Value0, Value) ; transformed(Value0, Value) ), transformed(D0, D2), put_dict(Key, D2, Value, D). ?- transformed(_{a:b, c:_{d:e}}, T). ERROR: Stack limit (1.0Gb) exceeded ERROR: Stack sizes: local: 0.7Gb, global: 0.2Gb, trail: 39.3Mb ERROR: Stack depth: 2,572,409, last-call: 0%, Choice points: 2,572,402 ERROR: Probable infinite recursion (cycle): ERROR: [2,572,408] transformed(, _66885952) ERROR: [2,572,407] transformed(, _66885978) ``` It works if I add the deletion: ```prolog foo(X, Y) :- atomic_list_concat(['bar', X, 'baz'], '/', Y). transformed(Tag{}, Tag{}). transformed(D0, D) :- get_dict(Key, D0, Value0), del_dict(Key, D0, _, D1), ( atomic(Value0) -> foo(Value0, Value) ; transformed(Value0, Value) ), transformed(D1, D2), put_dict(Key, D2, Value, D). ?- transformed(_{a:b, c:_{d:e}}, T). T = _3574{a:'bar/b/baz', c:_3560{d:'bar/e/baz'}} . ``` But that get\_dict, del\_dict dance is not the peak of elegance. So I guess dict\_pairs/3 it is 👍 Thanks @jan ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [July 3, 2021, 3:54pm UTC](https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135/5 "2021-07-03T15:54:19Z")
> [@anon95304481](#): > > But in the present transform, if you do not change the field names, no re-sorting is needed. True. The docs make is explicit not to make claims about the internal structure of dicts though. For some deep-down reason the keys and values have swapped position. Other changes may follow (there are no concrete plans). ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [July 3, 2021, 4:30pm UTC](https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135/7 "2021-07-03T16:30:10Z")
> [@anon95304481](#): > > Insert is still O(n), because you need to create/copy a new dict? The search for the insert location is O(log(N)). Next you have to make a new dict and copy the data. Copying the data are two simple memcpy() calls (the part before the new key and the part that follow it). So, yes, insert in O(n), but the constant factor is pretty low. Long time I did a comparison with rbtrees and If I recall correctly rbtrees started to win around 1,000 k-v pairs. May have changed a bit. In other words, used for representing compound data structures they are typically fine. They are not suitable to implement (for example) word-counting a document using _for each word, update the count in the dict by one_. The way to implement that is to make a flat list of words, use sort/4 (or msort/2) to sort while keeping duplicates and walk over the list to establish the counts. Next you can do dict\_pairs/3 to create a dict for subsequent lookup if an on-stack data structure is desirable. ---
**Author:** ![oskardrums](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/oskardrums/32/3594_2.png) [@oskardrums](https://swi-prolog.discourse.group/u/oskardrums)\ **Post date:** [July 3, 2021, 10:22pm UTC](https://swi-prolog.discourse.group/t/del-dict-4-behaviour-and-dict-iteration/4135/9 "2021-07-03T22:22:17Z")
I didn’t consider the O(n) cost of copying the dict on each del\_dict/4 and put\_dict/4, thank you! My actual per-atomic logic is quite expensive itself, so the traversal does not seem to be a significant bottleneck. I’ve put together a quick benchmark that applies our actual transformation to the atomic elements and got a 2.8 percent speedup with the dict\_pairs/2 approach and a 4.2 percent improvement with (=…)/2, both compared to my original get\_dict/3, del\_dict/4, put\_dict/4 based implementation.