# API Reference

All `tree` functions operate on nested tree-like structures. A structure is recursively defined as:

    Structure = Union[
        Any,
        Sequence['Structure'],
        Mapping[Any, 'Structure'],
        'AnyNamedTuple',
    ]

A single (non-nested) Python object is a perfectly valid structure:

    >>> tree.map_structure(lambda v: v * 2, 42)
    84
    >>> tree.flatten(42)
    [42]

You could check whether a structure is actually nested via `is_nested()`:

    >>> tree.is_nested(42)
    False
    >>> tree.is_nested([42])
    True

Note that `tree` only supports acyclic structures. The behavior for structures with cycle references is undefined.

tree.is_nested(structure)

  Checks if a given structure is nested.

      >>> tree.is_nested(42)
      False
      >>> tree.is_nested({"foo": 42})
      True

  Parameters:

    structure – A structure to check.

  Returns:

    True if a given structure is nested, i.e. is a sequence, a mapping, or a namedtuple, and False otherwise.

tree.assert_same_structure(a, b, check_types=True)

  Asserts that two structures are nested in the same way.

      >>> tree.assert_same_structure([(0, 1)], [(2, 3)])

  Note that namedtuples with identical name and fields are always considered to have the same shallow structure (even with check_types=True).

      >>> Foo = collections.namedtuple('Foo', ['a', 'b'])
      >>> AlsoFoo = collections.namedtuple('Foo', ['a', 'b'])
      >>> tree.assert_same_structure(Foo(0, 1), AlsoFoo(2, 3))

  Named tuples with different names are considered to have different shallow structures:

      >>> Bar = collections.namedtuple('Bar', ['a', 'b'])
      >>> tree.assert_same_structure(Foo(0, 1), Bar(2, 3))
      Traceback (most recent call last):
        ...
      TypeError: The two structures don't have the same nested structure.
      ...

  Parameters:

    - a – an arbitrarily nested structure.

    - b – an arbitrarily nested structure.

    - check_types – if True (default) types of sequences are checked as well, including the keys of dictionaries. If set to False, for example a list and a tuple of objects will look the same if they have the same size. Note that namedtuples with identical name and fields are always considered to have the same shallow structure.

  Raises:

    - ValueError – If the two structures do not have the same number of elements or if the two structures are not nested in the same way.

    - TypeError – If the two structures differ in the type of sequence in any of their substructures. Only possible if check_types is True.

tree.unflatten_as(structure, flat_sequence)

  Unflattens a sequence into a given structure.

      >>> tree.unflatten_as([[1, 2], [[3], [4]]], [5, 6, 7, 8])
      [[5, 6], [[7], [8]]]

  If structure is a scalar, flat_sequence must be a single-element list; in this case the return value is `flat_sequence[0]`.

      >>> tree.unflatten_as(None, [1])
      1

  If structure is or contains a dict instance, the keys will be sorted to pack the flat sequence in deterministic order. This is true also for `OrderedDict` instances: their sequence order is ignored, the sorting order of keys is used instead. The same convention is followed in `flatten()`. This correctly unflattens dicts and `OrderedDict`s after they have been flattened, and also allows flattening an `OrderedDict` and then unflattening it back using a corresponding plain dict, or vice-versa.

  Dictionaries with non-sortable keys cannot be unflattened.

      >>> tree.unflatten_as({1: None, 2: None}, ['Hello', 'world!'])
      {1: 'Hello', 2: 'world!'}

  Parameters:

    - structure – Arbitrarily nested structure.

    - flat_sequence – Sequence to unflatten.

  Returns:

    flat_sequence unflattened into structure.

  Raises:

    - ValueError – If flat_sequence and structure have different element counts.

    - TypeError – If structure is or contains a mapping with non-sortable keys.

tree.flatten(structure)

  Flattens a possibly nested structure into a list.

      >>> tree.flatten([[1, 2, 3], [4, [5], [[6]]]])
      [1, 2, 3, 4, 5, 6]

  If structure is not nested, the result is a single-element list.

      >>> tree.flatten(None)
      [None]
      >>> tree.flatten(1)
      [1]

  In the case of dict instances, the sequence consists of the values, sorted by key to ensure deterministic behavior. This is true also for `OrderedDict` instances: their sequence order is ignored, the sorting order of keys is used instead. The same convention is followed in `unflatten()`. This correctly unflattens dicts and `OrderedDict`s after they have been flattened, and also allows flattening an `OrderedDict` and then unflattening it back using a corresponding plain dict, or vice-versa.

  Dictionaries with non-sortable keys cannot be flattened.

      >>> tree.flatten({100: 'world!', 6: 'Hello'})
      ['Hello', 'world!']

  Parameters:

    structure – An arbitrarily nested structure.

  Returns:

    A list, the flattened version of the input structure.

  Raises:

    TypeError – If structure is or contains a mapping with non-sortable keys.

