How to break (11 (12 13)) using Car and Cdr in Scheme

3
votes

I need to return from a list only those values which are odd so I am trying to break my list using car and cdr functions. I have a recursive funciton call that checks if the Car returns a list then further break it using car and cdr , otherwise just pass the first element to a function call check if Odd.

The problem with the special case (10 11 (12 13)) is that car returns 10 cdr returns (11 (12 13))

then in second iteration car returns (11 (12 13)) cdr returns (11 (12 13))

so How can i further break my list using car and cdr. I need to preserve the brackets in my final answer as well as only return the list having odd values of integers.

3
listfunctional-programmingscheme
I'm confused, the car of (11 (12 13)) is 11. It looks like you have some kind of logic error in your program, because at a high level the approach you describe sounds like it would work, as long as you are careful to recurse when you encounter a list such as with ((12 13)). – Justin Ethier

3 Answers

4
votes

for a function that needs to work on an arbitrary nested list I find it easy to first write the flat list version (filter-odd in our case) and then edit it to produce the nested version (I will call it filter-odd*)

First for normal filter-odd

(define filter-odd
   (lambda (ls)
      (cond
        [(null? ls) '()]
        [(odd? (car ls)) (cons (car ls) (filter-odd (cdr ls)))]
        [else (filter-odd (cdr ls))])))

Now for filter-odd* (one right-hand side will be left as an exercise (though it seems like you know the answer from your question))

(define filter-odd*
   (lambda (ls)
      (cond
        [(null? ls) '()]
        [(list? (car ls)) #| Do something with both car and cdr of ls |# ]
        [(odd? (car ls)) (cons (car ls) (filter-odd* (cdr ls)))]
        [else (filter-odd* (cdr ls))])))

As a note, this design pattern can be used to help write any recursive program and convert it from only working on flat lists to working on arbitrarily deep lists.

1
votes

Here's a general solution, for lists with an arbitrary level of nesting:

(define (odds-list lst)
  (cond ((null? lst) '())                 ; the list is empty
        ((not (list? (car lst)))          ; first element is not a list
         (if (odd? (car lst))             ; element is odd
             (cons (car lst) (odds-list (cdr lst))) ; build the returned list
             (odds-list (cdr lst))))      ; element is even
        (else (cons (odds-list (car lst)) ; first element is a list
                    (odds-list (cdr lst))))))

Notice that three cases need to be considered:

  1. If the list is empty
  2. If the first element of the list is not a list
  3. If the first element of the list is a list

For the second case, two further cases need to be considered:

  1. If the element is odd, then we add it to the list returned
  2. If the element is even, we skip it and continue with the next element
0
votes

Here's my take:

(define filter*
  (lambda (e f)
    (cond ((pair? e)
           (append (filter* (car e) f)
                   (filter* (cdr e) f)))
          ((null? e) '())
          ((f e) (list e))
          (else '()))))

and then you can do:

> (filter* '(1 (2 . 3) ((4 . 5))) even?)
(2 4)
> (filter* '(1 (2 . 3) ((4 . 5))) odd?)
(1 3 5)