Scheme 中列表的非递减列表？
Non-decreasing list of lists in Scheme?
我们需要一个名为 nondecreaselist 的 Scheme 函数，它接收一个数字列表并输出一个列表列表，这些列表总体上具有相同顺序的相同数字，但分组为非减少。
例如，如果我们输入(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1)，输出应该是：
((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))
您将如何实施？我知道我们必须使用递归。
我目前的尝试：
(define (nondecreaselist s)
(cond ((null? s) '())
((cons (cons (car s)
((if (and (not (null? (cadr s)))
(not (> (car s) (cadr s))))
((cadr s))
('()))))
(nondecreaselist (cdr s))))))
但是，这给了我错误：
(int) is not callable:
发布的代码存在一些问题。第二个 cond 子句中没有测试表达式； if 及其子句周围的括号太多。也许最重要的问题是代码试图构建一个非递减列表，它将 consed 到 (nondecreaselist (cdr s)) 的结果，但是当非递减序列不止一个时number long 通过一直返回到 (cdr s).
，这在输入列表中再次开始太早了
修复 OP 代码
可以清理逻辑。当输入是一个空列表时，OP 代码已经是 return 一个空列表。除了测试 (null? (cadr s))（当 (cdr s) 为 '()，cadr 对 s 不起作用），可以在代码尝试之前测试 (null? (cdr s))一个(cadr s)。但是移动这个逻辑更好；当输入列表包含一个元素时，只是 return 一个包含输入列表的列表：((null? (cdr s)) (list s)).
而不是 (and (not (> ;... 通过测试 > 并执行适当的操作可以使逻辑更加清晰。在这种情况下，当 (> (car s) (cadr s)) 应该启动一个新的子列表时，cons 编辑到子列表列表中，即 return 从 nondecreaselist 编辑的结果。
否则，(car s) 应添加到 nondecreaselist 的结果 return 的第一个子列表中。为此，我们需要通过 consing s 到第一个子列表，然后 consing 那个新子列表回到 [=36= 来构建 return 列表] 的子列表列表是 return 从 nondecreaselist 编辑的结果。
修改后的代码如下：
(define (nondecreaselist s)
(cond ((null? s) '())
((null? (cdr s)) (list s))
((> (car s) (cadr s))
(cons (list (car s))
(nondecreaselist (cdr s))))
(else
(let ((next (nondecreaselist (cdr s))))
(cons (cons (car s)
(car next))
(cdr next))))))
使用辅助函数
另一种方法是定义一个辅助函数，该函数将输入列表和累积列表作为参数，return生成一个列表列表。辅助函数将从输入列表的前面获取数字并将它们添加到累加器，创建一个非递减列表，或者它将 cons 累积的非递减列表添加到对其余部分进行操作的结果输入的。
如果辅助函数 ndl-helper 的输入 lst 为空，则应 return 编辑包含累积非递减列表 sublst 的列表。请注意，sublst 需要在 returned 之前反转，因为它的构造方式如下所述。
如果累加器 sublst 为空，或者如果输入列表中的下一个数字大于或等于 sublst 中的最大数字，则下一个数字应该简单地添加到 sublst。通过 cons 将数字放到 sublst 的前面，只需要检查 sublst 的 car，因为它总是最大的（或等于最大的) sublst 中的值。但是，由于 sublst 的顺序是相反的，因此在将其添加到不断增长的列表列表之前需要将其反转。
否则，lst不为空，sublst不为空，输入列表中的下一个数小于sublst中的最大数。因此，需要启动一个新的子列表，因此旧的 sublst 被反转并 cons 通过调用剩余 lst 的辅助函数完成剩余计算的结果空累加器 sublst:
(define (nondecreaselist-2 lst)
(define (ndl-helper lst sublst)
(cond ((null? lst) (list (reverse sublst)))
((or (null? sublst)
(>= (car lst) (car sublst)))
(ndl-helper (cdr lst) (cons (car lst) sublst)))
(else
(cons (reverse sublst) (ndl-helper lst '())))))
(ndl-helper lst '()))
两个函数都有效：
> (nondecreaselist '(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1))
((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))
> (nondecreaselist-2 '(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1))
((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))
(define decrease-list
(lambda (l)
((lambda (s) (s s l cons))
(lambda (s l col)
;; limitcase1: ()
(if (null? l)
(col '() '())
;; limitcase2: (a1)
(if (null? (cdr l))
(col l '())
(let ((a1 (car l)) (a2 (cadr l)))
;; limitcase3: (a1 a2)
(if (null? (cddr l))
(if (>= a2 a1)
(col l '())
(col (list a1) (list (cdr l))))
;; most usual case: (a1 a2 ...)
(s s (cdr l)
(lambda (g l*)
(if (>= a2 a1)
(col (cons a1 g) l*)
(col (list a1) (cons g l*)))))))))))))
1 ]=> (decrease-list '(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1))
;Value: ((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))
我没有评论它，如果你有问题可以问，但我想你也可以自己研究我现在给你写的代码。
另请注意，可以将极限情况 () 和 (a1) 排除在循环之外并仅检查一次这些情况：
(define decrease-list
(lambda (l)
;; limitcase1: ()
(if (null? l)
'()
;; limitcase2: (a1)
(if (null? (cdr l))
(list l)
((lambda (s) (s s l cons))
(lambda (s l col)
(let ((a1 (car l)) (a2 (cadr l)))
;; limitcase3: (a1 a2)
(if (null? (cddr l))
(if (>= a2 a1)
(col l '())
(col (list a1) (list (cdr l))))
;; most usual case: (a1 a2 ...)
(s s (cdr l)
(lambda (g l*)
(if (>= a2 a1)
(col (cons a1 g) l*)
(col (list a1) (cons g l*)))))))))))))
我们需要一个名为 nondecreaselist 的 Scheme 函数，它接收一个数字列表并输出一个列表列表，这些列表总体上具有相同顺序的相同数字，但分组为非减少。
例如，如果我们输入(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1)，输出应该是：
((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))
您将如何实施？我知道我们必须使用递归。 我目前的尝试：
(define (nondecreaselist s)
(cond ((null? s) '())
((cons (cons (car s)
((if (and (not (null? (cadr s)))
(not (> (car s) (cadr s))))
((cadr s))
('()))))
(nondecreaselist (cdr s))))))
但是，这给了我错误：
(int) is not callable:
发布的代码存在一些问题。第二个 cond 子句中没有测试表达式； if 及其子句周围的括号太多。也许最重要的问题是代码试图构建一个非递减列表，它将 consed 到 (nondecreaselist (cdr s)) 的结果，但是当非递减序列不止一个时number long 通过一直返回到 (cdr s).
修复 OP 代码
可以清理逻辑。当输入是一个空列表时，OP 代码已经是 return 一个空列表。除了测试 (null? (cadr s))（当 (cdr s) 为 '()，cadr 对 s 不起作用），可以在代码尝试之前测试 (null? (cdr s))一个(cadr s)。但是移动这个逻辑更好；当输入列表包含一个元素时，只是 return 一个包含输入列表的列表：((null? (cdr s)) (list s)).
而不是 (and (not (> ;... 通过测试 > 并执行适当的操作可以使逻辑更加清晰。在这种情况下，当 (> (car s) (cadr s)) 应该启动一个新的子列表时，cons 编辑到子列表列表中，即 return 从 nondecreaselist 编辑的结果。
否则，(car s) 应添加到 nondecreaselist 的结果 return 的第一个子列表中。为此，我们需要通过 consing s 到第一个子列表，然后 consing 那个新子列表回到 [=36= 来构建 return 列表] 的子列表列表是 return 从 nondecreaselist 编辑的结果。
修改后的代码如下：
(define (nondecreaselist s)
(cond ((null? s) '())
((null? (cdr s)) (list s))
((> (car s) (cadr s))
(cons (list (car s))
(nondecreaselist (cdr s))))
(else
(let ((next (nondecreaselist (cdr s))))
(cons (cons (car s)
(car next))
(cdr next))))))
使用辅助函数
另一种方法是定义一个辅助函数，该函数将输入列表和累积列表作为参数，return生成一个列表列表。辅助函数将从输入列表的前面获取数字并将它们添加到累加器，创建一个非递减列表，或者它将 cons 累积的非递减列表添加到对其余部分进行操作的结果输入的。
如果辅助函数 ndl-helper 的输入 lst 为空，则应 return 编辑包含累积非递减列表 sublst 的列表。请注意，sublst 需要在 returned 之前反转，因为它的构造方式如下所述。
如果累加器 sublst 为空，或者如果输入列表中的下一个数字大于或等于 sublst 中的最大数字，则下一个数字应该简单地添加到 sublst。通过 cons 将数字放到 sublst 的前面，只需要检查 sublst 的 car，因为它总是最大的（或等于最大的) sublst 中的值。但是，由于 sublst 的顺序是相反的，因此在将其添加到不断增长的列表列表之前需要将其反转。
否则，lst不为空，sublst不为空，输入列表中的下一个数小于sublst中的最大数。因此，需要启动一个新的子列表，因此旧的 sublst 被反转并 cons 通过调用剩余 lst 的辅助函数完成剩余计算的结果空累加器 sublst:
(define (nondecreaselist-2 lst)
(define (ndl-helper lst sublst)
(cond ((null? lst) (list (reverse sublst)))
((or (null? sublst)
(>= (car lst) (car sublst)))
(ndl-helper (cdr lst) (cons (car lst) sublst)))
(else
(cons (reverse sublst) (ndl-helper lst '())))))
(ndl-helper lst '()))
两个函数都有效：
> (nondecreaselist '(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1))
((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))
> (nondecreaselist-2 '(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1))
((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))
(define decrease-list
(lambda (l)
((lambda (s) (s s l cons))
(lambda (s l col)
;; limitcase1: ()
(if (null? l)
(col '() '())
;; limitcase2: (a1)
(if (null? (cdr l))
(col l '())
(let ((a1 (car l)) (a2 (cadr l)))
;; limitcase3: (a1 a2)
(if (null? (cddr l))
(if (>= a2 a1)
(col l '())
(col (list a1) (list (cdr l))))
;; most usual case: (a1 a2 ...)
(s s (cdr l)
(lambda (g l*)
(if (>= a2 a1)
(col (cons a1 g) l*)
(col (list a1) (cons g l*)))))))))))))
1 ]=> (decrease-list '(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1))
;Value: ((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))
我没有评论它，如果你有问题可以问，但我想你也可以自己研究我现在给你写的代码。
另请注意，可以将极限情况 () 和 (a1) 排除在循环之外并仅检查一次这些情况：
(define decrease-list
(lambda (l)
;; limitcase1: ()
(if (null? l)
'()
;; limitcase2: (a1)
(if (null? (cdr l))
(list l)
((lambda (s) (s s l cons))
(lambda (s l col)
(let ((a1 (car l)) (a2 (cadr l)))
;; limitcase3: (a1 a2)
(if (null? (cddr l))
(if (>= a2 a1)
(col l '())
(col (list a1) (list (cdr l))))
;; most usual case: (a1 a2 ...)
(s s (cdr l)
(lambda (g l*)
(if (>= a2 a1)
(col (cons a1 g) l*)
(col (list a1) (cons g l*)))))))))))))