Is there a "complete" set of functions/operators for FRP?

Question

Functional Reactive Programming is an approach to specify side-effecting programs in a pure functional way.

Recently I've been using rxscala, which is the Java/Scala port port of ReactiveX. It is based around the concept of Observables that can be regarded as streams of values of a certain type.

For this question I want to exclude FRP approaches that handle time-continuous changes (signals).

Building new Observables from old ones

These Observables can be combined using a wealth of different functions to create new observables. These are similar to the functions that can be applied to collections. And those are already quite well understood, as we know Foldable, Traversable, Applicative, Monads and the like.

Indeed observables are foldable, traversable monads, like ordinary collections. But these traits can be implemented in multiple ways for observables, as an observable holds much more information (the timing information for each element) than an ordinary collection. And the result also has to be fitted with timing information.

Two Monad implementations

For example the monadic join (flatMap in Scala) can be implemented in at least two different, plausible ways:

• By switching between the nested observables, which results in truncating the currently active observable, once the next one begins emission, or

  RxJava Switch Visualization http://reactivex.io/documentation/operators/images/switch.c.png

• by mergeing the nested observables without dropping or delaying any events.

  RxJava Merge Visualization http://reactivex.io/documentation/operators/images/mergeDelayError.C.png

• ... and much much more (see the comments)

Limitations

I'm very pleased with the provided repertoire of combinator functions, but I keep running into situations where I'm not able to achieve what I want, and I have to fall back to some kind of concurrent programming.

Missing combinators or brains?

Now I'm wondering whether I'm just too stupid to construct the desired behavior using existing combinators. Or is it the case that the combinator functions available in rxscala are not sufficient to create every imaginable behavior?

Question

I'm asking for a proof that some basic set of combination functions B is enough to create "every conceivable observable" from some input observables.

Possibly the hardest part might be the definition of "every conceivable observable". Maybe the Haskell community has produced something like this?

Answer 1

Check out this blog post and this video. There, Bart de Smet proposes a minimal set of operations that can build every other operator there is. I guess, for performance reasons, one should probably not try to implement every operator there is by the basic operators but it's an interesting exercise to try for some.