将列表排序为子列表
Sort list into sublists
我正在尝试创建一个程序来对列表进行排序，然后将列表的每个部分分组到单独的列表中，并将其输出到列表列表中。这是一个应该更清楚的检查：
> (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)) 部分有问题，因为如果没有 first of rest 就会报错，rest of rest 也一样。
此外，在 ISL+ 中，这必须是 没有任何助手的单通道函数。任何帮助都会很棒。
有没有办法使用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)).
我不会把它称为 排序 而是某种类型的分区。您正在尝试收集已根据谓词排序的最长连续元素序列。我知道你说过你必须将所有这些都捆绑到一个函数中，但是先将它写成单独的函数，然后将它们组合成一个函数可能更容易。
在解决这个问题时，将其分解为子任务可能会有所帮助。首先，在最高级别，当列表出现时，有一些升序元素的初始前缀，然后是其余元素。结果应该是第一个前缀的列表，然后是处理其余元素的结果。这给了我们这样的结构：
(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* 和与 **cons[=60= 相同的 list** ].还有一个函数的引用，ordered-prefix，我们还没有定义。它的任务是 return 一个包含两个值的列表；第一个是列表的有序前缀，第二个是该前缀之后的列表尾部。现在我们只需要写那个函数：
(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 在其他函数中绑定函数，例如：
(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 现在定义为 within 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) 相同。您可能应该更改它，但为了清楚起见，我想保留原样。
唯一的性能考虑是这不是尾递归，所以你使用了更多的堆栈space。要解决这个问题，您需要将递归转换为反向构建列表的形式，然后在到达 return 时将其反转。这就是我在原版中所做的（您仍然可以查看编辑历史记录），但对于看起来像是学术练习的东西来说可能有点过分了。
您想将列表分解为最长的数字升序序列。并在 ISL+ 中完成，一次性完成。
这是在逻辑编程伪代码（好吧，Prolog）中实现的：
runs([], [[] ]).
runs([A], [[A]]).
runs([A,B|C], R) :-
( A > B -> runs([B|C], S ), R=[[A ]|S]
; true -> runs([B|C],[D|S]), R=[[A|D]|S] ).
这在类似 Scheme 的伪代码（嗯，完整的 Racket）中做同样的事情：
(define (runs xs)
(match xs
((list ) '(()))
((list A) (list (list A)))
((list A B C ...)
(cond
((> A B)
(let ([S (runs (cons B C))])
(cons (list A) S)))
(else
(let ([d_s (runs (cons B C))])
(let ([D (car d_s)]
[S (cdr d_s)])
(cons (cons A D) S))))))))
剩下您要做的就是将其融入 ISL+ 语言。我不知道 + 代表什么，但在 "intermediate student with lambda" 语言中肯定会有一个 lambda 结构。这让我们可以将嵌套 let 的分阶段分配模拟为
( (lambda (d_s)
( (lambda (D S)
(cons (cons A D) S))
(car d_s)
(cdr d_s)))
(runs (cons B C)))
我正在尝试创建一个程序来对列表进行排序，然后将列表的每个部分分组到单独的列表中，并将其输出到列表列表中。这是一个应该更清楚的检查：
> (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)) 部分有问题，因为如果没有 first of rest 就会报错，rest of rest 也一样。
此外，在 ISL+ 中，这必须是 没有任何助手的单通道函数。任何帮助都会很棒。
有没有办法使用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)).
我不会把它称为 排序 而是某种类型的分区。您正在尝试收集已根据谓词排序的最长连续元素序列。我知道你说过你必须将所有这些都捆绑到一个函数中，但是先将它写成单独的函数，然后将它们组合成一个函数可能更容易。
在解决这个问题时，将其分解为子任务可能会有所帮助。首先，在最高级别，当列表出现时，有一些升序元素的初始前缀，然后是其余元素。结果应该是第一个前缀的列表，然后是处理其余元素的结果。这给了我们这样的结构：
(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* 和与 **cons[=60= 相同的 list** ].还有一个函数的引用，ordered-prefix，我们还没有定义。它的任务是 return 一个包含两个值的列表；第一个是列表的有序前缀，第二个是该前缀之后的列表尾部。现在我们只需要写那个函数：
(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 在其他函数中绑定函数，例如：
(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 现在定义为 within 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) 相同。您可能应该更改它，但为了清楚起见，我想保留原样。
唯一的性能考虑是这不是尾递归，所以你使用了更多的堆栈space。要解决这个问题，您需要将递归转换为反向构建列表的形式，然后在到达 return 时将其反转。这就是我在原版中所做的（您仍然可以查看编辑历史记录），但对于看起来像是学术练习的东西来说可能有点过分了。
您想将列表分解为最长的数字升序序列。并在 ISL+ 中完成，一次性完成。
这是在逻辑编程伪代码（好吧，Prolog）中实现的：
runs([], [[] ]).
runs([A], [[A]]).
runs([A,B|C], R) :-
( A > B -> runs([B|C], S ), R=[[A ]|S]
; true -> runs([B|C],[D|S]), R=[[A|D]|S] ).
这在类似 Scheme 的伪代码（嗯，完整的 Racket）中做同样的事情：
(define (runs xs)
(match xs
((list ) '(()))
((list A) (list (list A)))
((list A B C ...)
(cond
((> A B)
(let ([S (runs (cons B C))])
(cons (list A) S)))
(else
(let ([d_s (runs (cons B C))])
(let ([D (car d_s)]
[S (cdr d_s)])
(cons (cons A D) S))))))))
剩下您要做的就是将其融入 ISL+ 语言。我不知道 + 代表什么，但在 "intermediate student with lambda" 语言中肯定会有一个 lambda 结构。这让我们可以将嵌套 let 的分阶段分配模拟为
( (lambda (d_s)
( (lambda (D S)
(cons (cons A D) S))
(car d_s)
(cdr d_s)))
(runs (cons B C)))