Scheme / Racket Best Practice - Recursion vs Variable Accumulation

Question

I'm new to Scheme (via Racket) and (to a lesser extent) functional programming, and could use some advise on the pros and cons of accumulation via variables vs recursion. For the purposes of this example, I'm trying to calculate a moving average. So, for a list '(1 2 3 4 5), the 3 period moving average would be '(1 2 2 3 4). The idea is that any numbers before the period are not yet part of the calculation, and once we reach the period length in the set, we start averaging the subset of the list according the chosen period.

So, my first attempt looked something like this:

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

This works. And I like the use of map. It seems composible and open to refactoring. I could see in the future having cousins like:

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

etc.

But, it's not in the spirit of Scheme (right?) because I'm accumulating with side effects. So I rewrote it to look like this:

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

Now, this version is more difficult to grok at first glance. So I have a couple questions:

1. Is there a more elegant way to express the recursive version using some of the built in iteration constructs of racket (like for/fold)? Is it even tail recursive as written?

2. Is there any way to write the first version without the use of an accumulator variable?

3. Is this type of problem part of a larger pattern for which there are accepted best practices, especially in Scheme?

Answer 1

It's a little strange to me that you're starting before the first of the list but stopping sharply at the end of it. That is, you're taking the first element by itself and the first two elements by themselves, but you don't do the same for the last element or the last two elements.

That's somewhat orthogonal to the solution for the problem. I don't think the accumulator is making your life any easier here, and I would write the solution without it:

#lang racket

(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

Well, as a general rule, you want to separate the manner in which you recurse and/or iterate from the content of the iteration steps. You mention fold in your question, and this points in the right step: you want some form of higher-order function that will handle the list traversal mechanics, and call a function you supply with the values in the window.

I cooked this up in three minutes; it's probably wrong in many ways, but it should give you an 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

Alternately, you could define a function that converts a list into n-element windows and then map average over the windows.

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

Also notice that the partition function is tail-recursive, so it doesn't eat up stack space -- this is the point of result and the reverse call. I explicitly keep track of the length of the list to avoid either repeatedly calling length (which would lead to O(N^2) runtime) or hacking together a at-least-size-3 function. If you don't care about tail recursion, the following variant of partition should work:

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

Final comment - using '() as the default value for an empty list could be dangerous if you don't explicitly check for it. If your numbers are greater than 0, 0 (or -1) would probably work better as a default value - they won't kill whatever code is using the value, but are easy to check for and can't appear as a legitimate average