计划/球拍最佳实践 - 递归vs可变积累

Question

我是Scheme（通过球拍）和（在较小程度上）函数式编程的新手，并且可以通过变量vs递归在积累的优缺点上使用一些建议。为了这个例子的目的，我试图计算一个移动平均数。所以，对于名单'(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. 有表达使用一些内置的球拍的迭代结构（如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)) 

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）可能会更好地作为默认值工作 - 它们不会杀死任何使用该值的代码，但易于检查并且不会显示为合法的平均值