Перестановочный вывод дерева замыканий - PullRequest
Новая
       32

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

8 голосов
/ 29 января 2011

Это концептуальный вопрос о том, как можно реализовать следующее в Лиспе (предполагая Common Lisp в моем случае, но любой диалект будет работать).Предположим, у вас есть функция, которая создает замыкания, которые последовательно перебирают произвольную коллекцию (или иным образом возвращают разные значения) данных и возвращают 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' к начальному лямбда-счетчику так, чтобы при итерации вы все равно могли вызывать его и получать старый кэшированныйзначение, если передано ": pause t", в надежде сделать перестановку немного чище.Кроме того, хотя вышеприведенный пример представляет собой простой список из двух идентичных замыканий, этот список может быть произвольно сложным деревом (которое может быть переставлено в порядке глубины, а результирующий набор перестановок будет иметь форму дерева).

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

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

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

Ответы [ 2 ]

2 голосов
/ 30 января 2011

Вам, безусловно, потребуется какой-то способ использования каждого значения, возвращаемого генератором, более одного раза.

В дополнение к предложениям Райнера Йосвига, на ум приходят три подхода.

Кэширование значений

permute-closures может, конечно, помнить каждое значение, возвращаемое каждым генератором, сохраняя его в списке, и использовать его снова и снова. Этот подход, очевидно, подразумевает некоторые накладные расходы памяти, и он не будет работать очень хорошо, если генерируемые последовательности могут быть бесконечными.

Создание новых генераторов на каждой итерации

В этом подходе вы бы изменили сигнатуру permute-closures, чтобы принимать в качестве аргументов не готовые к использованию генераторы, а блоки, которые их создают. Ваш пример будет выглядеть так: 

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

Таким образом, permute-closures может сбросить генератор, просто воссоздав его.

Создание копий состояний генератора

Вы можете предоставить способ создания копий генераторов вместе с их состояниями. Это своего рода подход № 2 в том, что permute-closures будет сбрасывать генераторы по мере необходимости, за исключением того, что сброс будет выполнен путем возврата к копии исходного состояния. Кроме того, вы сможете выполнить частичный сброс (т. Е. Выполнить возврат к произвольной точке, а не к началу), что может сделать или не сделать код permute-closures значительно проще.

Копирование состояний генератора может быть немного проще в языке с продолжениями первого класса (например, Схема), но если все генераторы следуют некоторой предопределенной структуре, абстрагирование ее с помощью макроса define-generator или некоторых других должно быть возможно в Common Лисп также.

1 голос
/ 29 января 2011

Я бы добавил к счетчику любой из этих:

  • возможность сброса счетчика на начало

  • разрешение счетчику вернуть NIL, когда счет завершен, а затем снова начать с первого значения при следующем вызове

...