計劃/球拍最佳實踐 - 遞歸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）可能會更好地作爲默認值工作 - 它們不會殺死任何使用該值的代碼，但易於檢查並且不會顯示爲合法的平均值