Como combinar o TaskT com a instância monad do Trampoline para obter cálculos assíncronos sem pilha?

Dec 13 2020

Trampolineé uma mônada e adiciona segurança de pilha a uma pilha de transformador de mônada. Ele consegue isso contando com um interpretador especial ( monadRec), que é alimentado com o resultado de uma computação monádica (na verdade, é uma versão especializada do padrão de mônada livre). Por esta razão, a Trampolinemônada deve ser a mônada mais externa, ou seja, a mônada base da pilha do transformador.

Na configuração a seguir TaskT(que é essencialmente Contcom compartilhamento) está o transformador de mônada e Trampolinea mônada de base:

// 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

Não é isso que eu quero, porque a Trampolineavaliação das forças antes do loop de eventos recebe o resultado das tarefas assíncronas. O que eu preciso é o contrário, mas como já mencionei, não há TrampolineTtransformador. o que estou perdendo?

Respostas

2 AaditMShah Dec 14 2020 at 12:10

Existem vários problemas neste trecho de código.

Problema nº 1: Não há transformador monad para IO(ou seja Task)

É sabido que não há transformador de mônada para IO. [1] Seu TaskTtipo é modelado após ContT, e ContTé de fato um transformador de mônada. No entanto, você está usando TaskTpara realizar cálculos assíncronos, como setTimeout, que é onde surge o problema.

Considere a definição de TaskT, que é semelhante a ContT.

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

Portanto, delayTaskTdeve ter o tipo (a -> b) -> Number -> a -> TaskT r m b.

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

No entanto, setTimeout(comp(k) (f), ms, x)retorna um id de tempo limite que não corresponde ao tipo m r. Observe que k => setTimeout(comp(k) (f), ms, x)deve ter o tipo (b -> m r) -> m r.

Na verdade, é impossível conjurar um valor do tipo m rquando a continuação ké chamada de forma assíncrona. O ContTtransformador monad só funciona para cálculos síncronos.

No entanto, podemos definir Taskcomo uma versão especializada de Cont.

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

Assim, sempre que Taskestiver presente em uma pilha de transformadores de mônadas, estará sempre na base, assim como IO.

Se você quiser tornar a Taskpilha de mônadas segura, leia a seguinte resposta .

Problema nº 2: a foofunção tem o tipo de retorno errado

Vamos supor por um momento que delayTaskTtenha o tipo correto. O próximo problema, como você já notou, é que footem o tipo de retorno errado.

O problema parece ser fooqual retorno a TaskTembrulhado em a Chaine este embrulhado TaskTestá completamente desacoplado da TaskTcadeia e, portanto, nunca é avaliado / disparado.

Estou assumindo que o tipo esperado de fooé a -> TaskT r Trampoline a. No entanto, o tipo real de fooé a -> Trampoline (TaskT r m a). Felizmente, a correção é fácil.

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

O tipo de fooé o mesmo que taskOfT, ou seja a -> TaskT r m a. Podemos nos especializar m = Trampoline.

Problema nº 3: você não está usando taskLiftTcorretamente

A taskLiftTfunção eleva uma computação monádica subjacente à TaskTcamada.

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

Agora, você está se inscrevendo taskLiftT(recChain)em foo(1)e 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)

No entanto, se usarmos a definição correta de foo, os tipos nem mesmo corresponderiam.

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)

Se estivermos usando a definição correta de, fooentão existem duas maneiras de definir bar. Observe que não há como definir corretamente o foousing setTimeout. Conseqüentemente, eu redefini foocomo taskOfT.

  1. Use fooe não use 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. Não use fooe use 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] Por que não há transformador IO em Haskell?