14

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?

  • 2
    Here's an interesting way to think about the problem... FRP can be viewed as a monad, even if it isn't usually formulated that way. Most (although not all) monads are isomorphic to the free monad. As Cont is the only monad I have seen suggested that cannot be expressed via the free monad, one can probably assume that FRP can be. As can almost anything else. – Jules Jun 6 '16 at 22:26
  • 2
    According to Erik Meijer, the designer of both LINQ and Rx.NET, IObservable is an instance of the continuation monad. – Jörg W Mittag Jun 7 '16 at 7:08
  • 1
    I don't have the time to work out the details right now, but my guess is that both RX extensions and the free monad approach accomplish very similar goals but might have slightly different structures. It's possible that RX Observables are monads themselves and then you can map a free monad computation to one using observables—that's very roughly what the "free" in "free monad" means. Or maybe the relationship isn't that direct and you're just picking up on how they are used for similar purposes. – Tikhon Jelvis Jul 29 '16 at 19:08
6
+50

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.

  • Insightful understanding of category theory! I was after something that talked not about how they are created, more about the differences when building a functional architecture and modeling effect composition with either of them. FreeMonad can be used to build DSLs for reified operations, whereas IObservables are more about discrete values over time. – MLProgrammer-CiM Sep 8 '17 at 11:15
  • 1
    @MLProgrammer-CiM, I'll see if I can add some insights on that in the next couple days. – Nathan Davis Sep 8 '17 at 15:59
  • I'd love a practical example of free monads – l--''''''---------'''''''''''' Aug 22 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.