Schemat/Rakieta Najlepsze praktyki - Rekursja vs Zmienna akumulacja

Question

Jestem nowicjuszem w Schemacie (poprzez Rakietę) i (w mniejszym stopniu) programowaniu funkcjonalnym, i mogę skorzystać z porady dotyczącej plusów i minusów kumulacji poprzez zmienne a rekursja. Na potrzeby tego przykładu próbuję obliczyć średnią ruchomą. Tak więc, dla listy '(1 2 3 4 5), średnia z 3 okresów ruchomych wynosiłaby '(1 2 2 3 4). Chodzi o to, że żadne liczby przed okresem nie są jeszcze częścią obliczeń, a kiedy osiągniemy długość okresu w zbiorze, zaczniemy uśredniać podzbiór listy według wybranego okresu.

Więc moja pierwsza próba wyglądała mniej więcej tak:

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

To działa. Podoba mi się użycie mapy. Wydaje się, że jest kompozycyjny i otwarty na refaktoryzację. Widziałam w przyszłości o kuzynów, takich jak:

(map (make-bollinger 5) '(1 2 3 4 5)) 
(map (make-std-deviation 2) '(1 2 3 4 5)) 

itp

Ale to nie w duchu Scheme (prawda?), bo jestem z akumulacją efektów ubocznych. Więc przepisałem go tak, aby wyglądał tak:

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

Teraz ta wersja jest trudniejsza do zignorowania na pierwszy rzut oka. Więc mam kilka pytań:

1. Czy jest bardziej eleganckim sposobem wyrażenia rekurencyjną wersję korzystaniu z niektórych zbudowany w konstrukcji iteracji rakietę (jak for/fold)? Czy to jest rekursywne, nawet jak napisane?

2. Czy istnieje sposób na napisanie pierwszej wersji bez użycia zmiennej akumulatora?

3. Czy ten typ problemu jest częścią większego wzorca, dla którego akceptowane są najlepsze praktyki, szczególnie w Planie?

Answer 1

To trochę dziwne, że zaczynacie od pierwszej listy, ale na końcu przestajecie ostro. Oznacza to, że sam bierzesz pierwszy element i dwa pierwsze elementy, ale nie robisz tego samego dla ostatniego elementu lub dwóch ostatnich elementów.

To jest trochę prostopadłe do rozwiązania problemu. Nie sądzę akumulator czyni swoje życie łatwiejsze tutaj i chciałbym napisać rozwiązanie bez niego:

#lang rakietę

(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

dobrze, jako ogólną zasadę, chcesz oddzielić sposób, w jaki powtarzasz i/lub powtarzasz zawartość kroków iteracyjnych. W swoim pytaniu wspominasz o numerze fold, co oznacza, że ​​potrzebujesz pewnej formy funkcji wyższego rzędu, która obsłuży mechanikę przejścia na liście i wywoła funkcję, którą dostarczysz z wartościami w oknie.

Ugotowałem to w ciągu trzech minut; to chyba źle na wiele sposobów, ale powinno dać wyobrażenie:

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

Alternatywnie, można zdefiniować funkcję, która przekształca listę w Windows n-elementów, a następnie mapie Średnia nad oknami.

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

zauważyć również, że funkcja partition jest ogon rekurencyjnej, więc nie jeść przestrzeń stosu - jest to punkt result i wywołanie reverse. Dokładnie śledzę długość listy, aby uniknąć wielokrotnego wywoływania length (która prowadziłaby do środowiska wykonawczego O (N^2)) lub hakowania razem funkcji at-least-size-3. Jeśli nie dbają o rekursji ogonowej, następujący wariant partition powinno działać:

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

końcowa uwaga - za pomocą „() jako wartość domyślną dla pustej listy może być niebezpieczne, jeśli nie jawnie sprawdzić dla tego. Jeśli twoje liczby są większe niż 0, 0 (lub -1) prawdopodobnie działałoby lepiej jako wartość domyślna - nie zabiją tego, który kod używa wartości, ale są łatwe do sprawdzenia i nie mogą być wyświetlane jako prawidłowa średnia