Scheme Standard Deviation

Question

I'm trying to get a function that returns the standard deviation of a single list and my code runs great, but I want to learn how to use map, apply and filter to apply in this code. So far I have use apply on the average function, but I can't get my head around into using them in the rest of the code

(define (average li)
  (/ (apply + li) (length li)))

(define (summation li avg)
  (if (null? li)
    0
    (+  
       (* (- (car li) avg) 
          (- (car li) avg))
    (summation (cdr li) avg))))

(define (sd li)
    (sqrt
        (/  
          (summation li (average li))
          (- (length li) 1))))

I have a feeling that map can be use in the summation function, yet thing it will make a big mistake.

Mulan Mulan · Accepted Answer · 2018-04-17T23:14:31

You can express summation using foldl

(define (summation li avg)
  (foldl (lambda (x acc)
           (+ acc
              (expt (- x avg)
                    2)))
         0
         li))

While these procedures you supply here seem simple, you should be considering the consequences of their implementation. For example, I'm sure you could write your own length function

(define (length li)
  (if (null? li)
      0
      (+ 1 (length (cdr li)))))

You use (apply + li) to calculate a your input list's sum, but I'm sure you realize that's a clever replacement for our simple recursive solution

(define (sum li)
  (if (null? li)
      0
      (+ (car li)
         (sum (cdr li)))))

Given sum and length, we implement average

(define (average li)
  (/ (sum li)
     (length li)))

Do you see the problem here? sum and length both iterate through the input list. Then we go on to write sd...

(define (sd li)
  (sqrt (/ (summation li
                      (average li))
           (- (length li) 
              1))))

Do you see how the problem has worsened? We know average already steps through the input list li twice, summation steps through it again, and notice there's another call to length – we've iterated thru li 4 times before sd can return its result

Let's rewind a little bit. Looking at average, wouldn't it be nice if there was some way we could sum the elements of li and count them simultaneously? Well we can!

(define (average li (return /))
  (if (null? li)
      (return 0 0)
      (average (cdr li)
               (lambda (sum count)
                 (return (+ sum (car li))
                         (+ count 1))))))


(average '(1))     ;; 1
(average '(1 2))   ;; 1 1/2
(average '(1 2 3)) ;; 2
(average '())      ;; Error: division by zero

Using this technique, you can perform transformations of virtually any complexity. Writing sd using this style is left as an exercise for the reader.

Scheme Standard Deviation

1 Answers