计划/球拍最佳实践-回归与可变积累

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

等。

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

(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. 是否有一种更优雅的方法来使用racket的内置迭代构造(如for/fold)来表示递归版本？它是否像所写的那样是尾递归的？
2. 是否有任何方法可以在不使用累加器变量的情况下编写第一个版本？
3. 是有公认的最佳实践的更大模式的一部分吗？

Answer 1

对我来说有点奇怪的是，你在第一个列表之前就开始了，但在它的末尾突然停止了。也就是说，第一个元素本身和前两个元素本身都是独立的，但是对于最后一个元素或最后两个元素，您不会做同样的事情。

这与问题的解决方案有些正交。我不认为累加器会让你的生活变得更轻松，我会写一个没有它的解决方案：

#朗球拍

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

Answer 2

作为一般规则，您希望将递归和/或迭代的方式与迭代步骤的内容分开。您在问题中提到了fold，这是正确的步骤:您需要某种形式的高阶函数来处理列表遍历机制，并调用您提供的带有窗口中的值的函数。

我花了三分钟就把它做好了；在很多方面它可能都是错误的，但是它应该给你一个想法：

;;;
;;; Traverse a list from left to right and call fn with the "windows"
;;; of the list.  fn will be called like this:
;;;
;;;     (fn prev cur next accum)
;;;
;;; where cur is the "current" element, prev and next are the
;;; predecessor and successor of cur, and accum either init or the
;;; accumulated result from the preceeding call to fn (like
;;; fold-left).
;;;
;;; The left-edge and right-edge arguments specify the values to use
;;; as the predecessor of the first element of the list and the
;;; successor of the last.
;;;
;;; If the list is empty, returns init.
;;;
(define (windowed-traversal fn left-end right-end init list)
  (if (null? list)
      init
      (windowed-traversal fn
                          (car list)
                          right-end
                          (fn left-end
                              (car list)
                              (if (null? (cdr list))
                                  right-end
                                  (second list))
                              init)
                          (cdr list))))

(define (moving-average list)
  (reverse!
   (windowed-traversal (lambda (prev cur next list-accum)
                         (cons (avg (filter true? (list prev cur next)))
                               list-accum))
                       #f
                       #f
                       '()
                       list)))

Answer 3

或者，您可以定义一个函数，将列表转换为n元素窗口，然后在窗口上映射平均值。

(define (partition lst default size)
  (define (iter lst len result)
    (if (< len 3)
      (reverse result)
      (iter (rest lst)
            (- len 1)
            (cons (take lst 3) result))))
  (iter (cons default (cons default lst))
        (+ (length lst) 2)
        empty))

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

(map avg (partition (list 1 2 3 4 5) 0 3))

还请注意，partition函数是尾递归的，因此它不会占用堆栈空间--这就是result和reverse调用的要点。我显式地跟踪列表的长度，以避免重复调用length (这将导致O(N^2)运行时)或将at-least-size-3函数合并在一起。如果您不关心尾递归，那么partition的以下变体应该可以工作：

(define (partition lst default size)
  (define (iter lst len)
    (if (< len 3)
      empty
      (cons (take lst 3)
            (iter (rest lst)
                  (- len 1)))))
  (iter (cons default (cons default lst))
        (+ (length lst) 2)))

最后的注释-使用'()作为空列表的默认值可能是危险的，如果您不显式地检查它。如果您的数字大于0，0(或-1)可能会更好地作为默认值-它们不会杀死任何使用该值的代码，但是很容易检查，并且不能显示为合法的平均值。