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

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

CodePudding user response：

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)

CodePudding user response：

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))