перевернуть общий список по схеме

Question

Я пытаюсь изменить общий список, используя схему. Как я могу перевернуть сложный список?

Я могу сделать так, чтобы один список работал (ABCD), используя мою функцию, но для некоторого сложного списка внутри другого списка, например (F ((ED) CB) A),результат просто (A ((ED) CB) F). Как я могу улучшить это?

(define (reverse lst)
    (if (null? lst)
        lst
        (append (reverse (cdr lst)) (list (car lst)))))

Любые комментарии будут высоко оценены!

Answer 1

Вот еще один способ, который использует параметр по умолчанию (r null) вместо дорогостоящей операции append -

(define (reverse-rec a (r null))
  (if (null? a)
      r
      (reverse-rec (cdr a)
                   (cons (if (list? (car a))
                             (reverse-rec (car a))
                             (car a))
                         r))))

(reverse-rec '(F ((E D) C B) A))
; '(A (B C (D E)) F)

Использование процедуры более высокого порядка foldl позволяет нам кодировать то же самое бездополнительный параметр -

(define (reverse-rec a)
  (foldl (lambda (x r)
           (cons (if (list? x) (reverse-rec x) x)
                 r))
         null
         a))

(reverse-rec '(F ((E D) C B) A))
; '(A (B C (D E)) F)

Answer 2

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

(define (reverse x)
    (cond ((null? x) '())
          ((not (list? x)) x)
          (else (append (reverse (cdr x)) (list (reverse (car x)))))))

(reverse '(F ((E D) C B) A))

'(A (B C (D E)) F)

Answer 3

(A ((E D) C B) F) - правильный результат, если ваша цель - изменить список ввода. В списке ввода было три элемента, и теперь присутствуют те же три элемента в обратном порядке. Поскольку это правильно, я не советую вам улучшать его поведение!

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