实现懒惰和记忆

Question

惰性是《纯函数式数据结构》一书中的基石，但没有明确描述他是如何获得它的，至少对我来说是这样。我以为我只需要写：

datatype 'a susp = $ of 'a
fun force ($x) = x
fun plus (x, y) = $case (x, y) of ($m, $n) => m + n

但后来我收到错误：

- use "ch4.sml";;
[opening ch4.sml]
ch4.sml:3.20 Error: syntax error: inserting  ORELSE
[unexpected exception: Compile]

uncaught exception Compile [Compile: "syntax error"]
raised at: ../compiler/Parse/main/smlfile.sml:19.24-19.46
../compiler/TopLevel/interact/evalloop.sml:45.54
../compiler/TopLevel/interact/evalloop.sml:306.20-306.23
../compiler/TopLevel/interact/interact.sml:65.13-65.16

---

我尝试将函数修改为

fun plus (x, y) = $(print "Evaluating...\n"; force x + force y)

但是用它来调用它并plus ($4, $5)对其进行了评估并且没有记住它，因为它返回$ 9而不是并且$ plus(force $4, force $5)打印了Evaluating...两次。

- plus ($4, $5);;
Evaluating...
val it = $ 9 : int susp
- plus ($4, $5);;
Evaluating...
val it = $ 9 : int susp

---

我也想获取关键字lazy，但我不确定 SML New Jersey 是否支持这个，它是否是由 Chris Okasaki 实现的，或者是手动脱糖的。该关键字在我的编辑器中突出显示，但在写作时

fun lazy plus ($x, $y) = $ (x + y)

我知道这是一个带有两个参数并且由类型给出的lazy函数：plus($x, $y)

val lazy = fn : 'a -> int susp * int susp -> int susp

---

我的问题归结为如何在新泽西州 SML 获得惰性和记忆？

Answer 1

您需要启用惰性并添加一些括号（$书中的 具有特殊的解析规则）：

Standard ML of New Jersey v110.83 [built: Thu May 31 09:04:19 2018]
- Control.lazysml := true;
[autoloading]
[ ... boring details ...] 
[autoloading done]
val it = () : unit
- open Lazy;
[autoloading]
[autoloading done]
opening Lazy

  datatype 'a susp = $ of 'a
- fun plus (x, y) = $(case (x, y) of ($m, $n) => m + n);
val plus = fn : int susp * int susp -> int susp
-  val x = plus($4, $5);
val x = $$ : int susp
- fun force ($x) = x;
val force = fn : 'a susp -> 'a
- force x;
val it = 9 : int
- fun lazy plus ($x, $y) = $ (x + y);
val plus = fn : int susp * int susp -> int susp
val plus_ = fn : int susp * int susp -> int

请注意，这不会记忆plus。