Saya memiliki fungsi pengangkatan variadik yang memungkinkan rantai monadik datar tanpa komposisi fungsi yang sangat bersarang:

const varArgs = f => {
  const go = args =>
    Object.defineProperties(
      arg => go(args.concat(arg)), {
        "runVarArgs": {get: function() {return f(args)}, enumerable: true},
        [TYPE]: {value: "VarArgs", enumerable: true}
      });

  return go([]);
};

const varLiftM = (chain, of) => f => { // TODO: replace recursion with a fold
  const go = (ms, g, i) =>
    i === ms.length
      ? of(g)
      : chain(ms[i]) (x => go(ms, g(x), i + 1));

  return varArgs(ms => go(ms, f, 0));
};

Ini berfungsi tetapi saya ingin abstrak dari rekursi dengan lipatan. Lipatan normal tampaknya tidak berfungsi, setidaknya tidak sesuai dengan tipe Task,

const varLiftM = (chain, of) => f =>
  varArgs(ms => of(arrFold(g => mx => chain(mx) (g)) (f) (ms))); // A

Karena aljabar pada baris A akan mengembalikan Task untuk setiap iterasi, bukan fungsi yang diterapkan sebagian.

Bagaimana saya bisa mengganti rekursi non-ekor dengan lipatan?

Berikut adalah contoh kerja dari implementasi rekursif saat ini:

const TYPE = Symbol.toStringTag;

const struct = type => cons => {
  const f = x => ({
    ["run" + type]: x,
    [TYPE]: type,
  });

  return cons(f);
};

// variadic argument transformer

const varArgs = f => {
  const go = args =>
    Object.defineProperties(
      arg => go(args.concat(arg)), {
        "runVarArgs": {get: function() {return f(args)}, enumerable: true},
        [TYPE]: {value: "VarArgs", enumerable: true}
      });

  return go([]);
};

// variadic monadic lifting function

const varLiftM = (chain, of) => f => { // TODO: replace recursion with a fold
  const go = (ms, g, i) =>
    i === ms.length
      ? of(g)
      : chain(ms[i]) (x => go(ms, g(x), i + 1));

  return varArgs(ms => go(ms, f, 0));
};

// asynchronous Task

const Task = struct("Task") (Task => k => Task((res, rej) => k(res, rej)));

const tOf = x => Task((res, rej) => res(x));

const tMap = f => tx =>
  Task((res, rej) => tx.runTask(x => res(f(x)), rej));

const tChain = mx => fm =>
  Task((res, rej) => mx.runTask(x => fm(x).runTask(res, rej), rej));

// mock function

const delay = (ms, x) =>
  Task(r => setTimeout(r, ms, x));

// test data

const tw = delay(100, 1),
  tx = delay(200, 2),
  ty = delay(300, 3),
  tz = delay(400, 4);

// specialization through partial application

const varAsyncSum =
  varLiftM(tChain, tOf) (w => x => y => z => w + x + y + z);

// MAIN

varAsyncSum(tw) (tx) (ty) (tz)
  .runVarArgs
  .runTask(console.log, console.error);

console.log("1 sec later...");

[EDIT] Seperti yang diinginkan dalam komentar, implementasi lipatan saya:

const arrFold = alg => zero => xs => {
  let acc = zero;

  for (let i = 0; i < xs.length; i++)
    acc = alg(acc) (xs[i], i);

  return acc;
};
3
Iven Marquardt 2 Juni 2019, 20:22

2 jawaban

Jawaban Terbaik

Panggilan of di sekitar arrFold tampaknya agak tidak pada tempatnya.

Saya tidak yakin apakah arrFold Anda adalah lipatan kanan atau lipatan kiri, tetapi dengan asumsi itu adalah lipatan kanan, Anda perlu menggunakan gaya passing lanjutan dengan penutupan seperti yang Anda lakukan dalam implementasi rekursif Anda:

varArgs(ms => of(arrFold(g => mx => chain(mx) (g)) (f) (ms)))

Menjadi

varArgs(ms => arrFold(go => mx => g => chain(mx) (x => go(g(x)))) (of) (ms) (f))

Dengan lipatan kiri, Anda bisa menulis

varArgs(arrFold(mg => mx => chain(g => map(g) (mx)) (mg)) (of(f)))

Tetapi Anda perlu memperhatikan bahwa ini membangun pohon panggilan yang berbeda dari lipatan kanan:

of(f)
chain(of(f))(g0 => map(m0)(g0))
chain(chain(of(f))(g0 => map(m0)(g0)))(g1 => map(m1)(g1))
chain(chain(chain(of(f))(g0 => map(m0)(g0)))(g1 => map(m1)(g1)))(g2 => map(m2)(g2))

Vs (dengan kelanjutan yang sudah diterapkan)

of(f)
chain(m0)(x0 => of(f(x0)))
chain(m0)(x0 => chain(m1)(x1 => of(f(x0)(x1))))
chain(m0)(x0 => chain(m1)(x1 => chain(m2)(x2) => of(f(x0)(x1)(x2)))))

Menurut undang-undang monad, mereka harus mengevaluasi hal yang sama, tetapi dalam praktiknya yang satu mungkin lebih efisien daripada yang lain.

1
scriptum 7 Juni 2019, 16:31

Anda tidak memerlukan kekuatan penuh monad untuk kasus penggunaan khusus ini. Anda hanya perlu functor aplikatif:

// type Cont r a = (a -> r) -> r

// type Async a = Cont (IO ()) a

// pure :: a -> Async a
const pure = a => k => k(a);

// ap :: Async (a -> b) -> Async a -> Async b
const ap = asyncF => asyncA => k => asyncF(f => asyncA(a => k(f(a))));

// delay :: (Number, a) -> Async a
const delay = (ms, a) => k => setTimeout(k, ms, a);

// async1, async2, async3, async4 :: Async Number
const async1 = delay(100, 1);
const async2 = delay(200, 2);
const async3 = delay(300, 3);
const async4 = delay(400, 4);

// sum :: Number -> Number -> Number -> Number -> Number
const sum = a => b => c => d => a + b + c + d;

// uncurry :: (a -> b -> c) -> (a, b) -> c
const uncurry = f => (a, b) => f(a)(b);

// result :: Async Number
const result = [async1, async2, async3, async4].reduce(uncurry(ap), pure(sum));

// main :: IO ()
result(console.log);
console.log("1 second later...");

Jika mau, Anda dapat mendefinisikan fungsi konteks aplikatif (yaitu apply) sebagai berikut:

const apply = (asyncF, ...asyncArgs) => asyncArgs.reduce(uncurry(ap), asyncF);

const result = apply(pure(sum), async1, async2, async3, async4);

Jika Anda menggunakan fungsi ini maka Anda dapat membuat fungsi lift:

const apply = asyncF => (...asyncArgs) => asyncArgs.reduce(uncurry(ap), asyncF);

const lift = f => apply(pure(f));

const asyncSum = lift(sum);

const result = asyncSum(async1, async2, async3, async4);

Perhatikan bahwa reduce sama dengan arrFold. Oleh karena itu, lift setara dengan varLiftM.

1
Aadit M Shah 3 Juni 2019, 11:49