chickadee » srfi-1 » reduce

reduce f ridentity listprocedure

reduce is a variant of fold.

RIDENTITY should be a "right identity" of the procedure F -- that is, for any value X acceptable to F,

(F X RIDENTITY) = X

reduce has the following definition:

If LIST = (), return RIDENTITY; Otherwise, return (fold F (car LIST) (cdr LIST)).

...in other words, we compute (fold F RIDENTITY LIST).

Note that RIDENTITY is used only in the empty-list case. You typically use reduce when applying F is expensive and you'd like to avoid the extra application incurred when fold applies F to the head of LIST and the identity value, redundantly producing the same value passed in to F. For example, if F involves searching a file directory or performing a database query, this can be significant. In general, however, fold is useful in many contexts where reduce is not (consider the examples given in the fold definition -- only one of the five folds uses a function with a right identity. The other four may not be performed with reduce).

Note: MIT Scheme and Haskell flip F's arg order for their reduce and fold functions.

;; Take the max of a list of non-negative integers.
(reduce max 0 nums) ; i.e., (apply max 0 nums)