Scheme output has extra parenthesis and periods-CodePudding

I started learning Scheme today, and wanted to write a function that would reverse a list (only surface level, nested lists stay in the same order).

Heres the function I made:

(define reverse (lambda (lst)
                  (if (> (length lst) 0)
                      (cons (reverse(cdr lst)) (car lst))
                      '()
                      )))

I thought it would just continuously add the values before everything after it so in the end it's reversed, but when doing (reverse '(5 12 31 7 98 13)), I should get (13 98 7 31 12 5), but instead I get '((((((() . 13) . 98) . 7) . 31) . 12) . 5). How come it's adding periods and parenthesis instead of adding the number to the list?

CodePudding user response：

(list x y ..... z) list structure is constructed like this in Scheme:

(cons x
      (cons y
            …
            …
            (cons z '())))

if you use append instead of cons and put your (car lst) into a list of its own, your code will work:

(define reverse 
   (lambda (lst)
     (if (> (length lst) 0)
         ;;(cons (reverse (cdr lst))       (car lst) )
         (append (reverse (cdr lst)) (list (car lst)))
         '()
     )))

CodePudding user response：

The list (13 98 7 31 12 5) is a visualization of the pairs (13 . (98 . (7 . (31 . (12 . (5 . ())))))). If the cdr is a pair or the empty list the dot and one set of parens is omitted. The code to create this structure is (cons 13 (cons 98 (cons 7 (cons 31 (cons 12 (cons 5 '())))))) while the structure your function creates is (cons (cons (cons (cons (cons (cons 13 '()) 98) 7) 31) 12) 5).

When iterating a list you always do it in order. eg. (1 2 3) is quite difficult to do in reverse. However when creating lists you always do them from end to beginning. eg. (cons 1 (cons 2 (cons 3 '()))) will have to evaluate the cons with 3 before the one with 2 etc. This can be used for a very efficent reverse using an accumulator:

(define (reverse lst acc)
  (if (null? lst)
      acc
      (reverse (cdr lst) 
               (cons (car lst) acc))))

So imagine calling this (reverse '(1 2 3) '()):

(reverse '(1 2 3) '())        ; => 
(reverse '(2 3) (cons 1 '())) ; ==> 
(reverse '(3) (cons 2 '(1)))  ; ==> 
(reverse '() (cons 3 '(2 1))) ; ==> 
'(3 2 1)