CODEWITHSUNDEEP
scheme
user3390460
user3390460

Reputation: 1

How to determine if a list has an even or odd number of atoms

tScheme novice question:

I need to determine if a list contains an even or odd amount of atoms using recursion. I know the easy way is to get list length and determine if it is even or odd, but I would like to see hows it's done using recursion.

(oddatom 
  (LIST 'x 'y 'v 'd 'r 'h 'y))

should return #t, while 

(oddatom 
  '((n m) (f p) l (u k p)))

should return #f

appreciate the help.

Upvotes: 0

Views: 2115

Answers (5)

GoZoner
GoZoner

Reputation: 70165

If '() is an atom (like it is in CommonLisp where '() is also T), it should be (odd-atom? '(() () ())) is #t:

(define (odd-atom? obj)
  (and (not (null? obj))
       (or (not (pair? obj))
           (let ((this? (or (null?     (car obj)) 
                            (odd-atom? (car obj))))
                 (rest? (odd-atom? (cdr obj))))
             (not (eq? this? rest?))))))
> (odd-atom? '())
#f
> (odd-atom? '(()))
#t
> (odd-atom? '(() () ()))
#t
> (odd-atom? '(() ()))
#f
> (odd-atom? '(() (a)))
#f
> (odd-atom? '(() (a b)))
#t
> (odd-atom? '((a) (a b)))
#t
> (odd-atom? '((a b) (a b)))
#f
>

Upvotes: 0

GoZoner
GoZoner

Reputation: 70165

Here is one:

(define (odd-atom? obj)
  (and (not (null? obj))
       (or (not (pair? obj))
           (let ((this? (odd-atom? (car obj)))
                 (rest? (odd-atom? (cdr obj))))
             (or (and (not this?) rest?)
                 (and (not rest?) this?))))))

or, learning from @uselpa to simplify the 'or this? rest?' logic above, another one:

(define (odd-atom? obj)
  (and (not (null? obj))
       (or (not (pair? obj))
           (not (eq? (odd-atom? (car obj))
                     (odd-atom? (cdr obj)))))))

Upvotes: 0

Joshua Taylor
Joshua Taylor

Reputation: 85853

I like Chris Jester-Young's answer, but I think it's worth providing a tail-recursive version that maintains its own stack as well. Note that this is an exercise in converting non-tail recursion into tail recursion, which is an imporant technique for some algorithms in Scheme. In this case, though, it's probably not all that important, and the code in Chris Jester-Young's answer does feel much more natural. So take this as an exercise, not necessarily a significant improvement.

The idea here is that the inner function, odd?, takes a list of things, and a value indicating whether an odd number of atoms (other than the empty list) have been seen so far.

(define (oddatom? thing)
  (let odd? ((things (list thing))
             (result #f))
    (cond
      ;; We're out of things to see.  Did we see an odd number of things?
      ((null? things)
       result)
      ;; Our list of things has the form ((x . y) …), so we recurse on 
      ;; (x y …), with the *same* value for result, since we haven't 
      ;; "seen" x or y yet, we've just "unwrapped" them.
      ((pair? (car things))
       (odd? (cons (caar things) (cons (cdar things) (cdr things))) result))
      ;; Our list of things has the form (() …), so we recurse on 
      ;; (…), with the *same* value for result, since we haven't "seen" any
      ;; additional atoms.
      ((null? (car things))
       (odd? (cdr things) result))
      ;; Our list of things has the form (<atom> …), so we recurse on (…), 
      ;; but with a flipped value for result, since we've seen one more atom.
      (else
       (odd? (cdr things) (not result))))))

The last two cases could be combined, making the second recursive argument based on the value of (null? (car things)) as:

(define (oddatom? thing)
  (let odd? ((things (list thing))
             (result #f))
    (cond
      ((null? things)
       result)
      ((pair? (car things))
       (odd? (cons (caar things) (cons (cdar things) (cdr things))) result))
      (else
       (odd? (cdr things) (if (null? (car things))
                              result
                              (not result)))))))

Upvotes: 1

C. K. Young
C. K. Young

Reputation: 223023

Here's my version of the solution:

(define (oddatom? lst)
  (let recur ((odd #f)
              (x lst))
    (cond ((null? x) odd)
          ((pair? x) (recur (recur odd (car x)) (cdr x)))
          (else (not odd)))))

Upvotes: 1

uselpa
uselpa

Reputation: 18917

I'd go for this:

(define (oddatom lst)
  (cond
    ((null? lst)       #f)
    ((not (pair? lst)) #t)
    (else (not (eq? (oddatom (car lst)) (oddatom (cdr lst)))))))

which means:

  1. the empty list is not odd (#f)
  2. an atom is odd (#t)
  3. otherwise, one and only one of the car or the cdr of the list may be odd (exclusive or).

Test cases (in Racket), including improper lists:

(require rackunit)
(check-equal? (oddatom (list 'x 'y 'v 'd 'r 'h 'y)) #t)
(check-equal? (oddatom '((n m) (f p) l (u k p))) #f)
(check-equal? (oddatom '(a (b) c)) #t)
(check-equal? (oddatom (cons 1 2)) #f)
(check-equal? (oddatom 1) #t)
(check-equal? (oddatom '(1 (2 . 3))) #t)

Upvotes: 0

Related Questions