Counting 'absolute' nesting levels of an iterable

Question

I need to write a function to count numbers of nests in an iterable. I reached my goal but wondering if there's any more neat/faster solution (maybe even a library or so?). Besides I'm afraid that my code is error prone.

Let's analyze two examples:

dct_test = {
    "a": {1: 2, 2: 3, 3: 4},
    "b": {"x": "y", "z": [1, 2, 3, {7, 8}]},
    "c": {"l": (2, 3, 5), "j": {"a": {"k": 1, "l": [1, 3, (2, 7, {"x": 1})]}}},
    "d": [1, (2, 3)]
}

tpl_test = (1, [3, 4, {5, 6, 7}], {"a": 5, "b": [9, 8]})

This is a visualization of what I'm trying to achieve:

Code:

from collections.abc import Iterable
from itertools import chain

# EXAMPLES
dct_test = {
    "a": {1: 2, 2: 3, 3: 4},
    "b": {"x": "y", "z": [1, 2, 3, {7, 8}]},
    "c": {"l": (2, 3, 5), "j": {"a": {"k": 1, "l": [1, 3, (2, 7, {"x": 1})]}}},
    "d": [1, (2, 3)]
}

tpl_test = (1, [3, 4, {5, 6, 7}], {"a": 5, "b": [9, 8]})

# FUNCTIONS
# checking if an argument is a 'real' iterable (list, tuple, set, dictionary)
def IsRealIterable(
    iter: Iterable
):
    return True if isinstance(iter, Iterable) and not isinstance(iter, str) else False

# converting an iterable to a list
def ConvertIterableToList(
    iter: Iterable,
    dct_keys=False, # False returns dict.values(), True returns dict.keys()
):
    if IsRealIterable(iter):
        if isinstance(iter, tuple) or isinstance(iter, set):
            return list(iter)
        
        elif isinstance(iter, dict):
            return list(iter.keys()) if dct_keys else list(iter.values())
        
        elif isinstance(iter, list):
            return iter
    else:
        raise TypeError("Given argument is not a list, tuple, set or dictionary")

# returns a list of iterables extracted from an iterable
def ExtractFromIterable(
    iter: Iterable
):
    if IsRealIterable(iter):
        return [i for i in ConvertIterableToList(iter) if IsRealIterable(i)]
    else:
        raise TypeError("Given argument is not a list, tuple, set or dictionary")

# returns number of levels in an iterable
def CountNestingLevels(
    iter: Iterable,
    cntr: int=0,
    only_sublevels: bool=True # if False then returns number of all nesting levels - not only a number of nests
):

    lst_to_inspect = ExtractFromIterable(iter)
    
    lst_deep = [] # empty list for nested iterables
    
    # analyzing structure
    # if lst_to_inspect is empty then returns already counted number of levels
    if not lst_to_inspect:
        return cntr if only_sublevels else cntr + 1
    else:
        cntr += 1
        
        for i in lst_to_inspect:
            
            # temporary list for iterables from each element in lst_to_inspect
            temp_list = ExtractFromIterable(i)
            # elements (only non-empty) should be added to lst_deep because otherwise ExtractFromIterable() would overwrite existing values
            lst_deep.append(temp_list) if temp_list else None

    # flattening lst_deep. it contains lists returned by ExtractFromIterable so lst_deep has structure: [[[], [], ...]]
    lst_deep = list(chain.from_iterable(lst_deep))
    
    # using ExtractFromIterable in lst_deep may return the same structure as lst_to_inspect
    # if no - use recursion to analyze remaining elements again
    # if yes - finish analyzing
    if lst_deep != lst_to_inspect:
        return CountNestingLevels(lst_deep, cntr)
    else:
        return cntr if only_sublevels else cntr + 1

print(CountNestingLevels(dct_test)) # returns 6
print(CountNestingLevels(tpl_test)) # returns 2

Do you have any tips how to improve this code?

Answer 1

In more than one place your code assumes that it is restricted to tuple, list, set, or dict. That's a perfectly reasonable policy decision for code like this. Given that decision, the code to check for iterability is needlessly complex. Something along these lines would do the trick:

isinstance(obj, (tuple, list, set, dict))

If your goal is to count nesting levels, there is no need to convert all of those data structures into a list form. It's extra code and extra computation. The only complication will be distinguishing dict from the other three types of supported objects -- but that's easy enough to do.

If we focus narrowly on lists, the depth of a list is just one plus the maximum of the depths of any sublists. Very roughly like this:

def depth(xs):
    if isinstance(xs, list):
        return 1 + max(depth(x) for x in xs)
    else:
        return 0

But that code will fail, for example, if the list is empty, because max() will raise a ValueError.

So we can revise that rough draft to handle the empty case. In the process, we can also handle the other three collection types:

def depth(obj):
    xs = (
        obj if isinstance(obj, (tuple, list, set)) else
        obj.values() if isinstance(obj, dict) else
        None
    )
    return (
        0 if xs is None else           # Not a collection.
        1 if not xs else               # Empty collection.
        1 + max(depth(x) for x in xs)  # Non-empty.
    )

Finally, note that depth() differs from your implementation because it counts the top level, so it returns depths one greater than your calculations. That makes more sense to me, because it distinguishes the supported data types (which always have a depth of at least one) from the unsupported data types (which have a depth of zero). Maintaining that distinction allows the algorithm to be composed more easily in a recursive context. Adjust as needed.

Answer 2

I think we could make use of recursivity, as well as dunder (double underscore) attribute. For example

def is_iterable(a):
    if "__iter__" in a.__dir__():
        print("I am an iterable ! You can do `for x in a`")
    else:
        print("I am not an iterable ! You can move on")

>>> a_dict = {"5": 3}
>>> is_iterable(a_dict)
I am an iterable ! You can do `for x in a`
>>> a_list = [1]
>>> is_iterable(a_list)
I am an iterable ! You can do `for x in a`
>>> a_int = 7
>>> is_iterable(a_int)
I am not iterable ! You can move on
>>> a_set = {3}
>>> is_iterable(a_set)
I am an iterable ! You can do `for x in a`

With that, you can now check if the object you have is iterable, if it is, you iterate over it (for x in the_iterable) and call the same function on all the items of that iterable, incrementing a function parameter counter by 1 at each step

def recursive_function(an_object, counter=0):
    if "__iter__" in an_object.__dir__():
        for x in an_object:
            recursive_function(x, counter+1)

Now the last part is to keep the highest counter, but I think you got the idea !

This should use memory and time way more efficiently

Hope this helps !