Глубокий реверс для деревьев в Схеме

Question

У меня есть глубокий переворот для базовой древовидной структуры данных в Схеме

(define (deep-reverse t)
  (cond ((null? t) '())
        ((not (pair? t)) t)  
        (else (cons (deep-reverse (cdr t)) (deep-reverse (car t))))))

(define stree (cons (list 1 2) (list 3 4)))
1 ]=> (deep-reverse stree)
;Value: (((() . 4) . 3) (() . 2) . 1)

Я чувствую себя чище, лучше результат будет:

(4 3 (2 1))

Может кто-нибудь дать некоторые рекомендациигде я ошибаюсь в своей функции глубокого реверса?Спасибо.

Answer 1

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

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

(define (deep-reverse t)
  (map (lambda (x)
         (if (list? x)
             (deep-reverse x)
             x))
       (reverse t)))

Answer 2

Попробуйте это:

(define (deep-reverse t)
  (let loop ((t t)
             (acc '()))
    (cond ((null? t) acc)
          ((not (pair? t)) t)
          (else (loop (cdr t)
                      (cons (loop (car t) '()) acc))))))

Назовите это так:

(define stree (cons (list 1 2) (list 3 4)))
(deep-reverse stree)
> (4 3 (2 1))

Для создания перевернутого списка, один метод заключается в накоплении ответа в параметре (я обычно называю этоacc).Поскольку мы работаем со списком списков, рекурсия должна вызываться как в части списка car, так и в части cdr.Наконец, я использую с именем let в качестве сокращения, чтобы избежать создания дополнительной функции, но тот же результат можно получить, определив вспомогательную функцию с двумя параметрами, деревом и аккумулятором:

(define (deep-reverse t)
  (aux t '()))

(define (aux t acc)
  (cond ((null? t) acc)
        ((not (pair? t)) t)
        (else (aux (cdr t)
                   (cons (aux (car t) '()) acc)))))

Answer 3

Для меня сработало следующее:

(define (deep-reverse tree)
  (define (deep-reverse-iter items acc)
    (cond
      ((null? items) acc)
      ((not (pair? items)) items)
      (else (deep-reverse-iter
        (cdr items)
        (cons (deep-reverse (car items)) acc)))))
  (deep-reverse-iter tree ()))

(define x (list (list 1 2) (list 3 4 (list 5 6))))

(newline)
(display (deep-reverse x))

Он печатает (((6 5) 4 3) (2 1)) как положено и использует минимум стандартных функций библиотеки: pair?, чтобы проверить, является ли дерево cons и null? для проверки пустого дерева / списка.

Это решение для деревьев является обобщением функции reverse для списков:

(define (reverse items)
  (define (reverse-iter items acc)
    (cond
      ((null? items) acc)
      ((not (pair? items)) items)
      (else (reverse-iter (cdr items) (cons (car items) acc)))))
  (reverse-iter items ()))

разница в том, что deep-reverse такжеприменяется к car items

Answer 4

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

(defun deep-reverse (tree)
   (cond ((zerop (length tree)) nil)
         ((and (= 1 (length tree)) (atom (car tree))) tree)
         ((consp (car tree)) (append (deep-reverse (cdr tree)) 
                                     (list (deep-reverse (car tree)))))
         (t (append (deep-reverse (cdr tree)) (list (car tree))))))