Wrote javascript version of error monad / monadplus, did I obey monad laws correctly?

Question

Just looking for some critiques hopefully from haskellers of how I might be breaking monad laws or just monadding all wrong. My or is something like the mplus for either and usable as a catch for failures from then which behaves mostly like the error monad.

I'm barely a haskeller so this was a big stretch for me, but I think it came out pretty well. Basic goal was some combinators you could create state machines compositionally with like how parser combinators are used to create state machines.

I wonder if my or might be more like the applicative <|> and if it could be improved to be less repeating.. does my structure anywhere cause repetition dangers where an entire chain gets executed twice because of one of the pieces composed into it?

(function() {
    this.m_ = {};

    /* canContinue: error monad gate, and general monad validator */
    this.m_.canContinue = function(m) { return m !== undefined && m.m !== undefined && m.m === Success && m.a !== undefined; };

    /* functor instance */
    this.m_.map = function(m, f) { return m.m === Failure ? new m.m.f(m.a) : new m.m.f(f(m.a)); };

    /* applicative instance; ret = return = pure */
    this.m_.ret = function(a) { return new success(a); };
    this.m_.ap = function(mf, ma) {
        return
             mf.m === Failure ? new mf.m.f(mf.a) :
            (ma.m === Failure ? new ma.m.f(ma.a) :
                                new success(mf.a(ma.a)));
    };

    /* alternative instance */
    this.m_.alternative = function(f1, f2) {
        return function(a) {
            var resultf1 = f1(a);
            if (resultf1.m === Success) return resultf1;
            return f2(a);
        };
    };

    /* monad instance */
    this.m_.bind = function(f, m) { return m_.canContinue(m) ? f(m.a) : m; };
    this.m_.kleisli = function(f1, f2) { return function(a) { return m_.bind(f2, f1(a)) }; };

    /* error monad's monadic actions, and some english verbiage aliases */
    this.m_.until = function(f, p) {
        return function(a) {
            var result = f(a);
            var goodResult = result;
            while(m_.bind(p, result).m === Failure) {
                if (result.m === Failure) return goodResult;
                else goodResult = result;
                result = m_.bind(f, result);
            }
            return result;
        };
    };
    this.m_.run = function(f, a) { return m_.bind(f, m_.ret(a)); };

    this.m_.or = this.m_.alternative;
    this.m_.then = this.m_.kleisli;


   (function() {
       this.or = function(f2) { return m_.or(this, f2); };
       this.then = function(f2) { return m_.then(this, f2); };
       this.until = function(p) { return m_.until(this, p); };
   }).call(Function.prototype);

    var either = function(m, a) { this.m = m; this.a = a; };

    var Success = {}
    var Failure = {}

    Success.f = this.success = function(a) { return new either(Success, a); };
    Failure.f = this.failure = function(a) { return new either(Failure, a); };

}).call(this);

///////////////////////////////////////////////////////////////
///////// TEST GARBAGE FOR PONDERING USES BELOW ///////////////


var assertEqual = function(a, b, msg) {
    return function(x) { return a === b ? new success(b) : new failure(msg); };
};

var validateCar = function(x) {
    return m_.run(
              assertEqual(x.color, "red", "wrong color")
        .then(assertEqual(x.gas, 20, "wrong gas"))
        .then(assertEqual(x.mph, 30, "wrong mph")), 0);
};

m_.run(validateCar, { gas: 20, mph: 30, color: "red" });

var inc = function(a) { return a > -1 ? new success(a+1) : new failure("need positive number"); };
var dec = function(a) { return a < 0 ? new success(a-1) : new failure("need negative number"); };
var stop = function(limit, isDec) { return function(a) {
    return isDec ?
        (a > limit ? new failure("go") : new success("stop")) :
        (a < limit ? new failure("go") : new success("stop")); };
};

var bla = new failure("ah fail");
var test = function(a) {
     return typeof a == "string" ? new success(a) : new failure(a);
};

var incOrDecTwice = m_.or(inc, dec).then(m_.or(inc, dec));

m_.run(incOrDecTwice.until(stop(22, true)), 2);
m_.run(incOrDecTwice.then(dec), 4);

m_.run(m_.or(inc, dec), 1);
m_.run(m_.or(inc, dec).until(m_.or(stop(22, false), stop(-22, true))), 1);
m_.run(m_.or(inc, dec).until(m_.or(stop(22, false), stop(-22, true))), -1);

Any thoughts on whether to put or onto Function.prototype like then is? I feel it's scoping is a touch confused there to a reader.. but at the same time it creates a nice symmetry, so I'm on the fence about it...

Answer 1

liftM2 f m1 m2      = do { x1 <- m1; x2 <- m2; return (f x1 x2) }
ap                =  liftM2 id

ap is already defined in Control.Monad library, against the Monad interface.

What if you decide to also implement the Maybe and Identity and List. Will you implement the ap again for each of them?

• My main point is that the use of making an interface explicit is it will enable you to program against it. It will enable some part of your programs DRY that would otherwise would not be.

• Another benefit would be enabling you to use preexisting algorithms, Monad libraries in this case or STL algorithm library is another example.

• Yet another benefit is that even if you cannot DRY up some routine at least your code readers will be able to identify the Idioms and patterns you are using.

