How do I get the partition to return two list output when pivot and the list are given as inputs?

Question

I'm trying to do a quicksort implementation in scheme using a partition that takes two arguement, a pivot and a list.

If I were to run:

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

I want the output to be:

=>;Value: ((2 1) (3 5 7 8 6 4))

I'm using this code:

(define (partition lt? lst)
 (if (null? lst)
     (values '() '())
     (let ((rest (cdr lst)))
       (if (lt? (car lst) (car rest))
           (let ((left (partition lt? rest)))
             (values (cons (car lst) (car left))
                     (cdr left)))
           (let ((right (partition lt? rest)))
             (values (car right)
                     (cons (car lst) (cdr right)))))))

It gives the following error: Output

Include the error in the body of your question, *as text*, not an image. — Shawn, Jun 03 '22 at 05:07
But I bet it has something to do with you passing a number as an argument that's used as a function — Shawn, Jun 03 '22 at 05:08

score 1 · Answer 1 · answered Jun 03 '22 at 12:21

Besides the problem with passing a number as an argument that's expected to be a function, you have another big issue too. Your partition function returns two values, but it's recursive and every time you call it, you're not capturing both of them, making it hard to actually build up the partitioned lists.

Here's a couple of ways to do it. The first, which I would suggest, is tail recursive thanks to a named let and only actually uses values for its final return value. The other one demonstrates the standard call-with-values function to capture both values returned by the recursive calls.

There's also a test harness that demonstrates another way to capture multiple values, the SRFI-11 let-values, which tends to be way more friendly than call-with-values. There's also SRFI-8's receive as yet another way not shown here.

(define (partition lt? what lst)
  (let loop ((lst lst)
             (lt '())
             (gte '()))
    (cond ((null? lst)
           (values (reverse lt) (reverse gte)))
          ((lt? (car lst) what)
           (loop (cdr lst) (cons (car lst) lt) gte))
          (else
           (loop (cdr lst) lt (cons (car lst) gte))))))

(define (partition2 lt? what lst)
  (if (null? lst)
      (values '() '())
      (call-with-values (lambda () (partition2 lt? what (cdr lst)))
        (lambda (lt gte)
          (if (lt? (car lst) what)
              (values (cons (car lst) lt) gte)
              (values lt (cons (car lst) gte)))))))

;;; Uses list= from SRFI-1 and let-values from SRFI-11 and format from SRFI-48
(define (test-partition op num lst expected-left expected-right)
  (let-values (((actual-left actual-right) (partition op num lst)))
    (format #t "(partition ~A ~S ~S) => ~S and ~S: " (if (eqv? op <) "<" ">") num lst
         actual-left actual-right)
    (if (or (not (list= = actual-left expected-left))
            (not (list= = actual-right expected-right)))
        (format #t "FAIL. Expected ~S and ~S instead.~%" expected-left expected-right)
        (format #t "PASS~%"))))

(test-partition > 3 '() '() '())
(test-partition > 3 '(1) '() '(1))
(test-partition < 3 '(1) '(1) '())
(test-partition < 3 '(4) '() '(4))
(test-partition < 3 '(1 4) '(1) '(4))
(test-partition < 3 '(1 2 4) '(1 2) '(4))
(test-partition < 3 '(1 3 4) '(1) '(3 4))

score 0 · Answer 2 · answered Jun 03 '22 at 10:11

Your definition of partition takes a procedure lt? and a list, but you are sending 3 as the procedure. You should perhaps have 3 arguments, lt?, pivot and lst? This is the source of your error message. Here is a more elaborate explanation of that type of error and its possible sources.

There are more errors in the code. partition returns two values, but your code does not use the appropriate steps to receive more values when calling itself, eg. let-values. Some of the code seems to expect a list with results instead of two results.

You should also start testing with the simplest cases. I would have done these first:

(partition > 3 '())      ; ==> (), ()
(partition > 3 '(1))     ; ==> (), (1)
(partition < 3 '(1))     ; ==> (1), ()
(partition < 3 '(4))     ; ==> (), (4)
(partition < 3 '(1 4))   ; ==> (1), (4)
(partition < 3 '(1 2 4)) ; ==> (1 2), (4)
(partition < 3 '(1 3 4)) ; ==> (1), (3 4)

score 0 · Accepted Answer · answered Jun 04 '22 at 20:39

0

I wrote this for you

(define (partition lt? pivot lst)
  ((lambda (s) (s s lst list))
   (lambda (s l* c)
     (if (null? l*)
         (c '() '())
         (let ((x (car l*)))
           (s s (cdr l*)
              (lambda (a b)
                (if (lt? x pivot)
                    (c (cons x a) b)
                    (c a (cons x b))))))))))

here is a test

1 ]=> (partition < '3 '(5 7 8 6 4 2 1))
;Value: ((2 1) (5 7 8 6 4))

answered Jun 04 '22 at 20:39

alinsoar

15,386
4
57
74

How can we implement this in a quicksort though? @alinsoar – user86365 Jun 05 '22 at 06:26
@user86365 You can find it well explained in the [course of Sedgewick](https://www.coursera.org/instructor/~250165) -- you can implement it from there. The idea is, you have a recursive procedure that splits the input in 2 smaller inputs (there are many ways you may select the pivot) and after you have 2 sets that were split by _`partition`_, you can merge them in constant time. – alinsoar Jun 05 '22 at 10:03

How do I get the partition to return two list output when pivot and the list are given as inputs?

3 Answers3

Linked