functional-programming - 排列闭包树的输出

Question

这是一个关于如何在 Lisp 中实现以下内容的概念性问题(假设我使用的是 Common Lisp，但任何方言都可以)。假设您有一个创建闭包的函数，该闭包顺序迭代任意数据集合(或以其他方式返回不同的值)并在耗尽时返回 nil，即

(defun make-counter (up-to)
  (let ((cnt 0))
    (lambda ()
       (if (< cnt up-to)
           (incf cnt)
           nil))))

CL-USER> (defvar gen (make-counter 3))
GEN
CL-USER> (funcall gen)
1
CL-USER> (funcall gen)
2
CL-USER> (funcall gen)
3
CL-USER> (funcall gen)
NIL
CL-USER> (funcall gen)
NIL

现在，假设您正在尝试排列一个或多个这些闭包的组合。 您将如何实现一个返回新闭包的函数，该闭包随后创建其中包含的所有闭包的排列？即:

(defun permute-closures (counters)
  ......)

满足以下条件:

CL-USER> (defvar collection (permute-closures (list 
                                                 (make-counter 3)
                                                 (make-counter 3))))
CL-USER> (funcall collection)
(1 1)
CL-USER> (funcall collection)
(1 2)
CL-USER> (funcall collection)
(1 3)
CL-USER> (funcall collection)
(2 1)
...

等等。

我最初设计它的方式是在初始计数 lambda 中添加一个“暂停”参数，这样在迭代时你仍然可以调用它并在传递“:pause t”时接收旧的缓存值，希望排列稍微干净一些。此外，虽然上面的示例是两个相同闭包的简单列表，但该列表可以是任意复杂的树(可以按深度优先顺序排列，并且生成的排列集将具有树的形状。)。

我实现了这个，但我的解决方案不是很干净，我正在尝试调查其他人如何解决这个问题。

提前致谢。

---

编辑 感谢您的所有回答。我最终做的是向生成器添加一个“继续”参数，并通过用置换该列表的闭包替换任何嵌套列表来展平我的结构。除非通过“继续”，否则生成器不会前进并且总是返回最后一个缓存的值。然后我只是递归地调用每个生成器，直到我到达最后一个 cdr 或一个 nil。如果我到达最后一个 cdr，我只是碰到它。如果我得到一个 NIL，我会碰到它之前的那个，并重置它后面的每个闭包。

Answer 1

您显然需要某种方式多次使用生成器返回的每个值。

除了 Rainer Joswig 的建议外，我还想到了三种方法。

缓存值

permute-closures 当然可以通过将每个生成器返回的每个值存储在列表中来记住每个值，并一遍又一遍地重复使用它。这种方法显然意味着一些内存开销，如果生成的序列可以是无限的，它就不会很好地工作。

在每次迭代中创建新的生成器

在这种方法中，您将更改 permute-closures 的签名，使其不是现成的生成器而是创建它们的 thunk 作为参数。您的示例将如下所示:

(permute-closures (list (lambda () (make-counter 3))
                        (lambda () (make-counter 3))))

这样，permute-closures 就可以通过简单地重新创建生成器来重置它。

使生成器状态可复制

您可以提供一种复制生成器及其状态的方法。这有点像方法 #2，因为 permute-closures 将根据需要重置生成器，除了重置将通过恢复到原始状态的副本来完成。此外，您将能够进行部分重置(即回溯到任意点，而不仅仅是开始)，这可能会或可能不会使 permute-closures 的代码明显更简单。

在具有一流延续性的语言(如 Scheme)中复制生成器状态可能会更容易一些，但如果所有生成器都遵循一些预定义的结构，则使用 define-generator 宏或在 Common Lisp 中也应该有一些这样的东西。