10

我是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 中？

4

3 回答 3

7

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

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

#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))
于 2012-02-01T05:35:15.753 回答
0

好吧，作为一般规则，您希望将递归和/或迭代的方式与迭代步骤的内容分开。你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)))
于 2012-02-01T23:21:37.310 回答
0

或者，您可以定义一个函数，将列表转换为 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）作为默认值可能会更好 - 它们不会杀死正在使用该值的任何代码，但易于检查并且不能显示为合法平均值

于 2012-02-02T04:18:47.763 回答