Is this a valid monad transformer in Javascript?

Question

In order to better understand monad transformers I implemented one. Since Javascript is dynamically typed I don't mimic type or data constructors but declare only plain old Javascript objects, which hold the corresponding static functions to form a specific monad / transformer. The underlying idea is to apply these methods to a value/values in a container type. Types and containers are separated so to speak.

Arrays can contain any number of elements. It is trivial to extend Arrays so that they implement the monad interface. Arrays can also represent the two variants of the maybe type. An empty Array corresponds to nothing. An Array with a single element corresponds to just(a). Consequently I will use Arrays as my container type. Please note that this is an quick and dirty implementation just for learning:

const array = {
  of: x => Array.of(x),
  map: f => ftor => ftor.map(f),
  ap: ftor => gtor => array.flatten(array.map(f => array.map(f) (gtor)) (ftor)),
  flatten: ftor => ftor.reduce((xs, y) => xs.concat(y), []),
  chain: mf => ftor => array.flatten(array.map(mf) (ftor))
}

const maybe = {
  of: array.of,
  empty: () => [],
  throw: ftor => { if (ftor.length > 1) throw Error("indeterministic value"); return ftor },
  map: f => ftor => maybe.throw(ftor).map(f),
  ap: ftor => gtor => maybe.flatten(maybe.map(f => maybe.map(f) (gtor)) (ftor)),
  flatten: array.flatten,
  chain: mf => ftor => maybe.flatten(maybe.map(mf) (ftor)),
  T: M => {
    return {
      of: x => M.of(maybe.of(x)),
      empty: () => M.of(maybe.empty()),
      map: f => ftor => M.map(gtor => maybe.map(f) (gtor)) (ftor),
      ap: ftor => gtor => M.flatten(M.map(htor => M.map(itor => maybe.ap(htor) (itor)) (gtor)) (ftor)),
      flatten: maybe.flatten,
      chain: mf => ftor => M.chain(gtor => maybe.chain(mf) (gtor)) (ftor)
    };
  }
};

Now I combine a maybe transformer with the monadic array to get a monad that can handle arrays of maybes.

const arraym = maybe.T(array);

const add = x => y => x + y;
const addm = x => y => [x + y];
const arrayOfMaybes = [[1],[],[3]]

When I treat arraym as an applicative functor, everything works as expected:

// yields: [[11],[],[13]] as expected
arraym.ap(arraym.map(add) (arrayOfMaybes)) (arraym.of(10));

However, when I apply chain something goes wrong:

// yields: [11,13] but [[11],[13]] expected
arraym.chain(x => arraym.chain(y => addm(x) (y)) (arrayOfMaybes)) ([[10]])

Is the cause of this problem

that this isn't a valid monad transformer?
that the way I apply chain is wrong?
that my expectation regarding the result is wrong?

I guess using a proper Maybe with a non-array representation would have exposed the type error you made by throwing instead of returning a mis-nested array — Bergi

Bergi Bergi · Accepted Answer · 2016-09-20T16:01:31

Is the cause of this problem that the way I apply chain is wrong?

Yes. You need to pass an mf that returns an arraym, not an array like addm does. You could use

const addmm = x => y => array.map(maybe.of)(addm(x)(y))
arraym.chain(x => arraym.chain( addmm(x) )(arrayOfMaybes))([[10]])

To help with this, you also might consider implementing lift for every monad transformer.

Is this a valid monad transformer in Javascript?

1 Answers