能否通过单子类型实现惰性求值？

27 浏览
0 Comments

能否通过单子类型实现惰性求值？

我目前正在研究Javascript中关于惰性求值和单子的使用案例。因此，我尝试实现了一个惰性类型，它实现了函子/单子类型类。相应的构造函数既惰性地处理它的参数，同时也惰性地处理其结果。下面是我设计的内容:

// 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中，单调动作序列是否总是急切求值?
  • 在严格求值的语言中，惰性求值是否是一种不能用单子实现的效果?

我甚至不确定我的研究是否有意义，因此可以选择投票关闭这个问题。

admin 更改状态以发布 2023年5月21日
0

2 答案

0 Comments

这明显毫无意义，因为操作序列根本不是惰性的。Lazy.join只是过早地触发了评估

是的。所以就不要这样做了：

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

（尽管出于性能考虑，你可以并可能应该删除Lazy包装或使Lazy = id）

Haskell中的单子动作序列是否总是急切地评估？

不，Haskell不会评估任何东西，直到你告诉它要做什么。单元是没有例外的，它们像任何其他数据类型一样工作。

急切评估是否是一个在严格评估的语言中无法通过单元实现的效果？

不，它完全正常工作。

但是，你可能需要注意的是，你还没有完全实现惰性实现，它还意味着结果共享而不是重新评估。这确实需要可变性，并且仅在评估函数是纯函数时才有效。

0
0 Comments

这要看你对“实现惰性求值”的理解。你可以创建一个“延迟”类型，并将其定义为一个单子型。但通常我们认为类型为“A -> State S B”的函数是从A到B的“有状态函数”。使用“A -> Delay B”似乎已经“强制执行”了参数A。我们似乎真正需要的是类似的“Delay A -> Delay B”。\n\n事实上，有多种将表达式转换为单子样式的方法。有一种按值调用的方法，这是通常使用的方法，还有一种按名字调用的方法。这在Phil Wadler在他1992年的论文“理解单子”（Comprehending Monads）中进行了讨论。不出所料，这些与有两种翻译成继续传递方式（CPS）的类似事实有关：一种是按值调用的，一种是按名字调用的。事实上，这些就是按值/名字单子样式翻译，只是使用了一个继续单子。CPS的目的是将目标实现语言的求值顺序与源语言的求值顺序分离开。如果使用按值调用的CPS转换来实现源语言，它将具有按值语义，而不管目标语言的求值顺序是什么。同样，如果使用按名称调用的CPS转换，您将获得按名称语义，而不管目标语言的求值顺序是什么。我不确定使用按值调用翻译Delay单子会产生何种结果，但我猜测它通常会有一点偏差，而\"修正\"它会更向按名调用翻译方向靠拢。

0