stumped on list recursion

Question

I am having issues with recursions involving lists for my HW. The HW problem asks the following:

"a (pair a b) is a (make-pair x y) where x is type a and y is type b (define-struct pair (a b))

Write the function partition as described here:

partition : (a -> bool) (listof a) -> (pair (listof a) (listof a)) divide a list into two lists: - one list of the elements for which the test is true, and - a second list of the elements for which the test is false."

What I was trying to do is the following:

(define (partition test lst2)
  (cond
    [(null? lst2) null]
    [(boolean=? #f (first(map test lst2))) (remove (first lst2) lst2) (partition test (rest lst2)))]
    [else (cond (first lst2) (partition test (rest lst2)))]))

I realize that using the map function here is not the right way to to do it, but I do not really know how to keep the recursion for the 2nd case going (or the else case for that matter, since no matter what I do, it doesn't move forward). Once I get the cases for true, would I get the cases for false using not somewhere in the code? Or would I need to do something completely different? I have been stumped on this problem for a while and some guidance would be nice!

Do you know about filter (gnu.org/software/mit-scheme/documentation/mit-scheme-ref/…) yet? — Benjamin Kovach
I do know about filter, however when I use it, I get: (list true true true) and what I am trying to get is a list of the elements that are true. I tried that about an hour ago and I did not know how to make a list of the things that correspond to the true statement. — user3819900
Nevermind I figured it out. Thanks a lot for the help~ It is really appreciated! — user3819900
these Q&A entries are not only for you personally, but also for anyone who might read them later. You should edit your question and put your solution in there to help others with same problem. :) — Will Ness
@WillNess No, the solution shouldn't be put into the question, it should be added as an answer. There's nothing wrong with answering your own question or accepting that answer; it helps keep the number of unanswered questions down, and it lets other users know what the solution was (as you point out) in a way that's consistent with the rest of the site. — Joshua Taylor

Óscar López Óscar López · Accepted Answer · 2014-07-09T16:49:30

For future reference, Racket already implements a partition procedure that returns two list values. For example:

(partition even? '(1 2 3 4 5 6 7 8 9 10))

=> '(2 4 6 8 10)
   '(1 3 5 7 9)

If you're interested in an implementation from scratch, filter is your best bet, as has been suggested in the comments. This implementation will return a pair as defined in the question:

(define (my-partition pred lst)
  (make-pair (filter pred lst)
             (filter-not pred lst)))

stumped on list recursion

1 Answers