Eliminate inner parenthesis runs into empty list a

问题:

The goal is to eliminate all inner parenthesis.

(flatten '(a (b c) d)) becomes '(a b c d)

This is my code in Racket

; if slist is null, return empty
; otherwise, if it is a pair, recursively solve car and cdr and concat them
; if it is a symbol, return the symbol

(define flatten
  (lambda (slist)
    (cond
      [ (null? slist) '()]
      [ (pair? slist)  
        (cons ((flatten (car slist)) (flatten (cdr slist))))]
      [ (symbol? slist) slist])))

It's complaining

procedure application: expected procedure, given: c; arguments were: ()

which means I am trying to access car and cdr of an empty list.

I did the trace:
> (flatten '(a (b c) d))
pair?-car-cdr
a
((b c) d)
symbol?
a
pair?-car-cdr
(b c)
(d)
pair?-car-cdr
b
(c)
symbol?
b
pair?-car-cdr
c
()
symbol?
c
(stops here)

The trace code is simple - a bunch of displays.

(define flatten
  (lambda (slist)
    (cond
      [ (null? slist) '()]
      [ (pair? slist) 
        (display 'pair?-car-cdr)
        (newline)
        (display (car slist))
        (newline)
        (display (cdr slist))
        (newline)
        (cons ((flatten (car slist)) (flatten (cdr slist))))]
      [ (symbol? slist) 
         (display 'symbol?)
         (newline)
         (display slist)
         (newline)
        slist])))

What I don't understand is how come the first condition (null? slist) didn't catch the empty list? I have two recursive calls. If it did catch the empty list, it would go to the next recursion which is the list {d}.

What is the problem with my recursion logic?

---

Update version

(define flatten
  (lambda (slist)
    (cond
      [ (null? slist) '()]
      [ (pair? slist)  
        (cons (flatten (car slist)) (flatten (cdr slist)))]
      [ (symbol? slist) slist])))

(display (equal? (flatten '(a (b a) b a c (a b) c (e f (b a)))) '(a b a b a c a b c e f b a)))
(newline)
(display (equal? (flatten '(a b c)) '(a b c)))
(newline)
(display (equal? (flatten '(a (b c))) '(a b c)))
(newline)
(display (equal? (flatten '((a)(b)(c) d)) '(a b c d)))
(newline)
(display (equal? (flatten '(a (b) ((c)) (((d))) ((((e (f g))))))) '(a b c d e f g )))
(newline)
(display (equal? (flatten '()) '()))
(newline)
(display (equal? (flatten '(a b () ())) '(a b)))
(newline)

As Ross Larson suggested, append will make the program works. But for the sake of learning, if any one have the time to spare, the result of my tests show only the base cases passed (2nd and the empty list)

I thought about writing a wrapper function which calls (cons (flatten slist) empty)

回答1:

The problem is this expression:

((flatten (car slist)) ...)

This means, apply whatever (flatten ...) returns. But since this returns a list, the application fails.

Change it to

(flatten (car slist))

回答2:

cons is going to recreate the structure (As you have observed). Take a look into append instead.

http://docs.racket-lang.org/reference/pairs.html

(I don't address the other issues as it seems the other answers have fixed the application of the recursion value)