OpenMusic: генерация дерева L-System с использованием lisp

Я пытаюсь работать с композиционным инструментом под названием OpenMusic, который представляет собой графическую среду разработки, основанную на общем lisp, и он использует нечто, называемое «деревьями ритма». Я пытаюсь создать деревья ритмов, используя набор правил, и в ОМ это дерево должно иметь следующую структуру:

  • Дерево — это список из двух элементов
  • Его первый элемент — узел
  • Его второй элемент — это список его дочерних элементов (которые также могут быть деревьями).

Учитывая глубину дерева n, начальное дерево с одним узлом (1) и правила преобразования:

  • (1) -> (1 2)
  • (2) -> (1)

Это должно дать:

n = 1 -> (1 (1 2))


tree lisp common-lisp l-systems
person kureta    schedule 21.04.2016    source источник
comment
Так где вопрос? Помните, что это не сервис по написанию кода ;)   -  person Daniel Jour    schedule 21.04.2016
comment
вы правы @Daniel, вопрос в том, как я могу определить это поведение рекурсивно? ответ может быть простым английским языком, поэтому не код службы. Я понятия не имею, с чего начать. Мне даже не нужен ответ, просто подтолкнуть в правильном направлении было бы более чем достаточно.   -  person kureta    schedule 22.04.2016
comment
@kureta Можете ли вы попытаться объяснить вопрос немного лучше? Может быть, добавить несколько примеров вызовов функций, их результатов и того, как результат был достигнут (в основном напишите процесс, который вы хотите, чтобы компьютер выполнял). Как сейчас, по крайней мере, я не могу понять, чего ты хочешь. Я имею в виду, вы начинаете с (1). Это преобразуется в (1 2) по первому правилу. Для (1 2) нет правила преобразования, так как же получить (1 (1 2))? Предполагается, что атомы в нем тоже трансформируются (но тогда у вас будет ((1 2) (1)))?   -  person jkiiski    schedule 22.04.2016
comment
@jkiiski согласно моему приведенному выше определению деревьев, использующих списки, правила применяются к узлам. поэтому один начальный узел 1 должен иметь двух дочерних элементов 1 и 2. Это результирующее дерево (1 наверху с двумя дочерними элементами 1, 2) представлено как (1 (1 2)). Это дерево имеет две конечные точки (листья) 1 и 2. Применение правил к одному дает 1 и 2. Применение правил к 2 дает один. поэтому после этого шага дерево равно (1 ((1 (1 2)) (2 (1))))   -  person kureta    schedule 22.04.2016
comment
mitpress.mit.edu/sicp/full-text/book/book. html   -  person    schedule 22.04.2016
comment
Спасибо @Rei Думаю, я отмечу этот ответ.   -  person kureta    schedule 22.04.2016

Ответы (1)


arrow_upward
1
arrow_downward

Рекурсивные алгоритмы для деревьев/списков обычно записываются с COND. Вы выясняете, каковы конечные условия, и ставите их на первое место. Затем обработайте атомы и, наконец, выполните итерацию по списку, рекурсивно вызывая функцию для его CAR и CDR и CONS результатов для создания выходного списка. Итак, базовый шаблон выглядит так:

(defun algo (list)
  (cond
    ((end-condition) suitable-end-value)
    ((atom list) (do-something-with-atom list))
    (t (cons (algo (car list)
             (algo (cdr list))))))

В этом случае это будет что-то вроде:

(defun rhythm-tree (n tree)
  (cond ((zerop n) tree)                 ; First end-condition.
        ((null tree) '())                ; Another end-condition.
        ((atom tree)                     ; An atom: transform into...
         (cons tree                      ; a list of the atom itself...
               (list (rhythm-tree (1- n) ; and a list of children.
                                  (case tree
                                    (1 (list 1 2))
                                    (2 (list 1))
                                    (otherwise '()))))))
        ;; Iterate over elements of a list.
        (t (cons (rhythm-tree n (car tree))
                 (rhythm-tree n (cdr tree))))))

(rhythm-tree 1 1)
;=> (1 (1 2))
(rhythm-tree 2 1)
;=> (1 ((1 (1 2)) (2 (1))))
person jkiiski    schedule 22.04.2016
comment
Большое спасибо! Это было невероятно полезно. - person kureta; 22.04.2016