可以通过单子类型实现惰性评估吗？

Question

我目前正在与Java中的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()

现在，这显然没有任何意义，因为动作序列根本不是惰性的。Lazy.join只是过早地触发评估。因此，出现了以下问题：

• 是否总是热切评估Haskell中的单子动作序列？
• 惰性评估是单子不能用严格评估的语言实现的效果吗？

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

Answer 1

这取决于“实施惰性评估”的含义。你当然可以创建一个“Delay”类型，它将是一个 monad。但通常我们认为具有类型的函数A -> State S B是“从A到的有状态函数B”。对于类似的东西A -> Delay B，似乎对于论证A我们已经“强迫”它了。看来我们真的想要更多类似的东西Delay A -> Delay B。

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

我不知道当使用带有 monad 的按值调用翻译时，事情会如何进行Delay，但我怀疑它通常会“稍微”关闭，并且“纠正”它会更倾向于调用- 名字翻译。