How does the Free monad and Reactive Extensions correlate?

Question

I come from a C# background, where LINQ evolved into Rx.NET, but always had some interest in FP. After some introduction to monads and some side-projects in F#, I was ready to try and step to the next level.

Now, after several talks on the free monad from people from Scala, and multiple writeups in Haskell, or F#, I have found grammars with interpreters on for comprehension to be quite similar to IObservable chains.

In FRP you compose an operation definition from smaller domain specific chunks including side-effects and failures that stay inside the chain, and model your application as a set of operations and side effects. In free monad, if I understood correctly, you do the same by making your operations as functors, and lifting them using coyoneda.

What would be the differences between both that tilt the needle towards any of the approaches? What is the fundamental difference when defining your service or program?

Answer 1

Monads

A monad consists of

• An endofunctor. In our software engineering world, we can say this corresponds to a datatype with a single, unrestricted type parameter. In C#, this would be something of the form:

  class M<T> { ... }
  

• Two operations defined over that datatype:

  • return / pure takes a "pure" value (i.e., a T value) and "wraps" it into the monad (i.e., it produces an M<T> value). Since return is a reserved keyword in C#, I'll use pure to refer to this operation from now on. In C#, pure would be a method with a signature like:

    M<T> pure(T v);
    

  • bind / flatmap takes a monadic value (M<A>) and a function f. f takes a pure value and returns a monadic value (M<B>). From these, bind produces a new monadic value (M<B>). bind has the following C# signature:

    M<B> bind(M<A> mv, Func<A, M<B>> f);
    

Also, to be a monad, pure and bind are required to obey the three monad laws.

Now, one way to model monads in C# would be to construct an interface:

interface Monad<M> {
  M<T> pure(T v);
  M<B> bind(M<A> mv, Func<A, M<B>> f);
}

(Note: In order to keep things brief and expressive, I'll be taking some liberties with the code throughout this answer.)

Now we can implement monads for concrete datagypes by implementing concrete implementations of Monad<M>. For instance, we might implement the following monad for IEnumerable:

class IEnumerableM implements Monad<IEnumerable> {
  IEnumerable<T> pure(T v) {
    return (new List<T>(){v}).AsReadOnly();
  }

  IEnumerable<B> bind(IEnumerable<A> mv, Func<A, IEnumerable<B>> f) {
    ;; equivalent to mv.SelectMany(f)
    return (from a in mv
            from b in f(a)
            select b);
  }
}

(I'm purposefully using the LINQ syntax to call out the relationship between LINQ syntax and monads. But note we could replace the LINQ query with a call to SelectMany.)

Now, can we define a monad for IObservable? It would seem so:

class IObservableM implements Monad<IObservable> {
  IObservable<T> pure(T v){
    Observable.Return(v);
  }

  IObservable<B> bind(IObservable<A> mv, Func<A, IObservable<B>> f){
    mv.SelectMany(f);
  }
}

To be sure we have a monad, we need to prove the monad laws. This can be non-trivial (and I'm not familiar enough with Rx.NET to know whether they can even be proved from the specification alone), but it's a promising start. To facilitate the remainder of this discussion, let's just assume the monad laws hold in this case.

Free Monads

There is no singular "free monad". Rather, free monads are a class of monads that are constructed from functors. That is, given a functor F, we can automatically derive a monad for F (i.e., the free monad of F).

Functors

Like monads, functors can be defined by the following three items:

• A datatype, parameterized over a single, unrestricted type variable.

• Two operations:

  • pure wraps a pure value into the functor. This is analogous to pure for a monad. In fact, for functors that are also a monads, the two should be identical.

  • fmap maps values in the input to new values in the output via a given function. It's signature is:

    F<B> fmap(Func<A, B> f, F<A> fv)
    

Like monads, functors are required to obey the functor laws.

Similar to monads, we can model functors via the following interface:

interface Functor<F> {
  F<T> pure(T v);
  F<B> fmap(Func<A, B> f, F<A> fv);
}

Now, since monads are a sub-class of functors, we could also refactor Monad a bit:

interface Monad<M> extends Functor<M> {
  M<T> join(M<M<T>> mmv) {
    Func<T, T> identity = (x => x);
    return mmv.bind(x => x); // identity function
  }

  M<B> bind(M<A> mv, Func<A, M<B>> f) {
    join(fmap(f, mv));
  }
}

Here I've added an additional method, join, and provided default implementations of both join and bind. Note, however, that these are circular definitions. So you'd have to override at least one or the other. Also, note that pure is now inherited from Functor.

IObservable and Free Monads

Now, since we have defined a monad for IObservable and since monads are a sub-class of functors, it follows that we must be able to define a functor instance for IObservable. Here's one definition:

class IObservableF implements Functor<IObservable> {
  IObservable<T> pure(T v) {
    return Observable.Return(v);
  }

  IObservable<B> fmap(Func<A, B> f, IObservable<A> fv){
    return fv.Select(f);
  }
}

Now that we have a functor defined for IObservable, we can construct a free monad from that functor. And that is precisely how IObservable relates to free monads — namely, that we can construct a free monad from IObservable.