UPDATE:I give an example in JS below. I would give Maybe and your Error monads and the ap function, without currying and infix operators they don't read well at all. So I give kleisli which proved to be easier to read and write.

As for the question of obeying monad laws.

Monadic laws are as follows from Haskell wiki. Left identity:

return a >>= f eqv. f a

converted to JS:

bind(f, ret(a)) eqv. f(a)

Right identity:

m >>= return eqv. m

converted to JS:

bind(ret, m) eqv. m

Associativity:

(m >>= f) >>= g eqv. m >>= (\x -> f x >>= g)

converted to JS:

bind(g, bind(f, m)) eqv. bind(function(x){ return bind(g, f(x)); }, m)

How do one check that an implementation obeys these laws? If your implementation is side effect free, as it should be, you can trace the statements using substitution model

Associativity Law (for case Success)

bind(g, bind(f, m)) where m is {m:Success, a:X} // start with LHS
bind(g, bind(f, {m:Success, a:X}))
bind(g, (m_.canContinue(m) ? f(m.a) : m))
bind(g, (true ? f(m.a) : m))
bind(g, f(m.a))
bind(g, f(X)) //(I)

bind(function(x){ return bind(g, f(x)); }, m) where m is {m:Success, a:X} // start with RHS
bind(function(x){ return bind(g, f(x)); }, m)
(m_.canContinue(m) ? f(m.a) : m) where f is function(x){ return bind(g, f(x)); } and m is {m:Success, a:X}
(true ? f(m.a) : m) where f is same as above and m is same as above
f(m.a) where f is same as above and m is same as above
f(X) where f is function(x){ return bind(g, f(x)); } (same as above) and m is same as above
bind(g, f(X)) //(II)

Associativity Law (for case Failure)

bind(g, bind(f, m)) where m is {m:Failure, a:X} // start with LHS
// binding failure to anything returns itself no need to write down all the steps
m where m is {m:Failure, a:X} // (I)


bind(function(x){ return bind(g, f(x)); }, m) where m is {m:Failure, a:X} // start with RHS
// binding failure to anything returns itself no need to write down all the steps
m where m is {m:Failure, a:X} // (II)

It is verbose. I was a little lax with the notation. (But this is not the exam, right?)

Identities follow similarly for cases m is {m:Success, a:X} and m is {m:Failure, a:X}

Separation of concerns in canContinue

One of the things I want to add here is that canContinue is trying to do two things at once. This has two consequences. First, it affects readability adversely. Its core algorithmic/logical bit m.m == Success is being lost to the reader in the validation code. Also at its only use site, name bind function, it is not evident immediately that you are doing a case analysis on type tag. (cond/pattern match on type) Second you are doing that validation many times unnecessarily on values produced by success(a) constructor.

Type tag .m

Haskell data structures are tagged records alright. But it pattern matches on the constructor name. JS has a constructor property as a type tag and an instanceof operator.

m instanceof Success is more readable to me than m.m === Success. It also excludes structures that happens to have a .m member but not constructed with the Success constructor. m.constructor === Success may be another option. This is a stylistic opinion and I am not a JS developer.

Implementing the Monad interface in JS.

var Just = function(value) {
   this.value = value;
}
var Nothing = function(){};

var just = function(a) {return new Just(a)}
var nothing = new Nothing();

var Monad = function(impl) {
    this.bind = impl.bind
    this.ret = impl.ret

    //each instance gets this for free
    this.fail = function(s) { throw s;}

    var ret = this.ret.bind(this);
    var bind = this.bind.bind(this);

    //each instance gets this for free
    this.liftM2 = function(f) {
      return function(m1, m2) {
        return bind(
          m1, 
          function (x1) { 
            return bind(
              m2,  
              function(x2) { 
                return ret(f(x1,x2));})})};
    };
};

Maybe Monad instance in haskell

     return :: a -> Maybe a
     return x  = Just x


     (>>=)  :: Maybe a -> (a -> Maybe b) -> Maybe b
     (>>=) m g = case m of
                    Nothing -> Nothing
                    Just x  -> g x

Compare the pattern matching with above haskell impl

var maybeMonad = new Monad({
   bind: function(m, f) {
     if (m instanceof Nothing) return nothing;
     if (m instanceof Just) return f(m.value);
     // may want to raise error here?
   },
   ret: function(a) {return just(a)}
   });

// We can add library functions after the fact
// other monad instances should also see this automatically
// NOTE: I switched the order of the parameters of bind
Monad.prototype.kleisli = function(f1, f2) { return function(a) { return this.bind(f1(a), f2) }.bind(this); };

// some tests, just for demo purposes
// === doesn't work on Just we compare the values instead
var myAdd = function (a, b) { return a + b;}

var tryDivide = function(a, b) { if (b !== 0) return just(a/b); else return nothing;}

(function(_) {
  console.log(_.liftM2(myAdd)(_.ret(10), tryDivide(10, 2)))

  // a test case for monad identity law in kleisli form
  console.assert(_.kleisli(_.ret, _.ret)(10).value === _.ret(10).value)

  // a test case for monad associativity law in kleisli form
  console.assert(_.kleisli(_.ret, _.kleisli(_.ret, _.ret))(10).value  
             === _.kleisli(_.kleisli(_.ret, _.ret), _.ret)(10).value)

})(maybeMonad)