A list where there are lists inside e.g. list[list[int]]

Recursive Definition

A nested list of integers:

• $\forall n \in \mathbb{Z}$, the single integer $n$ is a nested list of integers
• $\forall k \in \mathbb{Z}$ and nested lists of integers $a_{0},a_{1},\dots,a_{k-1}$, the list $[a_{0},a_{1},\dots,a_{k-1}]$ is also a nested list of integers

Each of the $a_i$ is called a sublist of the outer list

It may seem odd to include a single integer as a nested list, but it makes the definition and further code more elegant

Operations

Nested List Sum

Recursive definition: $$ \text{nested\_sum(x)} = \begin{cases} x, & x \in \mathbb{Z} \\ \sum_{i=0}^{k-1} \text{nested\_sum(x)}, & x = [a_{0},a_{1},\dots,a_{k-1}] \end{cases} $$

Python implementation:

def sum_nested_v1(nested_list: int | list) -> int:
    """Return the sum of the given nested list.

    This version uses a loop to accumulate the sum of the sublists.
    """
    if isinstance(nested_list, int):
        return nested_list
    else:
        sum_so_far = 0
        for sublist in nested_list:
            sum_so_far += sum_nested_v1(sublist)
        return sum_so_far


def sum_nested_v2(nested_list: int | list) -> int:
    """Return the sum of the given nested list.

    This version uses a comprehension and the built-in sum aggregation function.
    """
    if isinstance(nested_list, int):
        return nested_list
    else:
        return sum(sum_nested_v2(sublist) for sublist in nested_list)

Inductive Reasoning for this code

How to reason the code with the inductive approach or partial tracing Trace of the call:

>>> sum_nested_v1([1, [2, [3, 4], 5], [6, 7], 8])
36

Here, the recursive step will execute, since the argument is a nested_list Setup a loop accumulation table since there are more than one recursive call

The Function Design Recipe for nested lists

def f(nested_list: int | list) -> ...:
    if isinstance(nested_list, int):
        ...
    else:
        accumulator = ...

        for sublist in nested_list:
            rec_value = f(sublist)
            accumulator = ... accumulator ... rec_value ...

        return accumulator