¿Cómo combinar TaskT con la instancia de mónada de Trampoline para obtener cálculos asíncronos sin pila?

Dec 13 2020

Trampolinees una mónada y agrega seguridad de pila a una pila de transformador de mónada. Lo logra confiando en un intérprete especial ( monadRec), que se alimenta con el resultado de un cálculo monádico (en realidad es una versión especializada del patrón de mónada libre). Por esta razón, la Trampolinemónada debe ser la mónada más externa, que es la mónada base de la pila de transformadores.

En la siguiente configuración TaskT(que es esencialmente Contcon compartir) está el transformador de mónada y Trampolinela mónada 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

Esto no es lo que quiero, porque la Trampolineevaluación de fuerzas antes del ciclo de eventos recibe el resultado de las tareas asincrónicas. Lo que necesito es al revés, pero como ya he mencionado, no hay TrampolineTtransformador. ¿Qué me estoy perdiendo?

Respuestas

2 AaditMShah Dec 14 2020 at 12:10

Hay varios problemas en este fragmento de código.

Problema n. ° 1: no hay transformador de mónada para IO(es decir Task)

Es bien sabido que no existe un transformador de mónada para IO. [1] Su TaskTtipo se basa en el modelo ContTy, de ContThecho , es un transformador de mónada. Sin embargo, lo está utilizando TaskTpara realizar cálculos asincrónicos como setTimeout, que es donde surge el problema.

Considere la definición de TaskT, que es similar a ContT.

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

Por lo tanto, delayTaskTdebería tener el tipo (a -> b) -> Number -> a -> TaskT r m b.

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

Sin embargo, setTimeout(comp(k) (f), ms, x)devuelve un ID de tiempo de espera que no coincide con el tipo m r. Tenga en cuenta que k => setTimeout(comp(k) (f), ms, x)debería tener el tipo (b -> m r) -> m r.

De hecho, es imposible conjurar un valor de tipo m rcuando la continuación kse llama asincrónicamente. El ContTtransformador de mónada solo funciona para cálculos sincrónicos.

Sin embargo, podemos definirlo Taskcomo una versión especializada de Cont.

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

Por lo tanto, siempre que Taskesté presente en una pila de transformadores de mónada, siempre estará en la base, al igual que IO.

Si desea que la Taskpila de mónadas sea segura, lea la siguiente respuesta .

Problema n. ° 2: la foofunción tiene el tipo de retorno incorrecto

Supongamos por un momento que delayTaskTtiene el tipo correcto. El siguiente problema, como ya ha notado, es que footiene el tipo de devolución incorrecto.

El problema parece ser foocuál devuelve un TaskTenvuelto en a Chainy este envuelto TaskTestá completamente desacoplado de la TaskTcadena y, por lo tanto, nunca se evalúa / dispara.

Supongo que el tipo esperado de fooes a -> TaskT r Trampoline a. Sin embargo, el tipo real de fooes a -> Trampoline (TaskT r m a). Afortunadamente, la solución es fácil.

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

El tipo de fooes el mismo que taskOfT, es decir a -> TaskT r m a. Podemos especializarnos m = Trampoline.

Problema n. ° 3: no está usando taskLiftTcorrectamente

La taskLiftTfunción eleva un cálculo monádico subyacente a la TaskTcapa.

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

Ahora, va a aplicar taskLiftT(recChain)a foo(1)y 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)

Sin embargo, si usamos la definición correcta de fooentonces los tipos ni siquiera coincidirían.

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)

Si usamos la definición correcta de fooentonces hay dos formas de definir bar. Tenga en cuenta que no hay forma de definir correctamente foousing setTimeout. Por lo tanto, he redefinido foocomo taskOfT.

  1. Use fooy no 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. No use fooni 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 qué no hay un transformador IO en Haskell?