当将数据透视表和列表作为输入给出时，如何让分区返回两个列表输出？

Question

我正在尝试使用带有两个参数（一个枢轴和一个列表）的分区在方案中进行快速排序实现。

如果我要跑步：

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

除了将数字作为函数参数传递的问题之外，您还有另一个大问题。您的

partition

函数返回两个值，但它是递归的，每次调用它时，您都不会捕获这两个值，这使得实际构建分区列表变得困难。

这里有几种方法可以做到这一点。我建议，第一个是尾递归，这要归功于名为 let 的 ，并且实际上仅使用 values

 作为其最终返回值。另一个演示了标准 

call-with-values

 函数来捕获递归调用返回的两个值。

还有一个测试工具演示了另一种捕获多个值的方法，即

SRFI-11 let-values

，它往往比 call-with-values

 更友好。还有 

SRFI-8 的 receive 作为此处未显示的另一种方式。

(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

？这是您的错误消息的来源。 

这里是对该类型错误及其可能来源的更详细解释。 代码中错误较多。

partition

返回两个值，但您的代码在调用自身时没有使用适当的步骤来接收更多值，例如。

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)