Scheme/Lisp 中的迭代范围函数

Question

我想实现范围函数 (start, end, inc)，生成从开始到结束的所有自然数，增量为 inc。这是第一个版本：

(define (gen start end step)
  (if (>= start end)
  '()
  (cons start (gen (+ step start) end step))))

问题是，这不是尾递归。再试一次：

(define (gen-iter start end step acc)
  (if (>= start end)
    acc
    (gen-iter (+ step start) end step (cons start acc))))

但这会以相反的顺序生成一个列表:) 所以，是的，我可以用 O(n) 来反转它，并且很高兴，但我有点卡在这里，试图创建一个函数，该函数将从头到尾以正确的顺序构造一个列表， 而不是在每个列表上附加iteration，因为附加是昂贵的。也有内置的列表，不知道怎么操作。

Answer 1

并不总是那么容易看到，但 "reverse" 是这里的关键字。要使其迭代，您需要反向执行实际工作：

(define (my-range start end step)      
  (define (helper n acc)
    (if (= end n)
        (cons n acc)
        (helper (- n step) (cons n acc))))

  (define actual-end end) ; this needs improvement
  (helper actual-end '()))

就像在球拍中 range 你应该得到这些结果：

(my-range 1 10 1)  ; ==> (1 2 3 4 5 6 7 8 9)
(my-range 10 1 -1) ; ==> (10 9 8 7 6 5 4 3 2)

要得到这个正确的 actual-end 需要根据数学找到正确的值。

(my-range 1 10 2)  ; ==> (1 3 5 7 9)  (actual-end should be 9)
(my-range 10 1 -2) ; ==> (10 8 6 4 2) (actual-end should be 2)

我猜你可以使用 ceiling 过程和正常的数学过程来得到这个正确的。

Answer 2

正如 uselpa 在评论中所说，解决方案是在最后使用 reverse。扩展后，range 的 racket 实现与 reverseing 你的 gen-iter 函数的结果非常相似，除了一些你可能没有考虑过的情况。

range在racket中的实际实现使用(for/list ([i (in-range start end step)]) i)，但是那个扩展到的其实等同于

(reverse
 (for/fold ([fold-var null])
           ([i (in-range start end step)])
   (cons i fold-var)))

除了它使用 alt-reverse 函数而不是 reverse，并且它使用 for/fold/derived 来更好地报告错误。如果你扩展它，它在一些简化之后相当于这个（删除不必要的 let-values 包装器，错误检查等）

(reverse
 (let ([start start] [end end] [inc step])
   (let for-loop ([fold-var null] [pos start])
     (if (if (>= step 0)
             (< pos end)
             (> pos end))
         (let ([i pos])
           (let ([fold-var (cons i fold-var)])
             (for-loop
              fold-var
              (+ pos inc))))
         fold-var))))

那里的命名 let 等同于定义一个这样的辅助函数：（在替换一些 lets 并将辅助函数提升到 range 函数之外）

(define (range start end step)
  (reverse
   (range-reversed null start end step)))
(define (range-reversed fold-var pos end step)
  (if (if (>= step 0)
          (< pos end)
          (> pos end))
      (range-reversed
       (cons pos fold-var)
       (+ pos step)
       end
       step)
      fold-var))

这仍然与您的解决方案不同，因为您的解决方案假定 step 为正，而即使 step 为负，此解决方案也有效。如果 step 为正，则 if 条件将为 (< pos end) 而不是嵌套的 if.

它还在您使用 (>= pos end) 的地方使用 (< pos end)，但它也会切换 if 大小写。如果 (< x y) 与 (not (>= x y)) 相同，则这等同于您的解决方案，因为 (if (not a) b c) 等同于 (if a c b)。但是，至少有一种情况我能想到这是不正确的，其中 start 或 end 是 +nan.0。对于这种情况，racket 的 range 函数将 return 一个空列表，而您的解决方案将进入无限循环。

Scheme/Lisp 中的迭代范围函数

Iterative range function in Scheme/Lisp

lisp

scheme

range

racket