recursion - 方案/ Racket 最佳实践 - 递归与变量累加

Question

我是 Scheme(通过 Racket)和(在较小程度上)函数式编程的新手，并且可以对通过变量与递归进行累积的利弊提出一些建议。出于本示例的目的，我正在尝试计算移动平均线。因此，对于列表 '(1 2 3 4 5) , 3 周期移动平均线为 '(1 2 2 3 4) .这个想法是周期之前的任何数字还不是计算的一部分，一旦我们达到集合中的周期长度，我们就开始根据所选周期对列表的子集进行平均。

所以，我的第一次尝试看起来像这样:

(define (avg lst)
  (cond
   [(null? lst) '()]
   [(/ (apply + lst) (length lst))]))

(define (make-averager period)
  (let ([prev '()])
    (lambda (i)
      (set! prev (cons i prev))
      (cond
       [(< (length prev) period) i]
       [else (avg (take prev period))]))))

(map (make-averager 3) '(1 2 3 4 5))

> '(1 2 2 3 4)

这有效。我喜欢使用 map 。它似乎是可组合的并且可以重构。我可以看到将来有像这样的堂兄弟:

(map (make-bollinger 5) '(1 2 3 4 5))
(map (make-std-deviation 2) '(1 2 3 4 5))

等等。

但是，这不符合 Scheme(对吗？)的精神，因为我正在积累副作用。所以我把它改写成这样:

(define (moving-average l period)
  (let loop ([l l] [acc '()])
    (if (null? l)
        l
        (let* ([acc (cons (car l) acc)]
               [next
                 (cond
                  [(< (length acc) period) (car acc)]
                  [else (avg (take acc period))])])
          (cons next (loop (cdr l) acc))))))

 (moving-average '(1 2 3 4 5) 3)
 > '(1 2 2 3 4)

现在，这个版本乍一看更难理解。所以我有几个问题:

有没有更优雅的方式来使用一些内置的 Racket 迭代结构来表达递归版本(比如 for/fold )？它甚至是写的尾递归吗？

有没有办法在不使用累加器变量的情况下编写第一个版本？

这种类型的问题是否属于有公认最佳实践的更大模式的一部分，尤其是在 Scheme 中？

Answer 1

我有点奇怪，你在列表的第一个之前开始，但在它的末尾突然停止。也就是说，您将单独获取第一个元素和单独获取前两个元素，但对最后一个元素或最后两个元素不执行相同操作。

这与问题的解决方案有些正交。我认为累加器不会让您的生活变得更轻松，我会在没有它的情况下编写解决方案:

#lang Racket

(require rackunit)

;; given a list of numbers and a period, 
;; return a list of the averages of all 
;; consecutive sequences of 'period' 
;; numbers taken from the list.
(define ((moving-average period) l)
  (cond [(< (length l) period) empty]
        [else (cons (mean (take l period)) 
                    ((moving-average period) (rest l)))]))

;; compute the mean of a list of numbers
(define (mean l)
  (/ (apply + l) (length l)))

(check-equal? (mean '(4 4 1)) 3)
(check-equal? ((moving-average 3) '(1 3 2 7 6)) '(2 4 5))