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)
Bases: Generic
[_ReturnType
]
Represents a wrapped function call.
Primitive to convert recursion into an actual object.
func (Callable
[[ParamSpec
(_FuncParams
)], TypeVar
(_ReturnType
)]) –
args (ParamSpecArgs
) –
kwargs (ParamSpecKwargs
) –
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
See also
eli.thegreenplace.net/2017/on-recursion-continuations-and-trampolines
func (Callable
[[ParamSpec
(_FuncParams
)], Union
[TypeVar
(_ReturnType
), Trampoline
[TypeVar
(_ReturnType
)]]]) –
Callable
[[ParamSpec
(_FuncParams
)], TypeVar
(_ReturnType
)]