checking the first atom against the other atoms in a list

Question

I am trying to check the first atom in a list against the other atoms in a list, so if the first atom is 3 and the 3rd atom is three, I would want to evaluate it to false.

I have something like

(define (doubles a_list) (cond ((null? a_list) #t) (not ((eq? (car a_list) (car (cdr a_list)))) (doubles(cdr a_list)))

I have a feeling that this will only check atoms next to each other and not the one atom with the rest of them. what can i do to check all the items with the first one?

Answer 1

You want to repeatedly compare the first two elements of your list, reducing the cdr as you go:

(define (unique-first? x)
   ; uncomment the following line to trace the execution
   ;(display x) (newline)
   (or (null? x) (null? (cdr x))
       (and (not (eq? (car x) (cadr x)))
            (unique-first? (cons (car x) (cddr x))))))

note on special cases:

• (unique-first? '()) -> #t
• (unique-first? '(a)) -> #t

(which, indeed, verify the "first element doesn't appear twice" criteria).

Answer 2

I've got my tea, my code-review hat and a few spare minutes. You know what time it is.

---

What you want is a predicate that will tell you if there are duplicates of the first atom in a list.

(define (doubles a_list) 
  (cond ((null? a_list) #t)
        (not ((eq? (car a_list) (car (cdr a_list)))) (doubles(cdr a_list)))

Regardless of anything else, this won't work because it has unbalanced parentheses.

(define (doubles a_list) 
  (cond ((null? a_list) #t)
        (not ((eq? (car a_list) (car (cdr a_list)))) (doubles(cdr a_list)))))

---

That revised version won't work because it has a malformed second clause in the case. Oddly, it does seem to evaluate fine, but when you call it, you'll get an odd error message

Welcome to Racket v5.3.6.
> (define (doubles a_list) 
  (cond ((null? a_list) #t)
        (not ((eq? (car a_list) (car (cdr a_list)))) (doubles(cdr a_list)))))
> (doubles (list 1 2 3 4 5 6 7 3))
application: not a procedure;
 expected a procedure that can be applied to arguments
  given: #f
  arguments...: [none]
> 

The direct cause is this bit

... ((eq? (car a_list) (car (cdr a_list)))) ...

Because of the extra parens surrounding this expression, what it actually means is

"See if the first element of a_list is the same as the second, then call the result of that check as a function".

This is not what you want. The correct resolution is getting that not into these parens, which would make that a valid cond clause.

(define (doubles a_list) 
  (cond ((null? a_list) #t)
        ((not (eq? (car a_list) (car (cdr a_list))))
         (doubles (cdr a_list)))))

---

You can't call car on the empty list in Scheme. This works fine, for some definition of "fine", in Common Lisp but will throw you an error here.

> (define (doubles a_list) 
  (cond ((null? a_list) #t)
        ((not (eq? (car a_list) (car (cdr a_list))))
         (doubles (cdr a_list)))))
> (doubles (list 1 2 3 4 5 6 7 3))
car: contract violation
  expected: pair?
  given: '()
> 

The cause of this error is that you're checking whether a_list is null?, but then calling (car (cdr a_list)) later on. You'll get this error in the situation where a_list is something like (3). The fix for this is checking whether a_list or its cdr are null?

(define (doubles a_list) 
  (cond ((or (null? a_list) (null? (cdr a_list))) #t)
        ((not (eq? (car a_list) (car (cdr a_list))))
         (doubles (cdr a_list)))))

> (doubles (list 1 2 3 4 5 6 7 3))
#t

---

Now that we've got a version of your function that doesn't error out, lets take a look at your logic. The procedure for finding doubles in a list is

• for lists of length zero or one, the answer is False, since there can be no doubles in a list shorter than two elements
• otherwise, check if the first element of the list is in the rest.
• if it is, the answer is True since we've found a duplicate

Now, you've named your function doubles, but your prose explanation tells me that it really should have been unique-first?. Because you're not looking for doubles, your're looking to check if the first element of your list is unique among its peers. What you really want to do is

• for lists of length one, the answer is True, since that single element must be unique (I'm going to assume that you want the same for lists of length zero, but that might not actually make sense depending on the application)
• otherwise, check that the first element of the list is not in the rest.

That translates to

(define (unique-first? a_list) 
   (if (or (null? a_list) (null? (cdr a_list)))
       #t
       (not (member? (car a_list) (cdr a_list)))))

The member? function is fairly straightforward, and works on the same principles.

(define (member? elem lst)
  (cond ((null? lst) #f)
        ((eq? elem (car lst)) #t)
        (else (member? elem (cdr lst)))))

---

Finally, a couple of style points. The Scheme convention is to name predicates with a trailing ?, which will hint to your functions' callers that it will return #t or #f (I've done this above), and to use spinal-case rather than snake_case for names.

(define (unique-first? a-list) 
  (if (or (null? a-list) (null? (cdr a-list)))
       #t
       (not (member? (car a-list) (cdr a-list)))))