Bagaimana cara menggabungkan TaskT dengan monad instance Trampoline untuk mendapatkan komputasi asinkron tanpa tumpukan?

Dec 13 2020

Trampolineadalah monad dan menambahkan keamanan tumpukan ke tumpukan transformator monad. Ini mencapai ini dengan mengandalkan interpreter khusus ( monadRec), yang diberi makan dengan hasil komputasi monad (sebenarnya itu adalah versi khusus dari pola monad gratis). Untuk itu Trampolinemonad harus merupakan monad terluar, yaitu monad dasar dari stack transformator.

Dalam pengaturan berikut TaskT(yang pada dasarnya Contdengan berbagi) adalah trafo monad dan Trampolinemonad basis:

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

Ini bukan yang saya inginkan, karena Trampolineevaluasi kekuatan sebelum loop acara menerima hasil dari tugas-tugas asinkron. Yang saya butuhkan adalah sebaliknya, tetapi seperti yang telah saya sebutkan, tidak ada TrampolineTtrafo. Apa yang saya lewatkan?

Jawaban

2 AaditMShah Dec 14 2020 at 12:10

Ada beberapa masalah dalam cuplikan kode ini.

Masalah # 1: Tidak ada trafo monad untuk IO(mis. Task)

Diketahui bahwa tidak ada trafo monad untuk IO. [1]TaskT Tipe Anda dimodelkan ContT, dan ContTmemang merupakan transformator monad. Namun, Anda menggunakan TaskTuntuk melakukan komputasi asinkron seperti setTimeout, di situlah masalah muncul.

Pertimbangkan definisi dari TaskT, yang mirip dengan ContT.

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

Makanya, delayTaskTharus punya tipenya (a -> b) -> Number -> a -> TaskT r m b.

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

Namun, setTimeout(comp(k) (f), ms, x)mengembalikan id batas waktu yang tidak cocok dengan tipenya m r. Perhatikan bahwa k => setTimeout(comp(k) (f), ms, x)harus memiliki tipe (b -> m r) -> m r.

Faktanya, tidak mungkin untuk menyulap nilai tipe m rsaat kelanjutan kdisebut secara asinkron. The ContTmonad transformator hanya bekerja untuk perhitungan sinkron.

Namun demikian, kami dapat mendefinisikan Tasksebagai versi khusus dari Cont.

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

Jadi, setiap kali Taskada dalam tumpukan trafo monad, ia akan selalu berada di pangkalan, sama seperti IO.

Jika Anda ingin membuat Tasktumpukan monad aman maka baca jawaban berikut .

Masalah # 2: fooFungsi ini memiliki tipe pengembalian yang salah

Mari kita asumsikan sejenak bahwa delayTaskTmemiliki tipe yang benar. Masalah berikutnya, seperti yang telah Anda perhatikan adalah foojenis pengembalian yang salah.

Masalahnya adalah fooyang mengembalikan yang TaskTdibungkus dalam a Chaindan pembungkus TaskTini benar-benar dipisahkan dari TaskTrantai dan karenanya tidak pernah dievaluasi / diaktifkan.

Saya berasumsi bahwa jenis yang diharapkan fooadalah a -> TaskT r Trampoline a. Namun, tipe sebenarnya fooadalah a -> Trampoline (TaskT r m a). Untungnya, perbaikannya mudah.

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

Jenisnya foosama dengan taskOfT, yaitu a -> TaskT r m a. Kami bisa berspesialisasi m = Trampoline.

Masalah # 3: Anda tidak menggunakan taskLiftTdengan benar

The taskLiftTFungsi mengangkat sebuah perhitungan monadik yang mendasari ke dalam TaskTlapisan.

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

Sekarang, Anda menerapkan taskLiftT(recChain)untuk foo(1)dan 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)

Namun, jika kita menggunakan definisi yang benar foomaka jenisnya tidak akan cocok.

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)

Jika kita menggunakan definisi yang benar foomaka ada dua cara untuk mendefinisikan bar. Perhatikan bahwa tidak ada cara untuk menentukan foopenggunaan dengan benar setTimeout. Oleh karena itu, saya telah mendefinisikan ulang foosebagai taskOfT.

  1. Gunakan foodan jangan gunakan 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. Jangan gunakan foodan gunakan 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] Mengapa tidak ada transformator IO di Haskell?