当枢轴和列表作为输入给出时，如何使分区返回两个列表输出？

Question

我正在尝试使用一个分区在方案中进行QuickSort实现，该分区需要两个参数，一个枢轴和一个列表。

如果我要运行：

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

我希望输出是：

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

我正在使用此代码：

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

我会收到以下错误：

Answer 1

除了将数字作为一个预计将是一个函数的参数的问题外，您还遇到了另一个大问题。您的分区函数返回两个值，但是它是递归的，每次调用它时，您都不会捕获两个值，从而使实际构建分区列表很难。

这是几种做到这一点的方法。我建议的第一个是尾部递归的，这要归功于 nate ，并且仅实际使用value作为其最终返回值。另一个演示了标准call-with-with-with-with-code>函数，以捕获递归调用返回的两个值。

还有一个测试安全带，演示了捕获多个值的另一种方法， srfi-111 let-values ，它比call-with-with-values更友好。还有 srfi-8的在这里未显示的另一种方式。

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

Answer 2

我为你写了

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

这是一个测试

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

Answer 3

您对分区的定义采用一个过程lt？和一个列表，但是您将3作为过程发送。您应该有3个参数，lt？，pivot和lst？这是您的错误消息的来源。 这是对这种错误及其可能来源的更详细的解释。

代码中有更多错误。 分区返回两个值，但是您的代码不会使用适当的步骤来接收更多值，例如。 let-values。一些代码似乎期望有结果列表，而不是两个结果。

您还应该开始使用最简单的情况进行测试。我会首先做这些：

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