(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
rangesmust otherwise be a list, the code should test if
rangesis in fact a pair before taking the
;; 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
nulldoesn't mean it is therefore a
But in any case, if we abstract away the iterative list traversal, we don't need to bother ourselves about the minutae of taking
cdrand 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.
mapis great example, but
fold-leftis even more general than
mapalways produces a list of the same length as the input list.
fold-leftcan 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-leftdoesn't have to return a list, either.
(fold-left + 0 foo) ;; sum the elements of foo