如何在标准ML中创建一个不断增加大小的按需呼叫列表

Question

我正在尝试创建一个带有列表元素的惰性列表，这些列表元素一起表示0和1的所有组合。

示例：[[]，[0]，[1]，[0,0]，[0,1]，[1,0]…]

这在ML中可能吗？一旦我定义了列表元素的模式，我似乎就找不到改变它的方法。似乎还需要定义二进制模式的改变，这在函数语言中是不可能的(我从未在函数语言遇到过二进制表示)？

Answer 1

这里似乎有两个不同的问题：

1. 我们如何生成这种特殊的无限数据结构
2. 在ML中，我们如何实现按需调用

---

让我们从考虑第一点开始。我将按步骤生成这个特定的数据结构，其中第n步的输入是长度n的所有位模式的列表。我们可以通过在长度n的每个模式上加上0和1来生成长度n+1。代码中：

fun generate patterns =
let
val withZeros = List.map (fn pat => 0 :: pat) patterns
val withOnes = List.map (fn pat => 1 :: pat) patterns
val nextPatterns = withZeros @ withOnes
in
current @ generate nextPatterns
end
val allPatterns = generate [[]]

如果您要在Haskell等按需调用语言中实现这种方法，那么它将在开箱即用时表现良好。但是，如果您在ML中运行此代码，它将不会终止。这就引出了第二个问题：我们如何在ML中按需调用？

---

要在ML中按需调用，我们需要使用悬架。直观地说，暂停是一项计算，可能尚未运行，也可能尚未运行。合适的接口和实现如下所示。我们可以使用delay挂起计算，防止它立即运行。稍后，当我们需要挂起的计算的结果时，我们可以force它。这个实现使用引用来记住以前强制挂起的结果，保证任何特定的挂起最多只能评估一次。

structure Susp :>
sig
type 'a susp
val delay : (unit -> 'a) -> 'a susp
val force : 'a susp -> 'a
end =
struct
type 'a susp = 'a option ref * (unit -> 'a)
fun delay f = (ref NONE, f)
fun force (r, f) =
case !r of
SOME x => x
| NONE => let val x = f ()
in (r := SOME x; x)
end
end

接下来，我们可以根据暂停来定义懒惰列表类型，其中列表的尾部是延迟的。这使我们能够创建看似无限的数据结构；例如，fun zeros () = delay (fn _ => Cons (0, zeros ()))定义了一个无限的零列表。

structure LazyList :>
sig
datatype 'a t = Nil | Cons of 'a * 'a t susp
val singleton : 'a -> 'a t susp
val append : 'a t susp * 'a t susp -> 'a t susp
val map : ('a -> 'b) -> 'a t susp -> 'b t susp
val take : 'a t susp * int -> 'a list
end =
struct
datatype 'a t = Nil | Cons of 'a * 'a t susp
fun singleton x =
delay (fn _ => Cons (x, delay (fn _ => Nil)))
fun append (xs, ys) =
delay (fn _ =>
case force xs of
Nil => force ys
| Cons (x, xs') => Cons (x, append (xs', ys)))
fun map f xs =
delay (fn _ =>
case force xs of
Nil => Nil
| Cons (x, xs') => Cons (f x, map f xs'))
fun take (xs, n) =
case force xs of
Nil => []
| Cons (x, xs') =>
if n = 0 then []
else x :: take (xs', n-1)
end

有了这台机器，我们可以调整原始代码，在正确的位置使用惰性列表和暂停：

fun generate patterns =
delay (fn _ =>
let
val withZeros = LazyList.map (fn pat => 0 :: pat) patterns
val withOnes = LazyList.map (fn pat => 1 :: pat) patterns
val nextPatterns = LazyList.append (withZeros, withOnes)
in
force (LazyList.append (patterns, generate nextPatterns))
end)
val allPatterns = generate (LazyList.singleton [])

我们可以使用LazyList.take:强制执行此列表中的一部分

- LazyList.take (allPatterns, 10);
val it = [[],[0],[1],[0,0],[0,1],[1,0],[1,1],[0,0,0],[0,0,1],[0,1,0]]
: int list list