Thursday, July 23, 2009

What's wrong with this code? II

(let loop ((ranges (%char-set-ranges cs))
           (value 0))
      (if (null? ranges)
          value
          (loop (cdr ranges)
                (modulo (+ value (caar ranges) (cdar ranges)) 
                        bound))))
Again, the machinery of iterating down the list is woven into the code. And it is incorrect. Rather than testing for null? and assuming that ranges must otherwise be a list, the code should test if ranges is in fact a pair before taking the car or cdr.
;; Common, but incorrect:

  (if (null? foo)
      ... handle base case ...
      (let ((a (car foo)))
         ... handle recursive case ...
         ))

;; Correct:

    (cond ((pair? foo) (let ((a (car foo)))
                          ... handle recursive case ...
                          ))
          ((null? foo)  ... handle base case ...)
          (else (error "Improper list: " foo)))
The second way might be faster if the compiler is reasonably smart about type propagation. The compiler could note that once (pair? foo) is satisfied, then (car foo) does not need an additional type check. This is not the case with the first sample. Just because foo is not null doesn't mean it is therefore a pair.

But in any case, if we abstract away the iterative list traversal, we don't need to bother ourselves about the minutae of taking car and cdr and checking types:
(fold-left (lambda (value range)
             (modulo (+ value (car range) (cdr range))
                     bound))
           0
           (%char-set-ranges cs))
Here's another example:
(let loop ((syms (make-global-value-list))
           (result '()))
    (if (null? syms)
        result
        (let ((sym-str (symbol->string (caar syms))))
          (if (and (>= (string-length sym-str) (string-length string))
                   (string=? (substring sym-str 0 (string-length string))
                             string))
              (loop (cdr syms)
                    (cons (list (symbol->string (caar syms))) result))
              (loop (cdr syms) result)))))

(fold-left (lambda (result sym)
             (let ((sym-str (symbol->string (car sym))))
               (if (and (>= (string-length sym-str) (string-length string))
                        (string=? (substring sym-str 0 (string-length string))
                                   string))
                   (cons (list sym-str) result)
                   result)))
            '()
            (make-global-value-list))
We don't want to write code that iterates down a list. We want to write code that operates on a single element of a list and then use a higher-order function to make it work across the entire list. map is great example, but fold-left is even more general than map. map always produces a list of the same length as the input list. fold-left can add or remove elements:
;; Double the items in the list.
(fold-left (lambda (result item) 
             (cons item (cons item result)))
           '() foo)

;; Return a list of the lengths
;; of the non-empty strings.
(fold-left (lambda (result item)
             (let ((x (string-length item)))
               (if (zero? x)
                   result
                   (cons x result))))
           '()
            foo)
(Note that the returned list in each of these is in reverse order. That's ok, we can simply call reverse on the result if we want it in forward order. In most cases, a second traversal to reverse the result is about as cheap as trying to construct the list in forward order, and it is far less complicated.)

fold-left doesn't have to return a list, either.
(fold-left + 0 foo) ;; sum the elements of foo

No comments: