cascade

# cascade

Cascade is a library of continuation-passing, tail recursive versions of many
Clojure core functions.

The goal is to allow essentially unbounded recursion and mutual recursion of
seq operations. This means that the seq operations in this library must not
use the call stack. Instead, they use a combination of continuation-passing to
ensure that operations can always be in the tail position and trampolining to
ensure that operations do not use the call stack.

This provides the ability to write recursive algorithms that work on very nested
data structures in Clojure(Script) using familiar operations.

It aims to cover
- seq operations: reduce, transduce, into, and common transducer-producing fns
- CPS fn composition: identity, complement, comp

All seq operations can be passed a continuation as first argument, which will
be called on completion of the operation, and returns a thunk (0-arity
function) which can be called to begin the operation. A thunk will return
either another thunk, which can be called to continue the operation, or the
result. Thus, they are meant to be used with `clojure.core/trampoline`.

If a continuation is not passed in to most seq operations, it is assumed you
want to run the operation eagerly and will trampoline for you, returning the
result.

## Transducers

Transducer-producing functions like `map`, `filter`, etc. take functions which
accept a continuation and the element of the sequence they are operating on, and
should call the continuation with the result instead of returning it.

When passed a single function, they return a transducer for use with
`cascade.core/transduce` and `cascade.core/into`.

When passed a function and a collection, they will eagerly execute the operation
using `trampoline` and return the result.

When passed a continuation, a function and a collection, they will return a
thunk, meaning it can be trampolined.

## Examples

For an example of how this can be used practically, see `cascade.hike`.

What is a hike, but a really long walk?

Like clojure.walk, but defines `walk` in a way that supports walking very
large, nested data structures without using the call stack.

Defines recursive tree operations for Clojure data structures. Functions in
this namespace take any data structure (list, vector, map, set, seq) and
traverses those forms.

`cascade.hike/walk` is a generic tree walker that uses continuation-passing
and returns thunks. It takes any data structure, calls a function with a
continuation on every element, and uses the value passed into the continuation
in place of the original. This makes it easier to write recursive search-and-replace
functions for very nested data that do not use the call stack, as shown in the
rest of the functions in this namespace.