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

Question

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

// 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 中的单子动作序列是否总是急切求值？
惰性求值是不是严格求值语言中的monad无法实现的效果？

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

Answer 1

this evidently makes no sense, since the action sequence isn't lazy at all. Lazy.join simply triggers the evaluation prematurely

是的。所以不要那样做：

// (() -> (() -> a)) -> (() -> a)
Lazy.join = ttx => Lazy(() => ttx()());
//                         ^^ this function prevents `ttx` from being evaluated immediately

（虽然你可以，并且出于性能原因可能应该删除 Lazy 包装器或制作 Lazy = id）

are sequences of monadic actions in Haskell always eagerly evaluated?

不，Haskell 在您告诉它执行之前不会评估任何内容。 Monads 也不例外，它们像任何其他数据类型一样工作。

is lazy evaluation an effect that cannot be implemented by a monad in a strictly evaluated language?

不，它工作得很好。

但是，您可能想注意到您还没有完全实施 lazy implementation，这也意味着共享结果而不是重新评估。这确实需要可变性，并且只有在评估函数是纯函数时才能很好地工作。

Answer 2

玩转

你的问题很有趣，我还没有探索过这样的 monad，所以我想尝试一下。

正如 Bergi 指出的那样，您的数据构造函数中不需要额外的 thunk 包装器——即，Lazy 期望它的参数已经是一个 thunk。

您的 join 被破坏了——尽管看起来有悖常理，但您必须确保包装解包过程！将其视为添加一个包装器，但删除两个；你仍然删除了一层嵌套，达到了预期的结果

你的 monadic return（或本例中的 of）也坏了； return 并不总是与您的数据构造函数相同——即 Lazy.of(2) 应该等同于 Lazy($ => 2)

你的代码启发了我，所以我修改它直到我完成这个。我想你会很高兴 ^_^ Bergi 还建议 Lazy 不应该重新评估其结果。我通过 runLazy 方法中的安全记忆处理了这个问题。对此的反馈将不胜感激 <3

personal code style

As a convention, I write thunks as $ => expr instead of () => expr. When writing functional programs in JavaScript, you end up with a lot of ()s, often times adjacent to other ()s which can sometimes hurt readability. I think Lazy($ => f()) reads (at least) slightly better than Lazy(() => f()). Since this is meant to be an educational site, I figure this is worth mentioning. I feel like small change helps with readability, but I also don't want to confuse anyone.

For anyone that's stuck, feel free to substitute () for all $ in the code below. Moving along now ...

// data Lazy = Lazy (Unit -> a)
const Lazy = t => ({
  memo: undefined,
  // runLazy :: Lazy a -> Unit -> a
  runLazy () {
    return this.memo === undefined
      // console.log call just for demonstration purposes; remove as you wish
      ? (this.memo = t(), console.log('computed:', this.memo), this.memo)
      : this.memo
  },
  // chain :: Lazy a -> (a -> Lazy b) -> Lazy b
  chain (f) {
    return Lazy($ => f(this.runLazy()).runLazy())
  }
})

// Lazy.of :: a -> Lazy a
Lazy.of = x =>
  Lazy($ => x)
  
// repeat :: Int -> (a -> a) -> a -> Lazy a
const repeat = n => f => x =>
  n === 0
    ? Lazy.of(x)
    : Lazy.of(f(x)).chain(repeat (n-1) (f))

// m :: Lazy Number
const m = repeat (5) (x => x * 2) (1)

console.log('computations pending...')
// ...
console.log(m.runLazy()) // (1 * 2 * 2 * 2 * 2 * 2) => 32
console.log(m.runLazy()) // => 32

至于满足其他类别，这里有一些Lazy的方法实现。我在 empty 上挂断了 Monoid，但也许你或其他人对此有一些想法！

我还看到你从 f => join(map(f)) 派生了 chain，这也很好

函子

// map :: Lazy a -> (a -> b) -> Lazy b
map (f) {
  return Lazy($ => f(this.runLazy()))
}

适用

// apply :: (a -> b) -> a -> b
const apply = f => x => f (x)

// ap :: Lazy (a -> b) -> Lazy a -> Lazy b
ap (m) {
  return Lazy($ => apply (this.runLazy()) (m.runLazy()))
}

Monad

// Lazy.of :: a -> Lazy a
Lazy.of = x =>
  Lazy($ => x)

// chain :: Lazy a -> (a -> Lazy b) -> Lazy b
chain (f) {
  return Lazy($ => f(this.runLazy()).runLazy())
}

// join :: Lazy (Lazy a) -> Lazy a
join () {
  return Lazy($ => this.runLazy().runLazy())
}

幺半群

// empty
empty () {
  // unsure on this one
}

// concat :: (Monoid a) => Lazy a -> Lazy a -> Lazy a
concat (m) {
  return Lazy($ => this.runLazy().concat(m.runLazy()))
}

开启探索

这个话题对我来说很有趣，所以我很乐意讨论我在这里写的任何内容或关于本文中提出的想法的任何其他评论 question/answer。让我们玩得更开心！

Answer 3

这取决于你所说的 "implementing lazy evaluation" 是什么意思。你当然可以创建一个 "Delay" 类型，它将是一个 monad。但通常我们认为类型为 A -> State S B 的函数是 "stateful function from A to B"。对于像 A -> Delay B 这样的东西，似乎对于参数 A 我们已经 "forced" 它了。看起来我们真的想要更像 Delay A -> Delay B.

的东西

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

我不知道在 Delay monad 中使用按值调用转换时会发生什么事情，但我怀疑它通常会 "just a bit" 关闭并且 "correcting" 它将更倾向于按名称翻译。

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

Can lazy evaluation be implemented by a monadic type?

javascript

haskell

functional-programming

lazy-evaluation