Getting same parity for a list of numbers

Question

I'm doing the SICP exercise of filtering a list based on the odd/even-ness of the first argument. For example:

(same-parity 1 2 3 4 5 6 7)
; parity of first argument '1' is odd
; and we apply the 'odd' filter to the remaining list, (2 3 4 5 6 7)
(1  3 5 7)

Here is what I've come up with, which I'm having a bit of trouble with:

; Helper function
(define (list-append lst elem)
  (if (null? lst)
      (cons elem nil)
      (cons (car lst) (list-append (cdr lst) elem))))

; Actual function
(define (same-parity first . lst)
  ; start with an empty list, and we'll build it with side-effects
  (define L '())
    (define (same-parity-inner remaining-lst)
      ; when the list is exhausted, just return L
      (cond ((null? remaining-lst) L)
            ; if the current element of the list has the same parity
            ; as the first element, add that to our list
            (else (if (= (modulo first 2) (modulo (car remaining-lst) 2))
                      (list-append L (car remaining-lst)))
                    ; and then recurse with the remaining list elements
                   (same-parity-inner (cdr remaining-lst)))))
    (same-parity-inner lst))

Now I know there are a ton of nice solutions on the SICP problems, but I'm wondering if someone can point out where the folly of my implementation is, and help me figure out a better way to do it.

Update, here is one implementation, it's not great but it's the first working version I have. I found it a bit tricky having to use the 'actual list' instead of the vargs function param so I wrote another inner function to accept an actual list (maybe there's a better way to do this?).

; Helper
(define (append-list lst1 lst2)
  (if (null? lst1)
      lst2
      (cons (car lst1) (append (cdr lst1) lst2))))


(define (same-par first . lst)
  (define (same-par-inner lst)
    (cond ((null? lst) '())
          ((= (modulo first 2) (modulo (car lst) 2)) (append-list (list (car lst)) (same-par-inner (cdr lst)) ))
          (else (same-par-inner (cdr lst)))))
  (same-par-inner lst))

(same-par 1 2 3 4 5 6 7 99 11)
; (3 5 7 99 11)

Is there a way to do this recursively without defining an inner function?

Barmar Barmar · Accepted Answer · 2021-05-24T21:34:40

You can use apply to make the recursive calls without using a helper function. Its last argument is a list, which will be spread into arguments in the function call. This allows you to pass first again as well as (cdr lst).

You can also just use cons to build a new list from an element and a subsequent list, rather than creating a temporary list to use append-list.

(define (same-par first . lst)
  (cond ((null? lst) '())
        ((= (modulo first 2) (modulo (car lst) 2))
         (cons (car lst)
               (apply same-par first (cdr lst)) ))
        (else (apply same-par first (cdr lst)))))

Getting same parity for a list of numbers

1 Answers