Help explaining how `cons` in Scheme work?

Question

This is the function that removes the last element of the list.

(define (remove-last ll)
  (if (null? (cdr ll))
      '()
      (cons (car ll) (remove-last (cdr ll)))))

So from my understanding if we cons a list (eg. a b c with an empty list, i.e. '(), we should get a b c. However, testing in interaction windows (DrScheme), the result was:

If (cons '() '(a b c))

(() a b c)

If (cons '(a b c) '())

((a b c))

I'm like what the heck :(! Then I came back to my problem, remove all elements which have adjacent duplicate. For example, (a b a a c c) would be (a b).

(define (remove-dup lst)
  (cond ((null? lst) '())
        ((null? (cdr lst)) (car lst))
        ((equal? (car lst) (car (cdr lst))) (remove-dup (cdr (cdr lst))))
        (else (cons (car lst) (car (cdr lst))))
        )

  )

It was not correct, however I realize the answer have a . between a b. How could this happen?

`(a . b)`

There was only one call to cons in my code above, I couldn't see which part could generate this .. Any idea?

Thanks,

Answer 1

cons build pairs, not lists. Lisp interpreters uses a 'dot' to visually separate the elements in the pair. So (cons 1 2) will print (1 . 2). car and cdr respectively return the first and second elements of a pair. Lists are built on top of pairs. If the cdr of a pair points to another pair, that sequence is treated as a list. The cdr of the last pair will point to a special object called null (represented by '()) and this tells the interpreter that it has reached the end of the list. For example, the list '(a b c) is constructed by evaluating the following expression:

> (cons 'a (cons 'b (cons 'c '())))
(a b c)

The list procedure provides a shortcut for creating lists:

> (list 'a 'b 'c)
(a b c)

The expression (cons '(a b c) '()) creates a pair whose first element is a list.

Your remove-dup procedure is creating a pair at the else clause. Instead, it should create a list by recursively calling remove-dup and putting the result as the second element of the pair. I have cleaned up the procedure a bit:

(define (remove-dup lst)
  (if (>= (length lst) 2)
      (if (eq? (car lst) (cadr lst))
          (cons (car lst) (remove-dup (cddr lst)))
          (cons (car lst) (remove-dup (cdr lst))))
      lst))

Tests:

> (remove-dup '(a b c))
(a b c)
> (remove-dup '(a a b c))
(a b c)
> (remove-dup '(a a b b c c))
(a b c)

Also see section 2.2 (Hierarchical Data and the Closure Property) in SICP.

For completeness, here is a version of remove-dup that removes all identical adjacent elements:

(define (remove-dup lst)
  (if (>= (length lst) 2)
      (let loop ((f (car lst)) (r (cdr lst)))
        (cond ((and (not (null? r))(eq? f (car r)))
               (loop f (cdr r)))               
              (else
               (cons (car lst) (remove-dup r)))))
      lst))

Answer 2

Here in pseudocode:

class Pair { Object left, Object right}.

function cons(Object left, Object right) {return new Pair(left, right)};

So, 1. cons('A,'B) => Pair('A,'B) 2. cons('A,NIL) => Pair('A,NIL) 3. cons(NIL,'A) => Pair(NIL,'A) 4. cons('A,cons('B,NIL)) => Pair('A, Pair('B,NIL)) 5. cons(cons('A 'B),NIL)) => Pair(Pair('A,'B),NIL)

Let's see lefts and rights in all cases: 1. 'A and 'B are atoms, and whole Pair is not a list, so (const 'a 'b) gives (a . b) in scheme 2. NIL is an empty list and 'A is an atom, (cons 'a '()) gives list (a) 3. NIL and 'A as above, but as left is list(!), (cons '() 'a) gives pair (() . a) 4. Easy case, we have proper list here (a b). 5. Proper list, head is pair (a . b), tail is empty.

Hope, you got the idea.

Regarding your function. You working on LIST but construct PAIRS. Lists are pairs (of pairs), but not all pairs are lists! To be list pair have to have NIL as tail.

(a b) pair & list (a . b) pair not list

Despite cons, your function has errors, it just don't work on '(a b a a c c d). As this is not related to your question, I will not post fix for this here.