Как объединить TaskT с экземпляром монады Trampoline, чтобы получить асинхронные вычисления без стека?

Dec 13 2020

Trampoline- это монада, которая добавляет стековую безопасность в стек трансформатора монад. Это достигается за счет использования специального интерпретатора ( monadRec), которому передается результат монадических вычислений (на самом деле это специализированная версия шаблона свободной монады). По этой причине Trampolineмонада должна быть самой внешней монадой, то есть базовой монадой стека трансформаторов.

В следующей настройке TaskT(которая, по сути, связана Contс совместным использованием) - преобразователь монады и Trampolineбазовая монада:

// TASK

const TaskT = taskt => record(
  TaskT,
  thisify(o => {
    o.taskt = k =>
      taskt(x => {
        o.taskt = k_ => k_(x);
        return k(x);
      });

    return o;
  }));

// Monad

const taskChainT = mmx => fmm =>
  TaskT(k =>
    mmx.taskt(x =>
      fmm(x).taskt(k)));

const taskOfT = x =>
  TaskT(k => k(x));

// Transformer

const taskLiftT = chain => mmx =>
  TaskT(k => chain(mmx) (k));

// auxiliary functions

const taskAndT = mmx => mmy =>
  taskChainT(mmx) (x =>
    taskChainT(mmy) (y =>
      taskOfT([x, y])));

const delayTaskT = f => ms => x =>
  TaskT(k => setTimeout(comp(k) (f), ms, x));

const record = (type, o) => (
  o[Symbol.toStringTag] = type.name || type, o);

const thisify = f => f({});

const log = (...ss) =>
  (console.log(...ss), ss[ss.length - 1]);

// TRAMPOLINE

const monadRec = o => {
  while (o.tag === "Chain")
    o = o.fm(o.chain);

  return o.tag === "Of"
    ? o.of
    : _throw(new TypeError("unknown trampoline tag"));
};

// tags

const Chain = chain => fm =>
  ({tag: "Chain", fm, chain});


const Of = of =>
  ({tag: "Of", of});

// Monad

const recOf = Of;

const recChain = mx => fm =>
  mx.tag === "Chain" ? Chain(mx.chain) (x => recChain(mx.fm(x)) (fm))
    : mx.tag === "Of" ? fm(mx.of)
    : _throw(new TypeError("unknown trampoline tag"));

// MAIN

const foo = x =>
  Chain(delayTaskT(x => x) (0) (x)) (Of);

const bar = taskAndT(
  taskLiftT(recChain) (foo(1)))
    (taskLiftT(recChain) (foo(2))); // yields TaskT

const main = bar.taskt(x => Of(log(x))); // yields Chain({fm, chain: TaskT})

monadRec(main); // yields [TaskT, TaskT] but [1, 2] desired

Это не то, что я хочу, потому что Trampolineоценка форсировок до того, как цикл событий получит результат асинхронных задач. Мне нужно наоборот, но, как я уже упоминал, TrampolineTтрансформатора нет . Что мне не хватает?

Ответы

2 AaditMShah Dec 14 2020 at 12:10

В этом фрагменте кода есть несколько проблем.

Проблема №1: нет преобразователя монад для IO(т.е. Task)

Как известно, преобразователя монад для IO. [1] Ваш TaskTтип смоделирован ContTи ContTдействительно является преобразователем монад. Однако вы используете TaskTдля выполнения асинхронных вычислений, например setTimeout, вот где возникает проблема.

Рассмотрим определение TaskT, которое похоже на ContT.

newtype TaskT r m a = TaskT { taskt :: (a -> m r) -> m r }

Следовательно, delayTaskTдолжен иметь тип (a -> b) -> Number -> a -> TaskT r m b.

const delayTaskT = f => ms => x =>
  TaskT(k => setTimeout(comp(k) (f), ms, x));

