title: Scheme: Return all elements of an expression that can be obtained using any combination of car and cdr
body: <p>I'm trying to write a procedure in Scheme (R5RS) of my CS class that takes an expression (either a symbol or a list) as an argument and returns a list of (1) all the possible expression that can be formed by using car and cdr on the expression and (2) and an expression demonstrating how each of these components of the original expression were obtained. If a piece can be obtained in more than one way, it should be returned more than once.</p>
  
  <pre><code>Examples
  
  (pieces '()) =&gt; ((() x))
  
  (pieces 'apple) =&gt;  ((apple x))
  
  (pieces '(apple)) =&gt; (((apple) x) (apple (car x)) (() (cdr x)))
  
  (pieces '(a (b c))) =&gt;
                 (((a (b c)) x)
                  (a (car x))
                  (((b c)) (cdr x))
                  ((b c) (car (cdr x)))
                  (b (car (car (cdr x))))
                  ((c) (cdr (car (cdr x))))
                  (c (car (cdr (car (cdr x)))))
                  (() (cdr (cdr (car (cdr x)))))
                  (() (cdr (cdr x))))
  </code></pre>
  
  <p>Since we've just started with Scheme, we're limited to fairly basic syntax for this assignment. Here's what I have so far:</p>
  
  <pre><code>(define pieces
    (lambda (exp)
      (cond
        ((symbol? exp)
         (list exp 'x))
        ((null? exp)
         (list '() 'x))
        ((list? exp)
         (let ((b (pieces (car exp))) (c (pieces (cdr exp))))
            (list exp 'x b c))))))
  
  (pieces '()) =&gt; (() x)
  
  (pieces 'apple) =&gt; (apple x)
  
  (pieces '(apple)) =&gt; ((apple) x (apple x) (() x))
  
  (pieces '(a (b c))) =&gt; ((a (b c)) x (a x) (((b c)) x ((b c) x (b x) ((c) x (c x) (() x)))
                         (() x)))
  </code></pre>
  
  <p>The procedure returns all of the proper elements, but each recursion causes the components to be nested in an additional list. Is there any way to prevent that?</p>
  
  <p>Also, I have no idea where to start for the second part of the problem (showing how each element was obtained from the original using car and cdr). I've tried a million different approaches, and none of them have even been close to working. If anyone has any hints or suggestions on how to implement that feature, I'd really appreciate it. Thanks a ton.</p>