Racket - Separate Even and Odd Numbers?

Question

I'm trying to build a function in Racket/Scheme, where you are given a list of integers, and then it has to sort them into two sublists, one for even numbers, and one for odd numbers. I'm very new to racket, and I have some of the basics down with manipulating lists, but I can't seen to figure out how to define two sublists and put numbers in each one.

This is what I have so far:

    (define (segregate lst)
      (if (empty? lst)
          '()
          (if (even? (car a lst))
              (append (car alst) (segregate (cdr alst))))

And from there I'm stuck. So with that if condition, even numbers will be sorted into one list. But I need the odd numbers too. The else statement in this condition will give you those odd numbers, but I have no idea how to get them into a separate list.

This is the first time I've actually asked a question on this site, because my professor is not in his office for some reason.

Answer 1

So, your function needs to return two lists, right? Your base case needs to return two empty lists, and then in your recursive cases, you fill in the relevant one depending. Here's some skeletal code (fill in the <???>):

(define (odds-and-evens lst)
  (if (null? lst)
      (values '() '())
      (let-values (((odds evens) (odds-and-evens (cdr lst))))
        (cond ((odd? (car lst)) (values (cons <???> <???>) <???>))
              ((even? (car lst)) (values <???> (cons <???> <???>)))
              (else (values odds evens))))))

Answer 2

Chris' let-values-version is spicy, but I would have written it like this to make it tail recursive:

(define (split left? lst)
  (let loop ((lst lst) (a '()) (b '()))
    (if (null? lst)
        ;; you don't need to use values. `cons` or `list` are sometimes preferred
        (values (reverse a) (reverse b)) 
        (let ((e (car lst)))
          (if (left? e)
              (loop (cdr <???>) (cons <???> <???>) <???>)
              (loop (cdr <???>) <???>  (cons <???> <???>)))))))

(split odd? '(1 2 3 4 ...)) 
; ==> 
; (1 3 ...)
; (2 4 ...)

Even though it traverses both lists twice (one to do the separation and one to do the reverse) it's still many times faster and IMO simpler to follow.

If you don't care about the order you just skip the reverse step and it will be even faster.

Answer 3

Above codes are confunsing as hell. Racket is a very simple language and it's intended to understand what the code is doing while you're reading it. You can use tail recursion for this problem.

You analyze the first element of A, put it where it should and then call the function again until A is empty.

(define segregate
  (lambda (A o e) ;A is the list of integers, o is the list of odds and e is for evens.
      (cond ((empty? A) (list o e))
            ((even? (car A)) (segregate (cdr A) o (append e (car A)))
            (else (segregate (cdr A) (append o (car A)) e))))) 

Answer 4

Another alternative would be to use foldr

(define (odd-even xs)
  (foldr (lambda (x b)
           (if (odd? x)
               (list (cons x (first b)) (second b))
               (list (first b) (cons x (second b))))) '(()()) xs))

racket@> (odd-even '(1 2 3 4 5 6 7))
'((1 3 5 7) (2 4 6))

Answer 5

Using built-in partition:

(define (segregate lst)
  (let-values ([(e o) (partition even? lst)])
    (list e o)))