Racket ISL中仅使用foldr列表抽象实现total-pages函数

原实现先通过map遍历列表将每个页码范围对象转换为对应页数，再通过foldr遍历转换后的列表求和，会产生两次列表遍历，同时生成不必要的中间列表，性能更低。我们可以将元素转换的逻辑直接嵌入foldr的累加回调中，仅用一次遍历就完成计算。

实现代码 #

首先修正原代码中num-pages函数末尾括号不匹配的语法错误（原代码末尾误用了方括号]），改写后的两种等价实现如下：

;; 写法1：内联页数计算逻辑，无额外函数调用开销
(define (total-pages lorp)
  (foldr (lambda (current-range acc)
           (+ (+ 1
                 (- (page-end current-range)
                    (page-start current-range)))
              acc))
         0
         lorp))

如果你需要在其他地方复用单段范围的页数计算逻辑，可以保留独立的num-pages函数，在foldr回调中直接调用即可，依然是单次遍历，不会生成中间列表：

;; 写法2：保留可复用的num-pages函数
(define (num-pages rp)
  (+ 1
     (- (page-end rp)
        (page-start rp))))

(define (total-pages lorp)
  (foldr (lambda (current-range acc)
           (+ (num-pages current-range) acc))
         0
         lorp))

实现说明 #

foldr的回调函数接收两个参数：当前遍历到的列表元素、之前所有元素的累加结果。我们不需要先用map把所有元素转换成页数再求和，只需要在处理每个元素时，先算出当前元素对应的页数，直接和累加结果相加即可，省去了中间列表的构造开销和第二次遍历成本。

• 原实现时间复杂度为O(2n)，空间复杂度为O(n)（需要存储map生成的中间页数列表）
• 改写后实现时间复杂度为O(n)，空间复杂度为O(1)（不计递归栈开销），长列表场景下性能优势明显。

内容的提问来源于stack exchange，提问作者user19636979