List to dotted pair notation

Question

I am trying to write a simple Scheme function which convert given list to its dotted pair notation .

For example if the input is -

((1 (2)) 3 ((4)))

What will correspond to its dotted pair notation and what rules should be kept in the function to write such logic.

Any such pointers will be truly grateful.

Answer 1

If you ever implement your own LISP and need to do this remember than what you are asking actually is simpler than displaying lists as lists rather than dotted pair notation. Here's one way to do it:

(define (my-display x)
  (let recur ((x x) (list-mode #f))
    (cond ((pair? x)
           (display (if list-mode " " "("))
           (recur (car x) #f)
           (recur (cdr x) #t))
          ((not list-mode) (display x))
          ((null? x) (display ")"))
          (else 
           (display " . ")
           (display x)
           (display ")")))))

You see that we need to keep a state telling us that we are processing a list since how it looks depend on the cdr. What you want is to treat all pairs the same even when the cdr is () or pair? so it's much simpler:

(define (my-display x)
  (let recur ((x x))
    (cond ((pair? x)
           (display "(")
           (recur (car x))
           (display " . ")
           (recur (cdr x))
           (display ")"))
          (else (display x)))))

Of course a real implementation of this might have much more logic to display the different atomic values so thanks to that these actually just address the pairs. When making my own Lisp Zozotez print was the second largest function after read.

Answer 2

@Chris has given the right approach. Just make sure that printing the car and the cdr are actually recursive calls to your procedure:

(define (display-dotted sexp)
  (cond
    ((null? sexp) (display "()"))
    ((pair? sexp) (display "(")
                  (display-dotted (car sexp))
                  (display " . ")
                  (display-dotted (cdr sexp))
                  (display ")"))
    (else         (display sexp))))

then

> (display-dotted '((1 (2)) 3 ((4))))
((1 . ((2 . ()) . ())) . (3 . (((4 . ()) . ()) . ())))

Answer 3

Here is the long form:

((1 . ((2 . ()) . ())) . (3 . (((4 . ()) . ()) . ())))

Writing a function to print the long form is simple:

1. If the input is a pair, print the following:
   1. "(" or #\(
   2. The car of the pair
   3. " . "
   4. The cdr of the pair
   5. ")" or #\)
2. Otherwise, print the item as is.