Closing tree output

Question

This is a conceptual question about how to implement the following in Lisp: (assuming Common Lisp in my case, but any dialect will work). Suppose you have a function that creates locks that sequentially iterate over an arbitrary collection (or otherwise return different values) of data and return zero when exhausted, i.e.

(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 

Now suppose you are trying to rearrange combinations of one or more of these closures. How do you implement a function that returns a new closure, which subsequently creates a permutation of all closures contained in it? ie:

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

which is true the following:

 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) ... 

etc.

The way I designed it was to add a pause parameter to the original counting lambda so that when you repeat, you can still call it and get the old cached value if it is passed ": pause t", hoping to do a permutation a little cleaner. In addition, while the above example is a simple list of two identical closures, the list can be an arbitrarily complex tree (which can be rewritten in the order of depth-first order, and the resulting set of permutations will be in the form of a tree.).

It was implemented with me, but my solution was not very clean, and I am trying to ask how others approach this problem.

Thanks in advance.

---

edit Thanks for all the answers. What I ended up with was adding the continue argument to the generator and smoothing my structure, replacing any nested list with a closure that moved that list. The generators did not advance and always returned the last cached value if the "continue" was not transmitted. Then I just recursively called each generator until I got to the last cdr or nil. If I got to the last cdr, I just ran into it. If I got to NIL, I ran into it before it, and reset every close after it.

Answer 1

You will obviously need some way of using each value returned by the generator more than once.

In addition to Rainer Joswig's suggestions, three approaches come to mind.

Caching values

permute-closures can, of course, remember every value returned by each generator, storing it in a list and reusing it again and again. This approach explicitly involves some memory overhead, and it won’t work very well if the generated sequences can be infinite.

Creating new generators at each iteration

In this approach, you would change the permute-closures signature to accept not the ready-to-use generators as arguments, but the clumps that create them. Your example would look like this:

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

That way permute-closures can reset the generator just to recreate it.

Providing copying generator states

You could provide a way to create copies of the generators along with your states. This is similar to approach # 2 in that permute-closures will reset the generators as needed, except that the reset will be done by returning to a copy of the original state. In addition, you will be able to perform partial resets (i.e., return to an arbitrary point, not just the beginning), which may or may not make permute-closures code much easier.

Copying generator states may be a little easier in a language with first-class continuations (e.g. Scheme), but if all generators follow some predefined structure, abstracting it with the define-generator macro or some of them should be possible in Common Lisp.

Answer 2

I would add one of them to the counter:

• the ability to reset the start counter

• so that the counter returns NIL when the counter is done, and then starting from the first value again on the next call