tree.flatten_up_to(shallow_structure, input_structure, check_types=True)

  Flattens input_structure up to shallow_structure.

  All further nested components in input_structure are retained as-is.

      >>> structure = [[1, 1], [2, 2]]
      >>> tree.flatten_up_to([None, None], structure)
      [[1, 1], [2, 2]]
      >>> tree.flatten_up_to([None, [None, None]], structure)
      [[1, 1], 2, 2]

  If shallow_structure and input_structure are not nested, the result is a single-element list:

      >>> tree.flatten_up_to(42, 1)
      [1]
      >>> tree.flatten_up_to(42, [1, 2, 3])
      [[1, 2, 3]]

  Parameters:

    - shallow_structure – A structure with the same (but possibly more shallow) layout as input_structure.

    - input_structure – An arbitrarily nested structure.

    - check_types – If True, check that each node in shallow_tree has the same type as the corresponding node in input_structure.

  Returns:

    A list, the partially flattened version of input_structure wrt shallow_structure.

  Raises:

    - TypeError – If the layout of shallow_structure does not match that of input_structure.

    - TypeError – If check_types is True and shallow_structure and input_structure differ in the types of their components.

tree.flatten_with_path(structure)

  Flattens a possibly nested structure into a list.

  This is a variant of `flattens()` which produces a list of pairs: `(path, item)`. A path is a tuple of indices and/or keys which uniquely identifies the position of the corresponding `item`.

      >>> tree.flatten_with_path([{"foo": 42}])
      [((0, 'foo'), 42)]

  Parameters:

    structure – An arbitrarily nested structure.

  Returns:

    A list of `(path, item)` pairs corresponding to the flattened version of the input structure.

  Raises:

    TypeError – If `structure` is or contains a mapping with non-sortable keys.

tree.flatten_with_path_up_to(shallow_structure, input_structure, check_types=True)

  Flattens input_structure up to shallow_structure.

  This is a combination of `flatten_up_to()` and `flatten_with_path()`

  Parameters:

    - shallow_structure – A structure with the same (but possibly more shallow) layout as input_structure.

    - input_structure – An arbitrarily nested structure.

    - check_types – If True, check that each node in shallow_tree has the same type as the corresponding node in input_structure.

  Returns:

    A list of `(path, item)` pairs corresponding to the partially flattened version of input_structure wrt shallow_structure.

  Raises:

    - TypeError – If the layout of shallow_structure does not match that of input_structure.

    - TypeError – If input_structure is or contains a mapping with non-sortable keys.

    - TypeError – If check_types is True and shallow_structure and input_structure differ in the types of their components.

tree.map_structure(func, *structures, **kwargs)

  Maps func through given structures.

      >>> structure = [[1], [2], [3]]
      >>> tree.map_structure(lambda v: v**2, structure)
      [[1], [4], [9]]
      >>> tree.map_structure(lambda x, y: x * y, structure, structure)
      [[1], [4], [9]]
      >>> Foo = collections.namedtuple('Foo', ['a', 'b'])
      >>> structure = Foo(a=1, b=2)
      >>> tree.map_structure(lambda v: v * 2, structure)
      Foo(a=2, b=4)

  Parameters:

    - func – A callable that accepts as many arguments as there are structures.

    - *structures – Arbitrarily nested structures of the same layout.

    - **kwargs – The only valid keyword argument is check_types. If True (default) the types of components within the structures have to be match, e.g. `tree.map_structure(func, [1], (1,))` will raise a TypeError, otherwise this is not enforced. Note that namedtuples with identical name and fields are considered to be the same type.

  Returns:

    A new structure with the same layout as the given ones. If the structures have components of varying types, the resulting structure will use the same types as `structures[0]`.

  Raises:

    - TypeError – If func is not callable.

    - ValueError – If the two structures do not have the same number of elements or if the two structures are not nested in the same way.

    - TypeError – If check_types is True and any two structures differ in the types of their components.

    - ValueError – If no structures were given or if a keyword argument other than check_types is provided.

