Scheme: Extract every number in the list and reconstruct the list?

Question

This is a homework question, but I really just need some hints, that's all.
Basically, I need to create this function flat that's supposed to re-contract a new list from the input list (but here, the input list can have a nested list inside):

ex. flat of (A (B (C) D) A) is (A B C D A)

My algorithm is the following, not sure if it's correct:

1. Check if the list is empty: if not, go on; if yes, done -- return the empty list
2. If the list has length 1, done -- return the list
3. If list has length more than 1, what do I do now? (I can use car and cdr to extract the list, but in either case, how can I make it recursively extract the list to the end, and I'm thinking use append to re-construct the list after.)

Any help/hints would be appreciated.

Answer 1

The hint is that, if the list isn't null?, you shouldn't focus on the length of the list passed in to flat, but instead check to see whether the car of the list is a list itself or just an atom. If it's a list itself, you want to flatten it, as well as flattening the cdr of the list.

EDIT: Well, consider what happens in two different cases, one where you use cons and one where you use append:

(append '(a b c) '(d e f)) => (a b c d e f)

(cons '(a b c) '(d e f)) => '((a b c) d e f)

In the first case, you get a flat list back, and in the second case, you don't get a flat list back. You might then try

(define (bad-flatten lst) 
  (if ((null? lst) 
      '()
      (append (car (flatten lst)) (cdr (flatten lst)))))

but it won't work if the car of lst isn't a list. You need a third case, using cond, like so:

(define (incomplete-flatten lst)
  (cond ((null? lst) 
         '())
        ((list? (car lst)) 
         (append (flatten (car lst)) (flatten (cdr lst))))
        (else 
         ;; you need to do something different here. I can
         ;; think of at least two options.
        )))

Answer 2

Might not be the most optimized solution. Probably you can improve it further:

(define (list-flatten lst)
  (if (not (null? lst))
      (let loop ((args lst) (ret (list)) (c null))
         (if (not (null? args))
           (begin
             (set! c (car args))
             (cond ((list? c) (loop (cdr args) (append ret (list-flatten c)) c))
             (else (loop (cdr args) (append ret (list c)) c))))
           ret))
       #f))