Thursday 22 October 2020

Is there a valid array monad transformer?

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?



from Is there a valid array monad transformer?

No comments:

Post a Comment