0

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.

Nathan Hughes
  • 94,330
  • 19
  • 181
  • 276
user3390460
  • 1
  • 1
  • What should `(oddatom '(() () ()))` return? Should be #t but everybody is returning #f... everybody except my #2 answer. – GoZoner Apr 04 '14 at 00:29
  • @GoZoner According to the Little Schemer (p. 10, see also http://stackoverflow.com/a/12610253/1193075) '() is *not* an atom. – uselpa Apr 05 '14 at 14:29

5 Answers5

1

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)))))
C. K. Young
  • 219,335
  • 46
  • 382
  • 435
1

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)))))))
Community
  • 1
  • 1
Joshua Taylor
  • 84,998
  • 9
  • 154
  • 353
  • Chris' answer actually is tail recursive for flat lists. I remember I checked the performance of a similar version of `count-atoms` and something similar to your code and I was surprised that the shorter code won against more clever algo in my tests except the worst case with all atoms in `cdr`. – Sylwester Apr 03 '14 at 00:20
  • For flat lists, the difference will be negligible, but mine will allocate more heap space. Even so, Chris's version makes two calls to the recursive function, and only one of them is in tail position. – Joshua Taylor Apr 03 '14 at 00:35
  • Olin Shivers argues, in SRFI 1's commentary, that using a heap-based "stack" in the name of making an algorithm tail-recursive isn't usually worth it. Read http://srfi.schemers.org/srfi-1/srfi-1-reference.scm, "A note on recursion and iteration/reversal". Excerpt: The natural and efficient way to code these algorithms is recursively. This trades off intermediate temporary list structure for intermediate temporary stack structure. In a stack-based system, this improves cache locality and lightens the load on the GC system. Don't stand on your head to iterate! Recurse, where natural. – C. K. Young Apr 03 '14 at 19:06
  • @ChrisJester-Young I agree. It is good practice, though, to learn how to convert between the two forms, so I like to include both where possible (e.g., as shown in [this answer](http://stackoverflow.com/a/22844738/1281433)). I'll update the answer though, to indicate that this isn't necessarily any more performant, and that even if it were, it comes at a cost of some readability. – Joshua Taylor Apr 03 '14 at 20:36
0

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)
uselpa
  • 18,732
  • 2
  • 34
  • 52
0

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)))))))
GoZoner
  • 67,920
  • 20
  • 95
  • 145
0

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
>
GoZoner
  • 67,920
  • 20
  • 95
  • 145