tree.map_structure_up_to(shallow_structure, func, *structures, **kwargs)

  Maps func through given structures up to shallow_structure.

  This is a variant of `map_structure()` which only maps the given structures up to shallow_structure. All further nested components are retained as-is.

      >>> structure = [[1, 1], [2, 2]]
      >>> tree.map_structure_up_to([None, None], len, structure)
      [2, 2]
      >>> tree.map_structure_up_to([None, [None, None]], str, structure)
      ['[1, 1]', ['2', '2']]

  Parameters:

    - shallow_structure – A structure with layout common to all structures.

    - func – A callable that accepts as many arguments as there are structures.

    - *structures – Arbitrarily nested structures of the same layout.

    - **kwargs – No valid keyword arguments.

  Raises:

    ValueError – If func is not callable or if structures have different layout or if the layout of shallow_structure does not match that of structures or if no structures were given.

  Returns:

    A new structure with the same layout as shallow_structure.

tree.map_structure_with_path(func, *structures, **kwargs)

  Maps func through given structures.

  This is a variant of `map_structure()` which accumulates a path while mapping through the structures. A path is a tuple of indices and/or keys which uniquely identifies the positions of the arguments passed to func.

      >>> tree.map_structure_with_path(
      ...     lambda path, v: (path, v**2),
      ...     [{"foo": 42}])
      [{'foo': ((0, 'foo'), 1764)}]

  Parameters:

    - func – A callable that accepts a path and as many arguments as there are structures.

    - *structures – Arbitrarily nested structures of the same layout.

    - **kwargs – The only valid keyword argument is check_types. If True (default) the types of components within the structures have to be match, e.g. `tree.map_structure_with_path(func, [1], (1,))` will raise a TypeError, otherwise this is not enforced. Note that namedtuples with identical name and fields are considered to be the same type.

  Returns:

    A new structure with the same layout as the given ones. If the structures have components of varying types, the resulting structure will use the same types as `structures[0]`.

  Raises:

    - TypeError – If func is not callable or if the structures do not have the same layout.

    - TypeError – If check_types is True and any two structures differ in the types of their components.

    - ValueError – If no structures were given or if a keyword argument other than check_types is provided.

tree.map_structure_with_path_up_to(shallow_structure, func, *structures, **kwargs)

  Maps func through given structures up to shallow_structure.

  This is a combination of `map_structure_up_to()` and `map_structure_with_path()`

  Parameters:

    - shallow_structure – A structure with layout common to all structures.

    - func – A callable that accepts a path and as many arguments as there are structures.

    - *structures – Arbitrarily nested structures of the same layout.

    - **kwargs – No valid keyword arguments.

  Raises:

    ValueError – If func is not callable or if structures have different layout or if the layout of shallow_structure does not match that of structures or if no structures were given.

  Returns:

    Result of repeatedly applying func. Has the same structure layout as shallow_tree.

tree.traverse(fn, structure, top_down=True)

  Traverses the given nested structure, applying the given function.

  The traversal is depth-first. If `top_down` is True (default), parents are returned before their children (giving the option to avoid traversing into a sub-tree).

      >>> visited = []
      >>> tree.traverse(visited.append, [(1, 2), [3], {"a": 4}], top_down=True)
      [(1, 2), [3], {'a': 4}]
      >>> visited
      [[(1, 2), [3], {'a': 4}], (1, 2), 1, 2, [3], 3, {'a': 4}, 4]

      >>> visited = []
      >>> tree.traverse(visited.append, [(1, 2), [3], {"a": 4}], top_down=False)
      [(1, 2), [3], {'a': 4}]
      >>> visited
      [1, 2, (1, 2), 3, [3], 4, {'a': 4}, [(1, 2), [3], {'a': 4}]]

  Parameters:

    - fn –

      The function to be applied to each sub-nest of the structure.

      When traversing top-down:

        If `fn(subtree) is None` the traversal continues into the sub-tree. If `fn(subtree) is not None` the traversal does not continue into the sub-tree. The sub-tree will be replaced by `fn(subtree)` in the returned structure (to replace the sub-tree with None, use the special value `MAP_TO_NONE`).

      When traversing bottom-up:

        If `fn(subtree) is None` the traversed sub-tree is returned unaltered. If `fn(subtree) is not None` the sub-tree will be replaced by `fn(subtree)` in the returned structure (to replace the sub-tree with None, use the special value `MAP_TO_NONE`).

    - structure – The structure to traverse.

    - top_down – If True, parent structures will be visited before their children.

  Returns:

    The structured output from the traversal.

tree.MAP_TO_NONE = <object object>

  Special value for use with `traverse()`.