Can someone explain the following Scheme code?

Question

I have been listening to Stanford's programming paradigm lecture series, but I'm confused by the following code (from lecture 20). Would someone explain, line by line, what this is doing?

Thanks.

(define (flatten sequence)
(cond ((null? sequence) '())
((list? (car sequence)) (append (flatten (car sequence))
(flatten (cdr sequence))))
(else (cons (car sequence) (flatten (cdr sequence))))))

Answer 1

# define a procedure 'flatten' that takes a list 'sequence'
(define (flatten sequence)
  # if the 'sequence' is empty, return an empty list
  (cond ((null? sequence) (list))
        # if the first element of 'sequence' is itself a list, return a new list
        # made by appending the flattened first element of 'sequence' with the
        # flattened rest of the 'sequence'
        ((list? (car sequence))
         (append (flatten (car sequence))
                 (flatten (cdr sequence))))
        # if the first element of 'sequence' is not a list, return a new list
        # made by cons-ing that element with the flattened rest of the 'sequence'
        (else
         (cons (car sequence)
               (flatten (cdr sequence))))))

I pretty-printed it (inserted some newlines and indented the code to show its structure) and also replaced '() with (list) (which has the same value) just to prevent the code from being highlighted incorrectly.

+1 what is cons-ing? I'd appreciate if you explain other keywords as well. thanks

When I say cons-ing I'm just referring to the cons procedure. When you see (cons <expression> <list>) where <expression> is any Scheme expression or value and <list> is any Scheme expression that evaluates to a list, cons will return the <list> with the value of the <expression> tacked on the front of it. For example, (cons 1 (list 2 3 4)) returns the list (list 1 2 3 4). In fact, (list 1 2 3 4) in Scheme is just a short way of writing (cons 1 (cons 2 (cons 3 (cons 4 '() )))).

The other two words you might have trouble with are car and cdr. You can think of (car <list>) as meaning the first element or head of the <list>, and (cdr <list>) as meaning the rest of the elements or tail of the <list>. For example, (car (list 1 2 3 4)) returns the value 1, and (cdr (list 1 2 3 4)) returns the list (list 2 3 4).

If you need any help with other keywords, let me know.

Answer 2

1. define function to flatten a sequence

2. For the empty sequence, return empty

3. if the head (car) of the list is a sequence return the result of flattening it appended to the flattening of the tail (cdr)

4. else append the head to the flatting of the tail