CODEWITHSUNDEEP
schemeequalitymember
padawanMiyagi
padawanMiyagi

Reputation: 116

Trying to check if all elements of a list are unique

As the title suggest i am trying to write a scheme function that checks if all elements of a list are unique. I have written some code that i think should work: 

(define are-all-unique?
      (lambda (v)
        (if (member (car v) (cdr v))
            #f
            (if (pair? v)
                (are-all-unique? (cdr v))
                #t))))

and it works fine in the case where it is false, but if i write:

 (are-all-unique? '(1 2 3))

it returns: 

Exception in car: () is not a pair

Does anyone have a clue on how to fix this, and what i am doing wrong? :)

Upvotes: 2

Views: 1759

Answers (1)

belph
belph

Reputation: 362

Well, as your error message states, you're attempting to pass the empty list to car. As for why that's happening, let's take a look at your code.

As we know, we need to pass a cons cell to car and cdr for them to work. We check for this property using pair?, which you are doing. The problem is when you're doing it.

The best way to debug a function like this is trace through what happens when you pass the bad input (in this case '()) to the function. The first thing it will do is run the test in your if statement: (member (car v) (cdr v)). Now, since the input we're tracing is the empty list, this will fail every time. What you want is something more like this: 

;; are-all-equal? is a poor choice of function name, by the way, since that's
;; not really what this function checks
(define are-all-unique? 
  (lambda (v)
    (if (pair? v)
        ; The only way that this branch will ever execute is
        ; if (pair? v) is true, so we know that (car v) and (cdr v)
        ; will never raise any exceptions
        (and (not (member (car v) (cdr v)))
             (are-all-unique? (cdr v)))
        #t)))

The thing to note here is the control flow structure of this version of the function: a proper list is either a cons cell or the empty list, so we have two cases in our function (one for each possibility). When writing functions which deal with lists, one should (for the most part) decide what you want to do in the nonempty and empty cases, and make sending the list argument to the appropriate case the first thing you do inside of the function. Such an approach is appropriate when doing structural recursion (i.e., in the words of one of my freshman professors, 'the structure of your data informs the structure of your code').

Upvotes: 4

Related Questions