О необходимости преобразования всех атомов в списки из одного элемента при цикле - PullRequest
Новая
       11

О необходимости преобразования всех атомов в списки из одного элемента при цикле

1 голос
/ 30 октября 2019

Учитывая вложенный список ниже, который представляет древовидную структуру, 

(A (B 1 (2 f g)) C (D 3 4) E)

Следующая функция выдаст все элементы верхнего уровня в списке, только если все A C и Eзакодированы как списки из одного элемента. 

((A) (B 1 (2 f g)) (C) (D 3 4) (E))

(defun top-level-elm (lst)
  (loop for x from 0 to (- (length lst) 1)
     collect (car (nth x lst))))

(top-level-elm '((A) (B 1 (2 f g)) (C) (D 3 4) (E)))

;; Result: (A B C D E)

Если бы мы попытались зацикливаться во вложенных списках, чтобы найти элементы верхнего уровня для каждого из них, мы столкнулись бы с проблемой необходимости хранить данные в формате с множеством скобок, чтоне только не элегантен, но также может легко привести к ошибке. 

(defun elm-id (elm lst)
  (position elm (top-level-elm lst)))

(top-level-elm (child-of (nth 3 (top-level-elm lst)) lst))

;; Error Msg: The value 3 is not of type LIST

Вместо того, чтобы переписывать данные следующим образом: 

((A) ((B) (1) ((2) (f) (g))) (C) ((D) (3) (4)) (E))

Есть ли более элегантный способ кодирования?

Обновленная функция:

Со ссылкой на ответ @ coredump ниже, я обновил вышеуказанную функцию top-level-elm следующим образом: 

(defun top-level-elm (tree)
  (loop for i from 0 to (- (length tree) 1)
     collect (elt (elt (normalize-tree tree) i) 0)))

Пожалуйста, проверьтеесли я правильно понял

1 Ответ

4 голосов
/ 30 октября 2019

Есть ли более элегантный способ кодирования?

Сначала необходимо четко определить свой формат.

Затем у вас есть два основных варианта: убедитесь, что все ваши функции обрабатывают различные угловые случаи, которые можно использовать для представления дерева,или определить внутренний формат данных, который является более регулярным (но менее удобным для пользователя);в этом случае вы сначала нормализуете / дезинфицируете свои входные данные, а затем работаете с нормализованными данными. Оба действительны, но здесь демонстрируется второй подход.

Итак, здесь вы хотите написать дерево следующим образом: 

(A (B 1 (2 f g)) C (D 3 4) E)

Это внешний формат. Из ваших описаний вы определяете дерево следующим образом:

Дерево - это список (T1 ... Tn), где T1 - Tn - это либо поддеревья, либо атомы (данные);упрощенное обозначение A, где A - ненулевой атом, представляет дерево (A);NIL - это пустое дерево.

Давайте определим вспомогательную функцию, которая, учитывая дерево ввода, предоставленное пользователем, нормализует данные, чтобы сделать их правильной формой;Ваши другие функции могут затем предположить, что дерево всегда нормализовано, что упрощает дальнейшую обработку.

Чтобы определить нормализованное дерево, я буду использовать векторы, чтобы оно явно отличалось от внешнего формата: нормализованное дерево - это вектор, содержащий вложенные нормализованные деревья или атомы .

Вектор в Common Lisp представляет собой одномерный массив;к нему можно получить доступ в постоянное время с помощью elt, а его размер можно получить также в постоянное время. Ваш код, с другой стороны, вызывает length и nth в списках, но обе операции линейны по времени для этих структур данных, что делает итерации по этим спискам медленнее, чем необходимо: 

(defun top-level-elm (lst)
  (loop for x from 0 to (- (length lst) 1)
     collect (car (nth x lst))))

length должен пройти через весь список, что, к сожалению, не катастрофично;но каждый nth также нуждается в линейном обходе, и, поскольку вы делаете это в цикле, это дает квадратичную сложность O (n ^ 2) для всего цикла.

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

Так вот, как вы бы перебрали предоставленное пользователем дерево и вернули нормализованное дерево: 

(defun normalize-tree (tree)
  (typecase tree
    (list (map 'vector #'normalize-tree tree))
    (t (vector tree))))

Если входные данные представляют собой список, каждый дочерний элемент сопоставляется с его нормализованной формой, объединяя результат в вектор. Если входные данные не являются списком, это обязательно ненулевой атом, и он нормализуется как одноэлементный вектор, содержащий это значение.

С вашим примером дерева это даст: 

(normalize-tree
 '(A (B 1 (2 f g)) C (D 3 4) E))

=> #(#(A) #(#(B) #(1) #(#(2) #(F) #(G))) #(C) #(#(D) #(3) #(4)) #(E))

К счастью, нормализованный формат не нужно показывать пользователю, это только внутренний формат, который вам полезен. Фактически, вы также можете взять нормализованное дерево и вывести его в упрощенном виде.

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

(defun simplify-normalized-tree (tree)
  (flet ((simplify-item (item)
           (typecase item
             (vector (simplify-normalized-tree item))
             (t item))))
    (let ((simplified (map 'list #'simplify-item tree)))
      (if (rest simplified)
          simplified
          (first simplified)))))

Например: 

(simplify-normalized-tree
 (normalize-tree '(A (B 1 (2 f g)) C (D 3 4) E)))

=> (A (B 1 (2 F G)) C (D 3 4) E)

Вы можете еще глубже понять всю идею внутренних данных и определить два класса, leaf и node, оба подкласса класса treeгде node содержит вектор дочерних деревьев, а leaf содержит произвольные данные. Затем обработку дерева можно выполнить в терминах общих функций и т. Д. Не всегда желательно иметь такую ​​сложность, но в более крупных проектах это может быть полезно.

...