CODEWITHSUNDEEP
listrecursionschemeequalselement
trever
trever

Reputation: 1003

Checking if all elements in a list are the same in scheme

Define a recursive procedure 'all-zeroes?' that takes a list of bits and returns #t if and only if the list contains only zeroes. We are representing the bits zero and one by the first and third lower case letters in the word "oil". So far i have 

(define all-zero?
  (lambda (lst)
    (if (equal? lst '(o))
        #t
        (if (equal? (all-zero? (cons (cdr (lst)) '() )) '(o))
            #t
            #f)
        )
    )
  )

but its returning, variable all-zeroes? is not bound. What am i doing wrong and am I even on the right track?

Upvotes: 1

Views: 2606

Answers (2)

GoZoner
GoZoner

Reputation: 70135

You are looking for 'all zeros' in a list. If the first element of the list is not a zero then you are done with a false answer; if the first element is a zero, then continue on. When the list is empty then it had all zeros. This is expressed naturally using recursion, as such:

(define (all-zero? list)
  (or (null? list)                     ; #t if list is empty
      (and (eq? 'o (car list))         ; head is zero … 
           (all-zero? (cdr list)))))   ; … continue with rest.

Your code had a number of errors and style slip-ups:

  1. (cdr (lst)) ends up making a function call to lst but lst is not a function
  2. boolean functions, like equal? return #t/#f; no need to add them to your code
  3. stylistically 'hanging parens' (parens on a line by themselves) are to be avoided.
  4. your comparison with equal? should be based on the first element of lst

Upvotes: 1

Óscar López
Óscar López

Reputation: 235984

The function in the question is named all-zero?, but you're calling it as all-zeroes?, that explains the error. There are other more serious mistakes, though:

  • You're surrounding lst between parentheses, but lst is not a function: (lst)
  • The recursion is not being correctly advanced
  • You should use cond instead of nesting ifs

The correct way to implement this function would be to check if any element is not zero (returning #f) or keep traversing the list until it's empty, taking as convention that an empty list is #t for the condition:

(define all-zeroes?
  (lambda (lst)
    (cond ((null? lst) #t)
          ((not (eq? (car lst) 'o)) #f)
          (else (all-zeroes? (cdr lst))))))

The above can be further simplified using boolean connectors:

(define all-zeroes?
  (lambda (lst)
    (or (null? lst)
        (and (eq? (car lst) 'o)
             (all-zeroes? (cdr lst))))))

Depending on the interpreter in use, you can express the solution more succinctly. For example, in SRFI-1 you can use every or in Racket we have andmap:

(define (all-zeroes? lst)
  (andmap (curry eq? 'o) lst))

Anyway, it works as expected:

(all-zeroes? '(o o o))
=> #t
(all-zeroes? '(o o l))
=> #f

Upvotes: 1

Related Questions