tessl/pypi-returns

Functional programming library providing type-safe containers for error handling, side effects, and composable operations with monadic patterns.

—

Pending

Overview

Eval results

Files

Trampolines

Name: tessl/pypi-returns
Author: tessl

Tail-call optimization utilities that convert recursive functions into iterative ones to avoid stack overflow errors. This enables safe recursion in Python for functional programming patterns.

Capabilities

Trampoline Container

A container that represents a computation step in a recursive algorithm, enabling tail-call optimization.

class Trampoline[T]:
    """Container for tail-call optimized recursion"""
    def __init__(self, computation: Callable[[], Trampoline[T] | T]): ...
    
    def run(self) -> T:
        """Execute the trampoline until completion"""
        
    def bind(self, func: Callable[[T], Trampoline[U]]) -> Trampoline[U]:
        """Bind a function returning Trampoline"""
        
    def map(self, func: Callable[[T], U]) -> Trampoline[U]:
        """Transform the final result"""

    @classmethod
    def done(cls, value: T) -> Trampoline[T]:
        """Create a completed trampoline"""
        
    @classmethod  
    def call(cls, func: Callable[[], Trampoline[T] | T]) -> Trampoline[T]:
        """Create a trampoline from a thunk"""

Trampoline Decorator

Convert recursive functions to use trampolines automatically.

def trampoline(func: Callable[..., Trampoline[T]]) -> Callable[..., T]:
    """Convert trampoline-returning function to regular function"""

Usage Examples

Basic Tail Recursion

from returns.trampolines import Trampoline, trampoline

# Traditional recursive factorial (stack overflow risk)
def factorial_recursive(n: int, acc: int = 1) -> int:
    if n <= 1:
        return acc
    return factorial_recursive(n - 1, acc * n)

# Trampoline version (stack safe)
def factorial_trampoline(n: int, acc: int = 1) -> Trampoline[int]:
    if n <= 1:
        return Trampoline.done(acc)
    return Trampoline.call(lambda: factorial_trampoline(n - 1, acc * n))

@trampoline  
def factorial(n: int) -> Trampoline[int]:
    return factorial_trampoline(n)

# Safe for large numbers
result = factorial(10000)  # No stack overflow

Mutual Recursion

from returns.trampolines import Trampoline, trampoline

def is_even_trampoline(n: int) -> Trampoline[bool]:
    if n == 0:
        return Trampoline.done(True)
    return Trampoline.call(lambda: is_odd_trampoline(n - 1))

def is_odd_trampoline(n: int) -> Trampoline[bool]:
    if n == 0:
        return Trampoline.done(False)
    return Trampoline.call(lambda: is_even_trampoline(n - 1))

@trampoline
def is_even(n: int) -> Trampoline[bool]:
    return is_even_trampoline(n)

@trampoline    
def is_odd(n: int) -> Trampoline[bool]:
    return is_odd_trampoline(n)

# Safe for large numbers
result = is_even(100000)  # True, no stack overflow

List Processing

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

def sum_list_trampoline(items: List[int], acc: int = 0) -> Trampoline[int]:
    if not items:
        return Trampoline.done(acc)
    return Trampoline.call(
        lambda: sum_list_trampoline(items[1:], acc + items[0])
    )

@trampoline
def sum_list(items: List[int]) -> Trampoline[int]:
    return sum_list_trampoline(items)

# Process large lists safely  
large_list = list(range(50000))
total = sum_list(large_list)  # No stack overflow

Trampoline with Container Integration

from returns.trampolines import Trampoline, trampoline
from returns.result import Result, Success, Failure
from returns.maybe import Maybe, Some, Nothing

def safe_divide_recursive(
    dividend: float, 
    divisor: float, 
    depth: int = 0
) -> Trampoline[Result[float, str]]:
    if depth > 100:
        return Trampoline.done(Failure("Maximum recursion depth reached"))
    
    if divisor == 0:
        return Trampoline.done(Failure("Division by zero"))
        
    if dividend < 1:
        return Trampoline.done(Success(dividend))
        
    # Continue dividing
    return Trampoline.call(
        lambda: safe_divide_recursive(dividend / divisor, divisor, depth + 1)
    )

@trampoline
def safe_divide_until_small(dividend: float, divisor: float) -> Trampoline[Result[float, str]]:
    return safe_divide_recursive(dividend, divisor)

# Safe recursive division
result = safe_divide_until_small(1000000.0, 2.0)  # Success(small_number)

Performance Benefits

Trampolines provide several advantages for recursive algorithms:

Stack Safety: Eliminates stack overflow errors for deep recursion
Memory Efficiency: Uses constant stack space regardless of recursion depth
Composability: Works with other functional programming constructs
Debugging: Easier to debug than traditional recursion

When to Use Trampolines

Use trampolines when:

Implementing naturally recursive algorithms (factorial, fibonacci, tree traversal)
Processing large data structures recursively
Converting imperative loops to functional style
Implementing recursive descent parsers
Working with recursive data structures (linked lists, trees)

Trampolines enable safe functional programming patterns that would otherwise be limited by Python's recursion depth limit.

Install with Tessl CLI