javascript - 惰性求值可以通过 monadic 类型实现吗？

Question

我目前正在研究结合 Javascript 中的 monad 的惰性求值，以及可能从中演化出哪些用例。所以我尝试实现一个惰性类型，它实现了 functor/monad 类型类。相应的构造函数在其参数和结果中是惰性的。这是我想出的:

// a lazy type

// (() -> a) -> () -> b
const Lazy = thunk => () => thunk();

// (b -> a -> b) -> b -> Lazy a -> b
Lazy.fold = f => acc => tx => f(acc) (tx());

// (a -> b) -> Lazy a -> Lazy b
Lazy.map = f => tx => Lazy(() => f(tx()));

// Lazy (a -> b) -> Lazy a -> Lazy b
Lazy.ap = tf => tx => Lazy(() => tf() (tx()));

Lazy.of = Lazy;

// Lazy (Lazy a) -> Lazy a
Lazy.join = ttx => ttx();

// (a -> Lazy b) -> Lazy a -> Lazy b
Lazy.chain = ft => tx => Lazy.join(Lazy.map(ft) (tx));

// recursive bind (or chain in Javascript)

// Number -> (a -> b) -> a -> Lazy b
const repeat = n => f => x => {
  const aux = m => y => m === 0
   ? Lazy(() => y)
   : Lazy.chain(aux(m - 1)) (Lazy(() => f(y)));

  return aux(n) (x);
};

// impure function to observe the computation

const inc = x => (console.log(++x), x);

// and run

console.log(repeat(5) (inc) (0)); // logs 1, 2, 3, 4, 5, () => thunk()

现在这显然没有意义，因为 Action 序列一点也不懒惰。 Lazy.join 只是过早地触发评估。因此，出现了以下问题:

• Haskell 中的单子(monad) Action 序列是否总是急切求值？
• 惰性求值是一种不能由严格求值语言中的 monad 实现的效果吗？

我什至不确定我的研究是否有意义，所以请随意投票结束这个问题。

Answer 1

这取决于您所说的“实现惰性求值”是什么意思。你当然可以制作一个“延迟”类型，它将是一个单子(monad)。但通常我们将类型为 A -> State S B 的函数视为“从 A 到 B 的有状态函数”。对于 A -> Delay B 之类的东西，似乎对于参数 A 我们已经“强制”了它。看起来我们真的想要更像 Delay A -> Delay B 的东西。

事实证明，有多种方法可以将表达式转换为 monadic 样式。一种按值调用方式，这是通常的方式，一种按名称调用方式。 Phil Wadler 在他 1992 年的论文中对此进行了讨论 Comprehending Monads (PDF)。毫不奇怪，这些与一个类似的事实有关，即有两种转换为连续传递样式 (CPS) 的方式:按值调用和按名称调用。实际上，这些正是带有延续 monad 的 call-by-value/-name monadic 风格的翻译。 CPS 的目的是将目标实现语言的评估顺序与源语言的评估顺序分开。如果您使用按值调用 CPS 转换来实现源语言，那么无论目标语言的评估顺序是什么，它都将具有按值调用语义。同样，如果您使用按名称调用 CPS 转换，您同样会获得按名称调用语义，而不管目标语言的评估顺序如何。

我不知道当使用带有 Delay monad 的按值调用转换时，事情会如何发展，但我怀疑它通常会“稍微”偏离并且“更正”，它将更倾向于按名称进行翻译。