Trampolines¶

Python does not support TCO (tail call optimization), so any recursion-based algorithms become dangerous.

We cannot be sure that they won’t cause RecursionError on deeply nested data.

Here’s why we need trampolines: they allow to replicate tail call optimization by wrapping function calls into returns.trampolines.Trampoline objects, making recursion-based function always safe.

Example:

>>> from typing import Union, List
>>> from returns.trampolines import Trampoline, trampoline

>>> @trampoline
... def accumulate(
...     numbers: List[int],
...     acc: int = 0,
... ) -> Union[int, Trampoline[int]]:
...    if not numbers:
...        return acc
...    number = number = numbers.pop()
...    return Trampoline(accumulate, numbers, acc + number)

>>> assert accumulate([1, 2]) == 3
>>> assert accumulate([1, 2, 3]) == 6

The following function is still fully type-safe: - Trampoline object uses ParamSpec to be sure that passed arguments are correct - Final return type of the function is narrowed to contain only an original type (without Trampoline implementation detail)

API Reference¶

final class Trampoline(func, /, *args, **kwargs)[source]¶

Bases: Generic[_ReturnType]

Represents a wrapped function call.

Primitive to convert recursion into an actual object.

Parameters:

func (Callable[[ParamSpec(_FuncParams)], TypeVar(_ReturnType)]) –
args (ParamSpecArgs) –
kwargs (ParamSpecKwargs) –

func¶

args¶

kwargs¶

trampoline(func)[source]¶

Convert functions using recursion to regular functions.

Trampolines allow to unwrap recursion into a regular while loop, which does not raise any RecursionError ever.

Since python does not have TCO (tail call optimization), we have to provide this helper.

This is done by wrapping real function calls into returns.trampolines.Trampoline objects:

>>> from typing import Union
>>> from returns.trampolines import Trampoline, trampoline

>>> @trampoline
... def get_factorial(
...     for_number: int,
...     current_number: int = 0,
...     acc: int = 1,
... ) -> Union[int, Trampoline[int]]:
...     assert for_number >= 0
...     if for_number <= current_number:
...         return acc
...     return Trampoline(
...         get_factorial,
...         for_number,
...         current_number=current_number + 1,
...         acc=acc * (current_number + 1),
...     )

>>> assert get_factorial(0) == 1
>>> assert get_factorial(3) == 6
>>> assert get_factorial(4) == 24