Is there a valid array monad transformer?

Question

I know how to implement the single linked list monad transformer but couldn't get its array counterpart running. The problem is that there is a grouping effect which renders the transformer only valid for commutative base monads. Here is an example where for the sake of simplicity both the transformer and the base monad are arrays and there is no transformer type wrapper:

// ARRAY

const arrMap = f => xs =>
  xs.map((x, i) => f(x, i));

const arrAp = tf => xs =>
  arrFold(acc => f =>
    arrAppend(acc)
      (arrMap(x => f(x)) (xs)))
        ([])
          (tf);

const arrOf = x => [x];

const arrChain = mx => fm =>
  arrFold(acc => x =>
    arrAppend(acc) (fm(x))) ([]) (mx);

// Transformer

const arrChainT = ({map, ap, of ,chain}) => mmx => fmm =>
  chain(mmx) (mx => {
    const go = ([x, ...xs]) =>
      x === undefined
        ? of([])
        : ap(map(arrCons) (fmm(x))) (go(xs));

    return chain(go(mx)) (ys => of(arrFold(arrAppend) ([]) (ys)));
  });

const arrOfT = of => x => of([x]);

// Transformer stack

const arrArrChain = arrChainT(
  {map: arrMap, ap: arrAp, of: arrOf, chain: arrChain});

const arrArrOf = arrOfT(arrOf);

// auxiliary functions

const arrFold = f => init => xs => {
  let acc = init;
  
  for (let i = 0; i < xs.length; i++)
    acc = f(acc) (xs[i], i);

  return acc;
};

const arrAppend = xs => ys =>
  xs.concat(ys);

const arrCons = x => xs =>
  [x].concat(xs);

// MAIN

foo = x =>
  x === 0
    ? [[0, 1]]
    : [[0], [1]];

console.log(JSON.stringify(
  arrArrChain(arrArrChain(foo(0)) (foo)) (foo)));
    // yields [[0,1,0,0,1],[0,1,1,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1]]

console.log(JSON.stringify(
  arrArrChain(foo(0)) (x => arrArrChain(foo(x)) (foo))));
    // yields [[0,1,0,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0,1],[0,1,1,0],[0,1,1,1]]

Both computations should yield the same result. Now my question is: Is there a way to implement the array transformer in a lawful way?

The monad transformer instance of arrays would be the same as that of lists since they are isomorphic. Note that a naive implementation of a list monad transformer instance also does not yield a monad unless the argument monad is commutative. — Aadit M Shah
@AaditMShah I made Listt-done-right strict and it still works. I don't like to admit it, but you're right after all. — Iven Marquardt

Aadit M Shah Aadit M Shah · Accepted Answer · 2020-10-22T10:56:49

The array monad transformer is the same as the list monad transformer.

// Step m a = null | { head : a, tail : ListT m a }
// ListT m a = m (Step m a)

// nil : Monad m -> ListT m a
const nil = M => M.pure(null);

// cons : Monad m -> a -> ListT m a -> ListT m a
const cons = M => head => tail => M.pure({ head, tail });

// foldr : Monad m -> (a -> m b -> m b) -> m b -> ListT m a -> m b
const foldr = M => f => a => m => M.bind(m)(step =>
    step ? f(step.head)(foldr(M)(f)(a)(step.tail)) : a);

// append : Monad m -> ListT m a -> ListT m a -> ListT m a
const append = M => m1 => m2 => foldr(M)(cons(M))(m2)(m1);

// pure : Monad m -> a -> ListT m a
const pure = M => x => cons(M)(x)(nil(M));

// bind : Monad m -> ListT m a -> (a -> ListT m b) -> ListT m b
const bind = M => m => f => foldr(M)(x => append(M)(f(x)))(nil(M))(m);

// MonadListT : Monad m -> Monad (ListT m)
const MonadListT = M => ({ pure: pure(M), bind: bind(M) });

// MonadArray : Monad Array
const MonadArray = { pure: x => [x], bind: a => f => a.flatMap(f) };

// MonadListArray : Monad (ListT Array)
const MonadListArray = MonadListT(MonadArray);

// fromArray : Monad m -> Array a -> ListT m a
const fromArray = M => a => a.reduceRight((xs, x) => cons(M)(x)(xs), nil(M));

// lift : Monad m -> m a -> ListT m a
const lift = M => m => M.bind(m)(pure(M));

// foo : Nat -> ListT Array Nat
const foo = x => x === 0
    ? fromArray(MonadArray)([0, 1])
    : lift(MonadArray)([0, 1]);

// associativityLHS : Monad m -> m a -> (a -> m b) -> (b -> m c) -> m c
const associativityLHS = M => m => k => h => M.bind(M.bind(m)(k))(h);

// associativityRHS : Monad m -> m a -> (a -> m b) -> (b -> m c) -> m c
const associativityRHS = M => m => k => h => M.bind(m)(x => M.bind(k(x))(h));

// lhs :: ListT Array Nat
const lhs = associativityLHS(MonadListArray)(foo(0))(foo)(foo);

// rhs :: ListT Array Nat
const rhs = associativityRHS(MonadListArray)(foo(0))(foo)(foo);

console.log(JSON.stringify(lhs) === JSON.stringify(rhs));
console.log(JSON.stringify(lhs));

Note that each step of the list is wrapped in the argument monad. This allows other monadic actions to be interleaved and it's necessary to preserve the monad laws if the argument monad is not commutative.

Is there a valid array monad transformer?

1 Answers