Function that tests whether all items in a list are the same

Question

The program consists of two functions: the helper predicate function singleton-list? that checks whether a given list contains only one item and the function that does the actual job all-same?.

;; Predicate function: singleton-list?
;; -----------------------------------
;; The singleton-list? predicate function tests whether a list contains only a
;; single item. That is, if the list provided has got only one element in it,
;; the function returns true. In all other cases, the function returns a value
;; of false. First it checks if the object we're sent is in fact a list. If it
;; is, we check whether "cdr" returns a nonempty list. If it does, that means
;; there is more than one item in the list and thus a value of false is
;; returned.
;;
;; Usage examples:
;;     (singleton-list? '(A))     => #t
;;     (singleton-list? '(A B C)) => #f
;;     (singleton-list? '())      => #f

(define singleton-list?
    (lambda (ls)
        (and (pair? ls) (null? (cdr ls)))))


;; Predicate function: all-same?
;; -----------------------------
;; The all-same? predicate function tests whether all elements in a given list
;; are identical. Fist it checks if the list passed in is an empty list. If it
;; is, we return a value of false because the concept of sameness does not make
;; a whole lot of sense when there are no things to be compared against each
;; other. When there is only one item in a list, we return true. Otherwise,
;; we've got a list with more than one item in it. We compare the first item
;; with the second. If they're equal, we call the function recursively with our
;; list where the first element has been removed.
;;
;; Usage examples:
;;     (all-same? '(A A A)) => #t
;;     (all-same? '(A B A)) => #f
;;     (all-same? '(A))     => #t
;;     (all-same? '())      => #f

(define all-same?
    (lambda (ls)
        (cond ((null? ls)           #f) ; If empty list, return false
              ((singleton-list? ls) #t) ; If single-item list, return true
              (else                 (if (equal? (car ls) (car (cdr ls)))
                                        (all-same? (cdr ls))
                                         #f)))))

Answer 1

First, a note about testing: inside singleton-list? you check if the argument is a pair, while it is called by all-same? always with a non-empty list, so the test will be always true.

So you can simplify the program by eliminating the auxiliary function and replacing, inside the definition of all-same?, the second branch of the conditional with the only significant test:

((null? (cdr ls)) #t)

Then, note that your function returns a boolean value, and each branch of the cond and the inner if returns a boolean value. This is a good reason to perform a little simplification of the function, by using and and or as control structures (this is typical of the lisp languages). So the function could be redefined as:

(define all-same?
  (lambda (ls)
    (and (not (null? ls))
         (or (null? (cdr ls))
             (and (equal? (car ls) (cadr ls))
                  (all-same? (cdr ls)))))))

Finally, it may be questionable to decide that the function should return false when the list is empty, since in mathematics the universal quantifier is true even for an empty set. So, in case the function could be defined to return true even if the list is empty (“there are no elements, so there are no two element different”), we could further simplify the function in the following way:

(define all-same?
  (lambda (ls)
    (or (null? ls)
        (null? (cdr ls))
        (and (equal? (car ls) (cadr ls))
             (all-same? (cdr ls))))))

Answer 2

I agree with @Renzo: you should eliminate the singleton-list? helper function, and write it as a single or.

Furthermore, it's unnecessarily cumbersome to return a lambda when you could just define a function conventionally:

(define (all-same? ls)
    (or (null? ls)
        (null? (cdr ls))
        (and (equal? (car ls) (cadr ls))
             (all-same? (cdr ls)))))