How to get the even elements in a list recursively

问题:

I'm trying to create a function that will return the even numbered elements in a list.

For example:

(evens '(a b c d)) 

should return

(b d)

The code below seems to work for lists that have and odd numbers of elements, but if I give it a list with an even number of elements, it is incorrect.

For example:

(evens '(a b c d e))

will return

(b d)

But:

(evens '(a b c d))

will return

(a c)

Any thoughts?

Changed my code to:

(DEFINE (evens lis)
(cond
    ((null? lis) '())   
    (else (cons (cadr lis) (evens (cdr lis))))
    ))

Gets a error saying that the object passed to safe-car is not a pair?

回答1:

The problem is that if your list has an even number of elements, the modulo branch is matched and you start consing with the car of the list ... hence in your example, you get the a, and so on.

More importantly, though, you don't need to use length for this function ... and you shouldn't: since length takes linear time in the length of the list, evens now takes quadratic time.

Suggestion: your program should 'remember' whether it's in an 'odd' or 'even' location at each recursive step ... how could you do this (there are several ways)?

回答2:

Your code has few missing checks and a bit of incorrect logic.

(define (evens lis)
(cond
    ((null? lis) '())   
    ((eq? (cdr lis) '()) '()) ;missing condition
    (else (cons (cadr lis) (evens (cddr lis)))))) ; it is cddr not cdr

回答3:

I'm going to answer your question with commented examples, in the hope that you actually learn something instead of just being given code that works. Actually, looking at several pieces of code may be more enlightening, assuming that you're new to scheme.

Your original definition looked like this:

(define (evens lis)
  (cond (;; Check: Recursion stop condition
         (null? lis)
         '())
        (;; Wrong: Calling length at each step => O(n^2)
         ;; Wrong: Assuming even element if list has even number of elements
         (= (modulo (length lis) 2) 0) 
         ;; Wrong: Recursing with the rest of the list, you'll get odds
         (cons (car lis) (evens (cdr lis)))) 
        (else
         ;; Wrong: Recursing with the rest of the list with cdr, you'll get odds
         (evens (cdr lis)))))

Afterwards, you've edited your question to update it to something like this:

(define (evens lis)
  (cond (;; Check: Recursion stop condition
         (null? lis)
         '())   
        (else
         ;; Check: Building list with second element
         ;; Wrong: If lis only has 1 element,
         ;;        (cdr lis) is null and (car (cdr list)) is an error.
         (cons (cadr lis)
               ;; Wrong: Recursing with cdr, you'll get odds
               (evens (cdr lis))))))

A solution is to check if the list has at least a second element:

(define (evens lis)
  (cond (;; Check: Recursion stop condition 1
         (null? lis)
         '())
        (;; Check: Recursion stop condition 2: list of length = 1
         (null? (cdr lis))
         '())
        (else
         ;; Check: Building list with second element
         ;; The previous cond clauses have already sorted out
         ;; that lis and (cdr lis) are not null.
         (cons (cadr lis)
               ;; Check: Recurse "the rest of the rest" of lis with cddr
               (evens (cddr lis)))))

Exercise: Use if and or to simplify this solution to only have 2 branches.

回答4:

This same question has been asked time and again over the last couple of days. I'll give a direct answer this time, to set it straight:

(define (evens lst)
  (if (or (null? lst)             ; if the list is empty 
          (null? (cdr lst)))      ; or the list has a single element
      '()                         ; then return the empty list
      (cons (cadr lst)            ; otherwise `cons` the second element
            (evens (cddr lst))))) ; and recursively advance two elements

And here's how to do some error checking first:

(define (find-evens lst)
  (if (list? lst)
      (evens lst)
      (error "USAGE: (find-evens [LIST])")))