# Introduction

Trampolinen is a Python package that provides a decorator for writing programs that use deeply recursive function calls or tail calls. In addition, Trampolinen provides an implementation of lazy values (values that are computed only when demanded, by calling a function and caching the result), using the decorator to support deeply nested lazy values.

# Examples

## Inorder binary tree traversal

```from collections import namedtuple
from trampolinen import Trampolining, Ycall, Ytailcall

class Tree(namedtuple("Tree", ( "left", "value", "right" ))):
@Trampolining
def inorder_reduce(self, fn, acc):
if self.left is not None:
acc = yield Ycall(self.left.inorder_reduce, fn, acc)
acc = yield Ycall(fn, acc, self.value)
if self.right is not None:
acc = yield Ytailcall(self.right.inorder_reduce, fn, acc)
yield acc

t = Tree(Tree(None, 2, Tree(None, 4, None)), 1, Tree(None, 3, None))
def collect(acc, value):
acc.append(value)
return acc
print t.inorder_reduce(collect, []) # prints [2, 4, 1, 3]
```

## Lazy (incremental) quicksort

```from trampolinen.lazy import Lazy, LazyVal, Ytailcall

def lazy_quicksort(a):
def partition(low, high):
pivot = a[low]
i = low
for j in range(low + 1, high):
if a[j] < pivot:
i += 1
a[j], a[i] = a[i], a[j]
a[low], a[i] = a[i], a[low]
return i
def lazy_quicksort_helper(low, high, rest):
if low < high:
pos = partition(low, high)
right = Lazy(lazy_quicksort_helper, pos + 1, high, rest)
mid = LazyVal(( a[pos], right ))
return Ytailcall(lazy_quicksort_helper, low, pos, mid)
else:
return rest.ytailforce()
return Lazy(lazy_quicksort_helper, 0, len(a), LazyVal(None))

a = lazy_quicksort([2, 3, 4, 5, 1])
print a.force()[0] # partially sort and prints 1
print a.force()[1].force()[0] # sort some more and prints 2
```