functional-programming - 如何判断一个序列是否在增加？

Question

这是一个更大任务的一个片段，但我真的很挣扎。scheme/lisp 的资源比 C、Java 和 Python 更有限。

如果我传入一个包含数字列表的 var list1，我如何判断该列表是否单调递增？

Answer 1

如果一个列表的元素少于两个，那么我们会说“是”。

如果一个列表有两个或更多元素，那么如果第一个大于第二个，我们会说“不”，否则在列表的尾部递归。

Answer 2

(define (monotonically-increasing? lst)
  (apply < lst))

或者，如果你想要单调不递减：

(define (monotonically-non-decreasing? lst)
  (apply <= lst))

是的，就这么简单。完全 O(n)，不需要手动递归。

奖金：为了更好的衡量标准：

(define (sum lst)
  (apply + lst))

:-P

Answer 3

如果效率不是问题，您可以这样做：

(equal? list1 (sort list1 <=))

这是一个O(n log n)解决方案，因为排序。对于最佳解决方案，只需将每个元素与下一个元素进行比较，并测试当前元素是否小于或等于下一个元素，注意最后一个元素（没有下一个元素）。这将产生一个O(n)解决方案。

这是需要做什么的总体思路，以功能性风格编写。仍然不是编写解决方案的最快方法，但至少它O(n)很短；您可以将其用作从头开始编写更简单解决方案的基础：

(define (increasing? lst)
  (andmap <=
          lst
          (append (cdr lst) '(+inf.0))))

上面检查每个数字lst是否小于或等于下一个数字。该andmap过程测试<=条件是否适用于两个列表中的所有元素对。第一个列表是作为参数传递的列表，第二个列表是同一个列表，但向右移动了一个位置，最后添加了正无穷值以在两个列表中保持相同的大小 - 它适用于最后一个元素，因为任何数字都将小于无穷大。例如，使用此列表：

(increasing? '(1 2 3))

上面的过程调用将检查(<= 1 2)and (<= 2 3)，(<= 3 +inf.0)因为所有条件都计算为#t整个过程返回#t。如果只有一个条件失败，整个过程就会返回#f。