Однако setTimeout(comp(k) (f), ms, x)возвращает идентификатор тайм-аута, который не соответствует типу m r. Обратите внимание, что он k => setTimeout(comp(k) (f), ms, x)должен иметь тип (b -> m r) -> m r.

Фактически, невозможно вызвать значение типа, m rкогда продолжение kвызывается асинхронно. Преобразователь ContTмонад работает только для синхронных вычислений.

Тем не менее, мы можем определить его Taskкак специализированную версию Cont.

newtype Task a = Task { task :: (a -> ()) -> () } -- Task = Cont ()

Таким образом, всякий раз, когда Taskон присутствует в стеке преобразователя монад, он всегда будет в основании, как и IO.

Если вы хотите сделать Taskстек монад безопасным, прочтите следующий ответ .

Проблема № 2: fooфункция имеет неправильный тип возвращаемого значения

Предположим на мгновение, что delayTaskTэто правильный тип. Следующая проблема, как вы уже заметили, - это fooнеправильный тип возвращаемого значения.

Проблема, похоже, в том, fooчто возвращает a, TaskTзавернутый в, Chainи этот завернутый TaskTполностью отделен от TaskTцепочки и, таким образом, никогда не оценивается / не запускается.

Я предполагаю , что ожидаемый тип fooявляется a -> TaskT r Trampoline a. Однако на самом деле fooэто a -> Trampoline (TaskT r m a). К счастью, это легко исправить.

const foo = delayTaskT(x => x) (0);

Тип fooтакой же , как taskOfT, например a -> TaskT r m a. Мы можем специализироваться m = Trampoline.

Проблема № 3: вы taskLiftTнеправильно используете

taskLiftTФункция поднимает лежащее в основе монадического вычисления в TaskTслой.

taskLiftT :: (forall a b. m a -> (a -> m b) -> m b) -> m a -> TaskT r m a

taskLiftT(recChain) :: Trampoline a -> TaskT r Trampoline a

Теперь вы подаете заявку taskLiftT(recChain)на foo(1)и foo(2).

foo :: a -> Trampoline (TaskT r m a) -- incorrect definition of foo

foo(1) :: Trampoline (TaskT r m Number)
foo(2) :: Trampoline (TaskT r m Number)

taskLiftT(recChain) (foo(1)) :: TaskT r Trampoline (TaskT r m Number)
taskLiftT(recChain) (foo(2)) :: TaskT r Trampoline (TaskT r m Number)

Однако, если мы будем использовать правильное определение, fooтогда типы даже не будут совпадать.

foo :: a -> TaskT r Trampoline a -- correct definition of foo

foo(1) :: TaskT r Trampoline Number
foo(2) :: TaskT r Trampoline Number

-- Can't apply taskLiftT(recChain) to foo(1) or foo(2)

