Scheme/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 (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)

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

1. 是否有更优雅的方式来表达递归版本使用一些内置的球拍迭代结构(如for/fold)？这甚至是书面的尾递归吗？

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

3. 这类问题是否是可接受的最佳实践的更大模式的一部分,尤其是在Scheme中？

Answer 1

我有点奇怪,你是在列表的第一个之前开始,但在它结束时急剧停止.也就是说,你自己拿第一个元素和前两个元素,但你不会对最后一个元素或最后两个元素做同样的事情.

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

#lang球拍

(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))