置换闭包树的输出

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'参数,这样当迭代时你仍然可以调用它并接收旧的缓存值,如果传递":pause t",希望稍微进行排列清洁器.此外,虽然上面的示例是两个相同闭包的简单列表,但列表可以是任意复杂的树(可以以深度优先的顺序进行置换,并且得到的置换集将具有树的形状.).

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

提前致谢.

---

编辑感谢您的所有答案.我最终做的是向生成器添加一个'continue'参数,并通过用置换该列表的闭包替换任何嵌套列表来展平我的结构.除非传递"继续",否则生成器不会前进并始终返回最后一个缓存的值.然后我只是递归调用每个生成器,直到我到达最后一个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 中也应该可以使用宏或类似的东西将其抽象出来。