Сглаживание списка в схеме

Question

Я пытаюсь создать функцию для выравнивания списков на языке R5RS в схеме и испытываю проблему, когда моя функция просто возвращает список ввода, не удаляя скобки. Я понял, что это связано с дополнительными минусами, но когда я удаляю его, результат становится списком без элементов, которые были в круглых скобках. Может ли кто-нибудь указать мне в правильном направлении?

(define (denestify lst) 
    (cond ((null? lst)'()) 
     ((list? (car lst))(cons (denestify (cons (car (car lst))(cdr (car lst)))) 
           (denestify (cdr lst)))) 
     (else (cons (car lst)(denestify (cdr lst)))))) 

Answer 1

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

(define (denestify lst) 
    (cond ((null? lst) '()) 
     ((pair? (car lst)) 
     (append (denestify (car lst)) 
       (denestify (cdr lst)))) 
     (else (cons (car lst) (denestify (cdr lst)))))) 

Например:

(denestify '(1 (2 (3 4 (5) (6 (7) (8)) (9))) 10)) 
=> '(1 2 3 4 5 6 7 8 9 10) 

Answer 2

Это показывает, как преобразовать Óscar López ответ в один, который не использует append, а также хвостовая рекурсия :

(define (denestify-helper lst acc stk) 
    (cond ((null? lst) 
     (if (null? stk) (reverse acc) 
      (denestify-helper (car stk) acc (cdr stk)))) 
     ((pair? (car lst)) 
     (denestify-helper (car lst) acc (cons (cdr lst) stk))) 
     (else 
     (denestify-helper (cdr lst) (cons (car lst) acc) stk)))) 

(define (denestify lst) (denestify-helper lst '() '())) 

(denestify '(1 (2 (3 4 (5) (6 (7) (8)) (9))) 10)) 

Обратите внимание, как он использует аккумулятор для создания списка в обратном порядке, а также список в виде стека.

Какие результаты в

'(1 2 3 4 5 6 7 8 9 10) 

, как и ожидалось.

---

После того как я отправил это я думал, что это изменение:

(define (denestify-helper lst acc stk) 
    (cond ((null? lst) 
     (if (null? stk) (reverse acc) 
      (denestify-helper (car stk) acc (cdr stk)))) 
     ((pair? (car lst)) 
     (denestify-helper (car lst) acc (if (null? (cdr lst)) 
              stk 
              (cons (cdr lst) stk)))) 
     (else 
     (denestify-helper (cdr lst) (cons (car lst) acc) stk)))) 

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