Flattening a list in scheme

Question

I'm attempting to create a function for flattening lists in the R5RS language in scheme and am experiencing the issue where my function simply returns the input list without removing the parenthesis. I figured this was due to the extra cons, but when I remove it the output becomes the list without the elements that were in the parenthesis. Can someone point me in the right direction?

(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

This shows how to convert Óscar López answer into one that doesn't use append and is also tail recursive:

(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))

Note how it uses the accumulator to build up the list in reverse and also a list as a stack.

Which results in

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

as expected.

---

After I posted this I thought of this change:

(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))))

Which eliminates some useless consing by effectively doing tail-call optimization on our stack. One could go further and optimize handling of one element lists.

Answer 2

If you want to flatten a list of lists, then you have to use append to combine each sublist. Besides, your implementation is overly complicated, try this instead:

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

For example:

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