One line tree implementation

Question

Based of this answer, I want to create a one line tree as part of another class like thus:

self._tree = collections.defaultdict(lambda: self._tree)

I will need to allow the users of said class to add path elements to the tree and run some callback starting at the lowest tree level. My naive implementation raises a error when I run pytest:

def _add(self, tree, path):
    for node in path:
        tree = tree[node]

def _run(self, tree, callback):
    for key in tree.keys():
        callback(tree[key]) # !!! Recursion detected (same locals & position)
        self._run(key)

This code works iff the tree is defined as

    def tree():
        return collections.defaultdict(tree)

    self._tree = tree()

Why is my naive approach not working with the lambda expression?

⚠ The Zen of Python states that

Simple is better than complex.

The one-line lambda makes the code complex where there is a simpler implementation. Therefore the one-line lambda should not be used in production code. However, I shall leave this question here for academic interest.

The method passed to `defaultdict` must create a new instance, not reference back to an existing object. In your case `tree` is a method that returns a new `defaultdict(tree)`, but your one-liner is a lambda that returns the original `self._tree` instance of `defaultdict(lambda: etc.)` — PaulMcG, Mar 02 '16 at 16:05
@PaulMcGuire: Then why does `d = collections.defaultdict(lambda: d); d['foo']['bar']` seems to work fine despite being ugly when printed? — Sardathrion - against SE abuse, Mar 02 '16 at 16:10
Kevin's answer and Tadhg McDonald-Jensen's comment illustrate the improper recursion in the one-line lambda approach. — PaulMcG, Mar 02 '16 at 16:17
looking back at the [that answer](http://stackoverflow.com/questions/635483/what-is-the-best-way-to-implement-nested-dictionaries-in-python/19829714#19829714) it was behaving the exact same way: instead of creating new sub dicts it only creates a reference to itself. (it shows {...} for dictionaries that are already displayed in recursive structure) — Tadhg McDonald-Jensen, Mar 02 '16 at 17:31

Kevin · Accepted Answer · 2016-03-03T00:04:49.653

7

The one-line defaultdict design in the first linked question doesn't look right to me. It produces unusual self-referential loops:

>>> d = collections.defaultdict(lambda: d)
>>> d["a"] = 23
>>> d["b"]["c"] = 42
>>> print d["b"]["a"] #we never created a value with these keys, so it should just return a defaultdict instance.
23
>>> #uh, that's not right...

A one-line lambda implementation of the function in your second link would look more like:

tree = lambda: defaultdict(tree); self._tree = tree()

Edit: looks like you can do it in a single statement with:

self._tree = (lambda f: f(f))(lambda t: defaultdict(lambda: t(t)))

... But requiring college-level lambda calculus skills just to shrink your script by one statement seems like an unwise bargain. Consider a more understandable approach.

edited Mar 03 '16 at 00:04

answered Mar 02 '16 at 16:12

Kevin

74,910
12
133
166

this is easy to verify with `assert d is d['b']` before a value is set to the key 'b'. it just refers back to itself. – Tadhg McDonald-Jensen Mar 02 '16 at 16:14
To preempt any comments asking "ok but can you do it in one line with no semicolons?" I think it's theoretically possible but it requires some rather tricky uses of lambda. Fixed-point combinators may be required. I'm still playing around with it. – Kevin Mar 02 '16 at 16:26
1

@Kevin: Thank you! Of course one should not be [assigning lambda in the first place](http://legacy.python.org/dev/peps/pep-0008/#programming-recommendations). – Sardathrion - against SE abuse Mar 02 '16 at 16:40
1

I got it with one line, I don't like it even a little bit but I got it. – Tadhg McDonald-Jensen Mar 02 '16 at 19:01
100% agree with your final statement, question edited to make that clear for future readers. – Sardathrion - against SE abuse Mar 03 '16 at 08:11

score 2 · Answer 2 · edited May 23 '17 at 10:33

even with the code from that answer it is having the exact same issue:

d = collections.defaultdict(lambda:d)
assert d is d[1] is d[2][4]

every sub dict is only creating a reference to itself instead of a new dictionary.

in order for this to work properly the lambda needs to create a new defaultdict object with itself (the lambda expression) as the first argument. However the only reference to the lambda is kept as self._tree.default_factory so the one-liner would have to look like this:

self._tree = collections.defaultdict(lambda:collections.defaultdict(self._tree.default_factory))

This is so inherently confusing that I cannot stress enough how much I recommend against doing it in one line.

100% agree with your final statement, question edited to make that clear for future readers. — Sardathrion - against SE abuse, Mar 03 '16 at 08:10

One line tree implementation

2 Answers2