Построить список в Лиспе, используя итеративную рекурсивную функцию

Question

Супер новичок в Лиспе, но, по крайней мере, я пытаюсь простить меня, если подход кажется немного странным.
Я открыт для изучения новых идей, но мне определенно нужно узнать, что не так с моим подходом.
У меня есть функция, которая создает список с использованием итеративного рекурсивного подхода.

(defun create-tree-iteratively(sub-list)
    (if (equal (length sub-list) 1)
        sub-list
        (loop for i in sub-list
            do(setq subtree (list i))
            do(setq sub-sub-list (remove i sub-list))
            do(append subtree (create-tree-iteratively sub-sub-list))
        )
    )
)

Входные данные для моей программы:

'(1 2 3)

Ожидаемый результат:

'((1 (2 3) (3 2)) (2 (1 3) (3 1)) (3 (1 2) (2 1)))

Мои циклы (рекурсия) запускают файл.У меня есть проблемы в правильной обработке результатов рекурсии.

Answer 1

Некоторые начальные примечания.

• Задавая вопрос, который включает в себя реализацию алгоритма опишите алгоритм : нелегко угадать, что вы хотите, основываясь на одном примере (ниже я сделал два предположения).
• Я полагаю, что вы уже писали на Python ранее, так как в вашем коде присутствуют значительные признаки «Python Braindamage» (обратите внимание, что это комментарий о Python, который я потратил годымоей жизни, а не о ваших способностях).В частности:
  • Lisp не путает формы, которые создают новые привязки (переменные) с присваиванием, как это делает Python.Вы не создаете новую привязку в функции с помощью setq, вы создаете ее с помощью некоторой формы привязки, такой как let;
  • Вы не добавляете новые элементы в конец списка с помощью append вы создаете новый список, в который добавляются новые элементы, и поскольку списки являются связанными списками, а не массивами переменной длины при перетаскивании, append занимает время, пропорциональное длине списка.
• Но в одном отношении ваш код игнорирует важный урок Python: все эти маркеры закрытия групп не имеют значения для любого, кто читает код, и вам не следует заполнять строки маркерами закрытия (или открытия) одной группы,Они просто шум, который затрудняет чтение кода.На самом деле в Python они настолько невидимы, что их вообще не существует.Это одна из вещей, которые Python понял правильно.

Как говорится, здесь есть три версии того, что я думаю вы хотите: первая реализует то, о чем я думаюпоследовательный алгоритм, второй реализует то, что, я думаю, вам может понадобиться, а последний - абстрагирует тест завершения и может выполнять любой (или любой другой)).

(defun make-permuted-tree (l)
  ;; this builds the tree all the way down
  (if (null l)
      '()
    (loop for e in l
          collect (cons e (make-permuted-tree (remove e l))))))

(defun make-permuted-tree/strange (l)
  ;; this stops before the end
  (if (null (rest l))
      l
    (loop for e in l
          collect (cons e (make-permuted-tree/strange (remove e l))))))

(defun make-permuted-tree/general (l &key (base-test (lambda (b)
                                                       (null b))))
  ;; this stops where you want it to, which by default is at the end
  (labels ((make-permuted-tree (lt)
             (if (funcall base-test lt)
                 lt
               (loop for e in lt
                     collect (cons e (make-permuted-tree (remove e lt)))))))
    (make-permuted-tree l)))

В качестве примеров этого:

> (make-permuted-tree/strange '(1 2 3))
((1 (2 3) (3 2)) (2 (1 3) (3 1)) (3 (1 2) (2 1)))

> (make-permuted-tree '(1 2 3))
((1 (2 (3)) (3 (2))) (2 (1 (3)) (3 (1))) (3 (1 (2)) (2 (1))))

> (make-permuted-tree/general '(1 2 3))
((1 (2 (3)) (3 (2))) (2 (1 (3)) (3 (1))) (3 (1 (2)) (2 (1))))

> (make-permuted-tree/general '(1 2 3) :base-test (lambda (b)
                                                    (null (rest b))))
((1 (2 3) (3 2)) (2 (1 3) (3 1)) (3 (1 2) (2 1)))

Answer 2

Стиль кода

• Желательно не иметь закрывающих скобок в своих собственных строках, обычное соглашение в Лиспе - это сгруппировать круглые скобки в конце, например: ))).

• Поскольку cons-ячейки имеют только два слота, CAR и CDR, когда они используются в качестве списка, они не содержат длину списка.Таким образом, единственный способ вычислить длину - это пересечь всю цепочку ячеек, что и делает ваша функция.Если ваш список имеет размер N, вам придется вычислять длину N раз, что делает число шагов в вашей функции пропорциональным N * N.

• В цикле,за одним DO может следовать несколько выражений, вам не нужно повторять ключевое слово DO.Кроме того, добавьте пробелы перед открытием скобок.

• SETQ не должен применяться с несвязанными переменными, такими как subtree или sub-sub-list.Сначала у вас должно быть окружение let, где вы вводите локальные переменные (например, вокруг loop) или используете предложения with в цикле.Или лучше использовать существующие возможности LOOP, чтобы избежать мутации самостоятельно.

• Возвращаемое значение APPEND важно, так как это результат добавления аргументов (которыйостаются неизменными).Но здесь вы не используете возвращаемое значение, что делает все выражение бесполезным.

Альтернатива

Вместо вычисления длины достаточно проверить, является ли вводсписки пустые, содержат один или несколько элементов (без учета).Также вы можете использовать collect, чтобы собрать все деревья в виде списка.Я не уверен, что результат для одноэлементного списка ввода правильный, возможно, он должен быть (list list).

(defun create-tree (list)
  (if (null (rest list))
      ;; covers both empty list and list with a single element
      list
      ;; otherwise, collect a list of trees
      (loop
        for i in list
        ;; collect all trees rooted at i, where a tree is a list (r c1 .. cn)
        ;; with R the root node and C1...CN each child tree. The child trees
        ;; are build recursively, with i removed from the list of values.
        collect (list* i (create-tree (remove i list))))))