cascade.core — town.lilac/cascade 2.0.1

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.

-eq-sequential clj/s

(-eq-sequential k xs ys)

-eq-unordered clj/s

(-eq-unordered k xs ys)

-reduce-kv-map clj/s

(-reduce-kv-map k step acc coll)

-reduce-kv-vec clj/s

(-reduce-kv-vec k step idx acc coll)

cat clj/s

(cat rf)

comp clj/s

(comp f)

(comp f g)

(comp f g & more)

Composes continuation-passing functions. The returned function accepts a continuation as its first argument and a variable number of additional args, calls the last function with a continuation of the next one and the arguments, and so on right-to-left.

complement clj/s

(complement f)

Takes a continuation-passing function f and returns a new continuation- passing function which accepts the same args, does the same effects (if any) and calls the passed in continuation with the opposite truth value.

cont-with clj/s

(cont-with f)

(cont-with f x)

(cont-with f x y)

(cont-with f x y z)

(cont-with f x y z & args)

Takes a non-continuation passing function f and any arguments to apply to the front. Returns a function that accepts a continuation as the first argument, and when called applies f with the initial args and then any additional args passed to the new function, passing the result to the continuation.

drop clj/s

(drop n)

(drop n coll)

(drop k n coll)

drop-while clj/s

(drop-while pred)

(drop-while pred coll)

(drop-while k pred coll)

eq clj/s

(eq x y)

(eq k x y)

Just like clojure.core/=, but works for very nested data structures. Supports deep equality of all Clojure data types. For custom data types that you want to descend into, implement IEqualWithContinuation.

filter clj/s

(filter pred)

(filter pred coll)

(filter k pred coll)

Applies pred, a continuation-passing function, to each element of coll and collects elements which pass a truth-y value into a list.

If a continuation k is passed in, calls it with the final result list. If f and a coll are passed in, trampolines and returns the result list. If only a function f is passed in, returns a continuation-passing transducer function for use with cascade.core/transduce.

identity clj/s

(identity k x)

Calls k with x.

IEqualWithContinuation clj/s protocol

A protocol for comparing two values using continuation-passing. Used by eq to allow outside extension to custom data types.

-eq clj/s

(-eq x k y)

Accepts a continuation k and another value y, and either calls the continuation with a boolean representing whether they are equal, or returns a thunk (0-arity function) that when called will continue the operation.

See cascade.core/-eq-sequential and cascade.core/-eq-unordered for examples how to write recursive CPS algorithms comparing two complex data structures.

into clj/s

(into to xform from)

(into k to xform from)

Returns a new collection consisting of to with all of the items resulting from trasnducing from with xform. xform should be a continuation-passing transducer. See cascade.core/map, cascade.core/filter, et al.

keep clj/s

(keep pred)

(keep pred coll)

(keep k pred coll)

Applies pred, a continuation-passing function, to each element of coll and collects all truth-y results into a list.

If a continuation k is passed in, calls it with the final result list. If f and a coll are passed in, trampolines and returns the result list. If only a function f is passed in, returns a continuation-passing transducer function for use with cascade.core/transduce.

map clj/s

(map f)

(map f coll)

(map k f coll)

(map k f coll & colls)

Applies f, a continuation-passing function, to each element of coll and collects the results into a list.

If a continuation k is passed in, calls it with the final result list. If f and a coll are passed in, trampolines and returns the result list. If only a function f is passed in, returns a continuation-passing transducer function for use with cascade.core/transduce.

map-into clj/s

(map-into f acc coll)

(map-into k f acc coll)

Continuation-passing style of (into acc (map f) coll). Calls (f k x) for all x in coll. f must call the passed in continuation c with the transformed value. conj's the transformed value on to acc. Calls passed in continuation k with final result, or trampolines when not.

mapcat clj/s

(mapcat f)

(mapcat k f & colls)

reduce clj/s

(reduce step acc coll)

(reduce k step acc coll)

(reduce k step acc coll el)

Continuation-passing style version of reduce. Calls (step k acc x) for all elements in seqable coll. The step function should call the passed in continuation k with the new accumulated value. If passed in, calls the continuation k with final result. Else trampolines and returns the result.

reduce-kv clj/s

(reduce-kv step acc coll)

(reduce-kv k step acc coll)

remove clj/s

(remove pred)

(remove pred coll)

(remove k pred coll)

Applies pred, a continuation-passing function, to each element of coll and collects elements which pass a false-y value into a list.

If a continuation k is passed in, calls it with the final result list. If f and a coll are passed in, trampolines and returns the result list. If only a function f is passed in, returns a continuation-passing transducer function for use with cascade.core/transduce.

some clj/s

(some predk coll)

(some k predk coll)

take clj/s

(take n)

(take n coll)

(take k n coll)

A continuation-passing, thunk-producing version of clojure.core/take.

If a continuation k is passed in, returns a thunk that can be called with trampoline and will call k with a list of the first n items of coll. If only n and coll are passed in, eagerly trampolines and returns the result. If only n is passed in, returns a continuation-passing transducer function for use with cascade.core/transduce.

take-while clj/s

(take-while pred)

(take-while pred coll)

(take-while k pred coll)

transduce clj/s

(transduce xform rf coll)

(transduce xform rf init coll)

(transduce k xform rf init coll)

Continuation-passing style version of clojure.core/transduce. Takes continuation-passing reducing function rf and a CPS xform (see cascade.core/map, cascade.core/filter, et al.) and applies (xform rf). Then, reduces the collection using that new reducing fn.