Schema/racchetta Best Practice - Ricorsione contro accumulo variabile

Question

Sono nuovo a Scheme (via Racket) e (in misura minore) programmazione funzionale, e potrei usare qualche consiglio sui pro e contro dell'accumulo tramite variabili vs ricorsione. Ai fini di questo esempio, sto cercando di calcolare una media mobile. Pertanto, per un elenco '(1 2 3 4 5), la media mobile a 3 periodi sarebbe '(1 2 2 3 4). L'idea è che qualsiasi numero prima del periodo non faccia ancora parte del calcolo, e una volta raggiunta la lunghezza del periodo nell'insieme, iniziamo a calcolare la media del sottoinsieme dell'elenco in base al periodo scelto.

Quindi, il mio primo tentativo sembrava qualcosa di simile:

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

Questo funziona. E mi piace l'uso della mappa. Sembra compositivo e aperto al refactoring. Ho potuto vedere in futuro con i cugini come:

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

ecc

Ma, non è nello spirito di Scheme (giusto?) Perché sto accumulando con effetti collaterali. Così ho riscritto per assomigliare a questo:

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

Ora, questa versione è più difficile da Grok a prima vista. Così ho un paio di domande:

1. C'è un modo più elegante per esprimere la versione ricorsiva utilizzando alcuni del costruito in costrutti di iterazione di racket (come for/fold)? È anche coda ricorsiva come scritto?

2. C'è un modo per scrivere la prima versione senza l'uso di una variabile di accumulatore?

3. Questo tipo di problema fa parte di un modello più ampio per il quale esistono best practice accettate, in particolare in Scheme?

Answer 1

E 'un po' strano per me che si sta iniziando prima che il primo della lista, ma fermandosi bruscamente alla fine di esso. Cioè, stai prendendo il primo elemento da solo e i primi due elementi da soli, ma non fai lo stesso per l'ultimo elemento o gli ultimi due elementi.

Questo è in qualche modo ortogonale alla soluzione del problema. Non credo che l'accumulatore sta rendendo la vita più facile qui, e vorrei scrivere la soluzione senza di essa:

#lang racchetta

(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

Beh, come regola generale, si vuole separare il modo in cui si ricorre e/o si itera dal contenuto dei passaggi di iterazione. Hai menzionato fold nella tua domanda, e questo indica il passo corretto: vuoi una qualche forma di funzione di ordine superiore che gestirà la meccanica di attraversamento dell'elenco e chiama una funzione che fornisci con i valori nella finestra.

L'ho cucinato in tre minuti; è probabilmente sbagliato in molti modi, ma dovrebbe dare un'idea:

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

In alternativa, è possibile definire una funzione che converte un elenco nelle finestre di n elementi e quindi mappare media sopra le finestre.

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

Si noti inoltre che la funzione partition è ricorsiva in coda, in modo da non mangia lo spazio dello stack - questo è il punto di result e la chiamata reverse. In modo esplicito, tengo traccia della lunghezza dell'elenco per evitare di chiamare ripetutamente lo length (che porterebbe al runtime O (N^2) o l'hacking di una funzione at-least-size-3. Se non si cura di ricorsione in coda, la seguente variante di partition dovrebbe funzionare:

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

finale commento - usando '() come il valore predefinito per un elenco vuoto potrebbe essere pericoloso se non si controlla in modo esplicito per questo. Se i tuoi numeri sono maggiori di 0, 0 (o -1) probabilmente funzionerebbero meglio come valore predefinito - non uccideranno qualunque codice stia usando il valore, ma sono facili da controllare e non possono apparire come media legittima