当枢轴和列表作为输入时，我如何让分区返回两个列表输出?

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