robrix/Traversal — pull request #50 by robrix (2014-12-14 02:35:46+00:00)
Title: [WIP] Asynchrony

This branch demonstrates the relationship between folds/reducers and `Enumerable`/`Observable`–style signals.

While some properties of this relationship are demonstrable with ordinary (recursive) folds (as I discovered in an experiment involving [`Reducers.framework`](https://github.com/robrix/Reducers)), they are unable to model `zip` due to the inversion of control flow; `zip` must pull values from each of its operands, interleaving these calls, while reducers expect to push values to the combining function. Bridging the gap between the push semantics of reducers and the pull semantics of zip appeared to require continuations/coroutines, which are unavailable/untenable in C-family languages. (I believe this is why Clojure does not provide `zip` or other similar “multi-reducibles” as a reducer/transducer.)

Non-recursive left folds, as described by [Oleg Kiselyov](http://okmij.org/ftp/Streams.html#enumerator-stream), are a solution to this problem. They model the continuation of the fold by requiring that instead of calling itself recursively, the fold continues by calling into a `recur` parameter (`self` in the original papers, an unfortunate name for implementation in Swift). Add a fixpoint and you have a regular recursive fold; add some laziness and you have `Stream`.

As of this writing, this branch demonstrates what I found in my earlier experiment with `Reducers.framework`: `map` (the signal operator) is directly representable using folds/reducers:

- `map` is implemented as a reducer: reducing it causes it to reduce its underlying collection, mapping the elements using by composing the combining function with its mapping function
- `Source` is effectively a subject, and conforms to `ReducibleType` (i.e. it implements a non-recursive left fold)
- reducing a `Source` causes the `combine` function to be called when the `Source` produces new values
- since both `map` and observation of the `Source`’s values simply apply functions to values, reducing a `map` over a `Source` has the same desirable behaviour

I hypothesize that Traversal’s use of non-recursive folds will allow `zip` to be used with `Source`, resulting in fine-grained coordination between the push- and pull-APIs but _without_ requiring coroutines, continuations, or even manual intervention.

**TL;DR:** signals are asynchronous folds; mapping and reduction of signals is implementable with _precisely_ the same `map` and `reduce` operators already in use for mapping and reduction of synchronous collections; time is an illusion, lunchtime doubly so (which is probably why I forget it so often).

TBD:

- [ ] Interpret returns of `Either.left` as cancellation of observation
- [ ] Test the `zip` hypothesis
- [ ] Implement `filter` as a reducer
- [ ] Implement `flattenMap` as a reducer (this is known to be challenging; cf #26)
- [ ] Formalize the relationship between the `recur` parameter and schedulers (they’re effectively synonymous but it would be nice to show that)
- [ ] `Source` currently produces values lazily, using a sampling function and a `Memo`, such that if no observer evaluates the `Memo` then no sample is ever taken; this is desirable for some purposes but certainly ought to be documented
- [ ] Demonstrate the relationship between sinks and `reduce`, e.g. to bind a signal to some property