scheme - 将列表排序为子列表

Question

我正在尝试创建一个程序，对列表进行排序，然后将排序后的列表的每个部分分组到单独的列表中，并将其输出到列表列表中。这是一个检查，应该可以使它更清楚:

> (sort-lists > '())
empty

> (sort-lists < '(1 2 3))
(list (list 1 2 3))

> (sort-lists >= '(2 2 2 2))
(list (list 2 2 2 2))

> (sort-lists < '(5 4 3 2 1))
(list (list 5) (list 4) (list 3) (list 2) (list 1))

> (sort-lists < '(1 2 3 4 2 3 4 5 6 1 2 9 8 7))
(list
 (list 1 2 3 4)
 (list 2 3 4 5 6)
 (list 1 2 9)
 (list 8)
 (list 7))

这是我所拥有的:

(define (sort-lists rel? ls)
  (cond
    [(empty? ls) '()]
    [(rel? (first ls) (first (rest ls)))
     (list (cons (first ls) (sort-lists rel? (rest ls))))]
    [else (cons (first ls) (sort-lists rel? (rest (rest ls))))]))

我对 (first (rest ls)) 部分有问题，因为如果没有第一个休息，那么它会给出错误，与其余的休息相同。

此外，这必须是 ISL+ 中的单 channel 函数，没有任何帮助程序。任何帮助都会很棒。

有没有办法用local将递归子问题的解合并到一个ans变量中，然后完成答案。所以对于(sort-lists < '(1 2 3 4 2 3 4 5 6 1 2 9 8 7)) ，您可以将 ans 定义为运行 (sort-lists < '(2 3 4 2 3 4 5 6 1 2 9 8 7)) 的结果，即'((2 3 4) (2 3 4 5 6) (1 2 9) (8) (7)).

Answer 1

我不会真正将其称为“排序”，而是某种类型的分区。您正在尝试收集已根据谓词排序的最长连续元素序列。我知道您说过必须将所有这些都捆绑到一个函数中，但是首先将其编写为单独的函数，然后将它们组合成一个函数可能要容易得多。

在解决这个问题时，将其分解为子任务可能会有所帮助。首先，在最高级别，当列表进入时，有一些升序元素的初始前缀，然后是其余元素。结果应该是第一个前缀的列表，然后是处理其余元素的结果。这给了我们这样的结构:

(define (slice predicate lst)
  (if (empty? lst)
      ;; If lst is empty, then there no contiguous 
      ;; subsequences within it, so we return '() 
      ;; immediately.
      '()
      ;; Otherwise, there are elements in lst, and we 
      ;; know that there is definitely a prefix and
      ;; a tail, although the tail may be empty. Then
      ;; the result is a list containing the prefix,
      ;; and whatever the sliced rest of the list is.
      (let* ((prefix/tail (ordered-prefix predicate lst))
             (prefix (first prefix/tail))
             (tail (second prefix/tail)))
        (list* prefix (slice predicate tail)))))

我希望该函数中的逻辑是相对清晰的。唯一可能有点不寻常的位是 let*(执行顺序绑定(bind))和 list**(与 **cons 相同)。还有一个对函数 ordered-prefix 的引用，我们尚未定义它。它的任务是返回两个值的列表；第一个是列表的有序前缀，第二个是该前缀之后的列表尾部。现在我们只需要编写该函数:

(define (ordered-prefix predicate lst)
  (cond
    ;; If the list is empty, then there's no prefix,
    ;; and the tail is empty too.
    ((empty? lst)
     '(() ()))
    ;; If the list has only one element (its `rest` is
    ;; empty, then the prefix is just that element, and 
    ;; the tail is empty.
    ((empty? (rest lst))
     (list (list (first lst)) '()))
    ;; Otherwise, there are at least two elements, and the
    ;; list looks like (x y zs...).
    (else 
     (let ((x (first lst))
           (y (second lst))
           (zs (rest (rest lst))))
       (cond
         ;; If x is not less than y, then the prefix is (x),
         ;; and the tail is (y zs...).
         ((not (predicate x y))
          (list (list x) (list* y zs)))
         ;; If x is less than y, then x is in the prefix, and the 
         ;; rest of the prefix is the prefix of (y zs...).  
         (else 
          (let* ((prefix/tail (ordered-prefix predicate (list* y zs)))
                 (prefix (first prefix/tail))
                 (tail (second prefix/tail)))
            (list (list* x prefix) tail))))))))

现在，这足以使 slice 工作:

(slice < '())                ;=> ()
(slice < '(1 2 3 4 2 3 4 5)) ;=> ((1 2 3 4) (2 3 4 5))

不过，它并不是全部集中在一个函数中。为此，您需要将 ordered-prefix 的定义添加到 slice 的定义中。您可以使用 let 在其他函数中绑定(bind)函数，例如:

(define (repeat-reverse lst)
  (let ((repeat (lambda (x)
                  (list x x))))
    (repeat (reverse lst))))

(repeat-reverse '(1 2 3)) ;=> ((3 2 1) (3 2 1))

但是，这不适用于 ordered-prefix，因为 ordered-prefix 是递归的；它需要能够引用自身。不过，您可以使用 letrec 来做到这一点，它允许函数引用自身。例如:

(define (repeat-n-reverse lst n)
  (letrec ((repeat-n (lambda (x n)
                       (if (= n 0) 
                           '()
                           (list* x (repeat-n x (- n 1)))))))
    (repeat-n (reverse lst) n)))

(repeat-n-reverse '(1 2 3) 3)     ;=> ((3 2 1) (3 2 1) (3 2 1))
(repeat-n-reverse '(x y) 2)       ;=> ((y x) (y x))
(repeat-n-reverse '(a b c d e) 0) ;=> ()

好的，现在我们已经准备好将它们放在一起了。 (由于 ordered-prefix 现在是在 slice 内定义的，因此它已经可以访问谓词，我们可以将其从参数列表中删除，但仍然使用它。)

(define (slice predicate lst)
  (letrec ((ordered-prefix
            (lambda (lst)
              (cond
                ((empty? lst)
                 '(() ()))
                ((empty? (rest lst))
                 (list (list (first lst)) '()))
                (else 
                 (let ((x (first lst))
                       (y (second lst))
                       (zs (rest (rest lst))))
                   (cond
                     ((not (predicate x y))
                      (list (list x) (list* y zs)))
                     (else 
                      (let* ((prefix/tail (ordered-prefix (list* y zs)))
                             (prefix (first prefix/tail))
                             (tail (second prefix/tail)))
                        (list (list* x prefix) tail))))))))))
    (if (empty? lst)
        '()
        (let* ((prefix/tail (ordered-prefix lst))
               (prefix (first prefix/tail))
               (tail (second prefix/tail)))
          (list* prefix (slice predicate tail))))))

这也是相对有效的。它不会分配任何不必要的数据，除了为清楚起见而使用 (list* y zs) 的地方，该值与 (rest lst) 相同。您可能应该更改它，但为了清楚起见，我想将其保留原样。

唯一的性能考虑是这不是尾递归，因此您使用了更多的堆栈空间。为了解决这个问题，您需要将递归转换为反向构建列表的形式，然后在返回列表时将其反转。这就是我在原版中所做的(您仍然可以查看编辑历史记录)，但这对于看似学术的练习来说可能有点过分了。