Counting unique elements in Scheme

2
votes

Write a recursive Scheme procedure count-dist elements that takes a list with duplicate elements and returns the number of distinct elements in the list.

This is my code, but it is not working correctly. Please help! Thanks!!

(define (count-dist-elements lis)   
  (cond
    ((null? lis) 0)
    ((null? (cdr lis))0)
    ((member (car lis)(cdr lis)))
     (else(+ 1(count-dist-elements (cdr lis))))))

p/s: let it be (count-dist-elements '(1 2 1 1 2 3 4 5 5 6 6 7 7 8 8 8 9))

3
countschemeuniqueelementdistinct
I don't think this has anything to do with your difficulties, but your code is not indented quite correctly. If this reflects how it actually looks and isn't just a glitch on entering it into Stack Overflow, may I strongly recommend that you get into the habit of always indenting and spacing your code with care? This will make it easier to read (for yourself and others) and will make some mistakes harder not to notice. - Gareth McCaughan

3 Answers

1
votes

It looks like you're getting pretty close.

  • What happens when you pass your function a list with one element? What should your function return in this case?
  • What about a two-element list with the same element (eg. (5 5))? Does your function return a sensible value?
0
votes

First: Why are you returning zero in the (null? (cdr lis)) case?

Second: What do you think your code returns in the case where the first element also occurs later in the list? Are you sure?

0
votes
 (define (count-dist-elements lst dist-elems count)
   (cond ((null? lst) count)
         ((member (car lst) dist-elems)
          (count-dist-elements (cdr lst) dist-elems count))
         (else
          (count-dist-elements (cdr lst)
                               (cons (car lst) dist-elems)
                               (+ 1 count)))))

(count-dist-elements '(a b b c) '() 0) ==> 3

(count-dist-elements '(1 2 1 1 2 3 4 5 5 6 6 7 7 8 8 8 9) '() 0) ==> 9

Or, if you want it recursive and not iterative (and, it has to use a function call like the one shown),

(define (count-dist-elements lst . dist-elems)
  (let ((dist-elems (if (null? dist-elems) '() (car dist-elems))))
    (cond ((null? lst) 0)
          ((member (car lst) dist-elems)
           (count-dist-elements (cdr lst) dist-elems))
          (else
           (+ 1 (count-dist-elements (cdr lst) (cons (car lst) dist-elems)))))))

Gives the same results.

(count-dist-elements '(1 2 1 1 2 3 4 5 5 6 6 7 7 8 8 8 9)) ==> 9