Перестановка вывода дерева замыканий

Это концептуальный вопрос о том, как можно реализовать следующее в Лиспе (в моем случае предполагается Common Lisp, но подойдет любой диалект). Предположим, у вас есть функция, которая создает замыкания, которые последовательно перебирают произвольную коллекцию (или иным образом возвращают разные значения) данных и возвращают ноль при исчерпании, т.е.

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

и так далее.

] Первоначально я задумал добавить параметр «пауза» к исходной лямбде подсчета, чтобы при итерации вы все еще могли вызывать его и получать старое кэшированное значение, если передано ": pause t", в надежде произвести перестановку немного чище. Кроме того, хотя приведенный выше пример представляет собой простой список из двух идентичных замыканий, список может быть произвольно сложным деревом (которое может быть переставлено в порядке глубины, и результирующий набор перестановок будет иметь форму дерева).

Я реализовал это, но мое решение было не очень чистым, и я пытаюсь узнать, как другие подойдут к этой проблеме.

Заранее спасибо.


edit Спасибо за все ответы. В конечном итоге я добавил к генератору аргумент «продолжить» и сгладил мою структуру, заменив любой вложенный список замыканием, которое переставляло этот список. Генераторы не продвигались вперед и всегда возвращали последнее кэшированное значение, если не было передано «continue». Затем я просто рекурсивно вызывал каждый генератор, пока не добрался до последнего cdr или nil. Если я добрался до последнего компакт-диска, я просто наткнулся на него. Если я доходил до NIL, я натыкался на предыдущее и сбрасывал каждое последующее закрытие.

8
задан yan 23 February 2011 в 19:41
поделиться