Deep-map for nested Python structures: preserve runtime shape, understand type hint limits and higher-kinded types

Learn how to deep-map nested lists, tuples, dicts and NamedTuples in Python, preserve shape at runtime, and why static type hints lack higher-kinded types.

Applying a function to every leaf inside an arbitrarily nested structure sounds simple until typing gets involved. Lists inside tuples inside lists, with a few dicts and homogeneous NamedTuple values sprinkled in — and the requirement that the output mirrors the input shape exactly. At runtime, that’s easy enough. Teaching a static type checker to see and guarantee that structure, though, runs straight into the edges of what Python’s type system can express today.

Problem setup

The goal is a map-like utility that walks through nested iterables of any depth, applies a callable to each leaf value, and returns a new structure with the same shape. Keys in dict objects must be preserved, and homogeneous NamedTuple values should be transformed field-wise.

>>> g = lambda x: x * 2
>>> payload = [([1, 2], [3, 4]), {"foo": 5, "bar": 6}]
>>> deep_apply(g, payload)
[([2, 4], [6, 8]), {"foo": 10, "bar": 12}]

Runtime implementation with type hints (the typing pain point)

Below is a working implementation that handles lists, tuples, dicts, generators, strings-as-leaves, and homogeneous NamedTuple values — while attempting to tell a type checker that the output shape is the same as the input. The behavior is correct at runtime, but the type-level story is where it falls short.

import inspect
from collections.abc import Iterable
from typing import Any, Callable, Generator, NamedTuple, cast
type Layer[T] = list[T] | tuple[T] | dict[Any, T] | Generator[T]
type DeepNest[T] = T | Layer["DeepNest[T]"]
def deep_apply[TIn, TOut](
        fn: Callable[[TIn], TOut], tree: DeepNest[TIn]
    ) -> DeepNest[TOut]:
    """
    Takes a nested iterable structure and applies fn to all of its nodes,
    returning them in the same structure.
    """
    kind = type(tree)
    match tree:
        case dict():
            return {
                k: deep_apply(fn, v)
                for k, v in tree.items()
            }
        # NamedTuple-like check
        case _ if hasattr(kind, "_fields") and isinstance(
                getattr(kind, "_fields"), tuple
            ):
            tmp = {
                k: deep_apply(fn, v)
                for k, v in cast(NamedTuple, tree)._asdict().items()
            }
            return cast(DeepNest[TOut], kind(**tmp))
        case _ if inspect.isgenerator(tree):
            return (deep_apply(fn, s) for s in tree)
        # str must be handled before Iterable
        case str():
            return fn(tree)
        case Iterable():
            kind = cast(type[list], kind)
            return kind(map(lambda s: deep_apply(fn, s), tree))
        case _:
            return fn(tree)

Why the type system can’t express the exact shape

The hard requirement — “the output object has exactly the same structure as the input” — cannot be expressed with current Python type hints. Even for flat lists, there are no structure-preserving type hints that would track element-level transformations while keeping the container shape fixed; in fact, such hints would run counter to the intended semantics of a list.

At best, you might hope to preserve union types level by level. That’s already a compromise because a level mixing lists and tuples would be typed as list | tuple, losing specific shape information. Conceptually, the mapping would look like this:

list[A | list[A | list[A]]] -> list[B | list[B | list[B]]]
list[A | tuple[A, A | list[A]] -> list[B | tuple[B, B | list[B]]

Even this looser preservation is out of reach. The obvious path would be to parameterize the “shape” by the leaf type, then remap the same shape with a new leaf type. That needs higher-kinded types — nested generics like C[A] — which Python does not have. A sketch of the desired signature makes that clear:

def deep_apply[A, B, C: NestedStructure](fn: Callable[[A], B], tree: C[A]) -> C[B]: ...

Those C[...]-style nested generics are not supported. There is an open feature request discussing higher-kinded types, and it hasn’t even been formulated into a PEP yet.

The constraints force this limitation. The leaf type before mapping is abstract, the leaf type after mapping is abstract, and the enclosing structure is itself abstract but identical across input and output. None of these abstractions can be inferred from the others, and in order to narrow the outer structure based on the inner leaf type, the type system would need the expressiveness of higher-kinded types. Python’s typing just isn’t there.

What you can do today

TL;DR: With current Python typing support, this is probably just impossible. Sorry.

You can keep the runtime behavior and basic annotations, understanding that type checkers won’t verify the structure preservation. If you do that, there is one small correction worth making to the annotations: for tuples you typically want the variadic form. The single-parameter form denotes a single-element tuple, not an arbitrary-length homogeneous tuple.

Same runtime behavior with a small annotation fix

This version keeps the exact behavior and clarifies that tuples are homogeneous and variadic at the type level.

import inspect
from collections.abc import Iterable
from typing import Any, Callable, Generator, NamedTuple, cast
type Layer[T] = list[T] | tuple[T, ...] | dict[Any, T] | Generator[T]
type DeepNest[T] = T | Layer["DeepNest[T]"]
def deep_apply[TIn, TOut](
        fn: Callable[[TIn], TOut], tree: DeepNest[TIn]
    ) -> DeepNest[TOut]:
    """
    Takes a nested iterable structure and applies fn to all of its nodes,
    returning them in the same structure.
    """
    kind = type(tree)
    match tree:
        case dict():
            return {
                k: deep_apply(fn, v)
                for k, v in tree.items()
            }
        # NamedTuple-like check
        case _ if hasattr(kind, "_fields") and isinstance(
                getattr(kind, "_fields"), tuple
            ):
            tmp = {
                k: deep_apply(fn, v)
                for k, v in cast(NamedTuple, tree)._asdict().items()
            }
            return cast(DeepNest[TOut], kind(**tmp))
        case _ if inspect.isgenerator(tree):
            return (deep_apply(fn, s) for s in tree)
        # str must be handled before Iterable
        case str():
            return fn(tree)
        case Iterable():
            kind = cast(type[list], kind)
            return kind(map(lambda s: deep_apply(fn, s), tree))
        case _:
            return fn(tree)

Why it’s important to know these limits

This is a practical example of where Python’s static typing draws the line. It’s tempting to model “same shape, different leaves” in types, but without higher-kinded types, you can’t. Recognizing that boundary helps you avoid overcomplicating annotations that the checker can’t meaningfully reason about, and it sets the right expectations when working with nested containers, dict keys that must remain untouched, and homogeneous NamedTuple values.

Takeaways

If you need a deep map that preserves shape at runtime, you can write it and keep straightforward annotations, aware they won’t capture the invariant you care about. If partial precision is acceptable, you can mentally model unions per level, but don’t expect static tools to track that mapping. If you use tuples as homogeneous sequences, annotate them with tuple[T, ...]. And if you’re hoping for shape-preserving guarantees, know that they’ll require higher-kinded types that Python simply doesn’t support yet.