Если мы используем правильное определение, fooто есть два способа дать определение bar. Обратите внимание, что нет способа правильно определить foousing setTimeout. Следовательно, я переопределил fooкак taskOfT.

  1. Используйте fooи не используйте taskLiftT.

    const bar = taskAndT(foo(1))(foo(2)); // yields TaskT
    

    // TASK
    
    const TaskT = taskt => record(
      TaskT,
      thisify(o => {
        o.taskt = k =>
          taskt(x => {
            o.taskt = k_ => k_(x);
            return k(x);
          });
    
        return o;
      }));
    
    // Monad
    
    const taskChainT = mmx => fmm =>
      TaskT(k =>
        mmx.taskt(x =>
          fmm(x).taskt(k)));
    
    const taskOfT = x =>
      TaskT(k => k(x));
    
    // Transformer
    
    const taskLiftT = chain => mmx =>
      TaskT(k => chain(mmx) (k));
    
    // auxiliary functions
    
    const taskAndT = mmx => mmy =>
      taskChainT(mmx) (x =>
        taskChainT(mmy) (y =>
          taskOfT([x, y])));
    
    const delayTaskT = f => ms => x =>
      TaskT(k => setTimeout(comp(k) (f), ms, x));
    
    const record = (type, o) => (
      o[Symbol.toStringTag] = type.name || type, o);
    
    const thisify = f => f({});
    
    const log = (...ss) =>
      (console.log(...ss), ss[ss.length - 1]);
    
    // TRAMPOLINE
    
    const monadRec = o => {
      while (o.tag === "Chain")
        o = o.fm(o.chain);
    
      return o.tag === "Of"
        ? o.of
        : _throw(new TypeError("unknown trampoline tag"));
    };
    
    // tags
    
    const Chain = chain => fm =>
      ({tag: "Chain", fm, chain});
    
    
    const Of = of =>
      ({tag: "Of", of});
    
    // Monad
    
    const recOf = Of;
    
    const recChain = mx => fm =>
      mx.tag === "Chain" ? Chain(mx.chain) (x => recChain(mx.fm(x)) (fm))
        : mx.tag === "Of" ? fm(mx.of)
        : _throw(new TypeError("unknown trampoline tag"));
    
    // MAIN
    
    const foo = taskOfT;
    
    const bar = taskAndT(foo(1))(foo(2)); // yields TaskT
    
    const main = bar.taskt(x => Of(log(x))); // yields Chain({fm, chain: TaskT})
    
    monadRec(main); // yields [TaskT, TaskT] but [1, 2] desired

  2. Не используйте fooи не используйте taskLiftT.

    const bar = taskAndT(
      taskLiftT(recChain) (Of(1)))
        (taskLiftT(recChain) (Of(2))); // yields TaskT
    

    // TASK
    
    const TaskT = taskt => record(
      TaskT,
      thisify(o => {
        o.taskt = k =>
          taskt(x => {
            o.taskt = k_ => k_(x);
            return k(x);
          });
    
        return o;
      }));
    
    // Monad
    
    const taskChainT = mmx => fmm =>
      TaskT(k =>
        mmx.taskt(x =>
          fmm(x).taskt(k)));
    
    const taskOfT = x =>
      TaskT(k => k(x));
    
    // Transformer
    
    const taskLiftT = chain => mmx =>
      TaskT(k => chain(mmx) (k));
    
    // auxiliary functions
    
    const taskAndT = mmx => mmy =>
      taskChainT(mmx) (x =>
        taskChainT(mmy) (y =>
          taskOfT([x, y])));
    
    const delayTaskT = f => ms => x =>
      TaskT(k => setTimeout(comp(k) (f), ms, x));
    
    const record = (type, o) => (
      o[Symbol.toStringTag] = type.name || type, o);
    
    const thisify = f => f({});
    
    const log = (...ss) =>
      (console.log(...ss), ss[ss.length - 1]);
    
    // TRAMPOLINE
    
    const monadRec = o => {
      while (o.tag === "Chain")
        o = o.fm(o.chain);
    
      return o.tag === "Of"
        ? o.of
        : _throw(new TypeError("unknown trampoline tag"));
    };
    
    // tags
    
    const Chain = chain => fm =>
      ({tag: "Chain", fm, chain});
    
    
    const Of = of =>
      ({tag: "Of", of});
    
    // Monad
    
    const recOf = Of;
    
    const recChain = mx => fm =>
      mx.tag === "Chain" ? Chain(mx.chain) (x => recChain(mx.fm(x)) (fm))
        : mx.tag === "Of" ? fm(mx.of)
        : _throw(new TypeError("unknown trampoline tag"));
    
    // MAIN
    
    const foo = taskOfT;
    
    const bar = taskAndT(
      taskLiftT(recChain) (Of(1)))
        (taskLiftT(recChain) (Of(2))); // yields TaskT
    
    const main = bar.taskt(x => Of(log(x))); // yields Chain({fm, chain: TaskT})
    
    monadRec(main); // yields [TaskT, TaskT] but [1, 2] desired


[1] Почему в Haskell нет преобразователя ввода-вывода?