doc fold, reduce

[Kevin Ryde]

New words for fold and reduce.  I found the kons/knil names unclear,
and e12/e21 bits very hard to tell which order calls were made.  And
how fold and reduce differed was also pretty subtle.



 -- Scheme Procedure: fold proc init lst1 ... lstN
 -- Scheme Procedure: fold-right proc init lst1 ... lstN
     Apply PROC to the elements of LST1 ... LSTN to build a result, and
     return that result.

     Each PROC call is `(PROC ELEM1 ...  ELEMN PREVIOUS)', where ELEM1
     is from LST1, through ELEMN from LSTN.  PREVIOUS is the return
     from the previous call to PROC, or the given INIT for the first
     call.  If any list is empty, just INIT is returned.

     `fold' works through the list elements from first to last.  The
     following shows a list reversal and the calls it makes,

          (fold cons '() '(1 2 3))

          (cons 1 '())
          (cons 2 '(1))
          (cons 3 '(2 1)
          => (3 2 1)

     `fold-right' works through the list elements from last to first,
     ie. from the right.  So for example the following finds the longest
     string, and the last among equal longest,

          (fold-right (lambda (str prev)
                        (if (> (string-length str) (string-length prev))
                            str
                            prev))
                      ""
                      '("x" "abc" "xyz" "jk"))
          => "xyz"

     If LST1 through LSTN have different lengths, `fold' stops when the
     end of the shortest is reached; `fold-right' commences at the last
     element of the shortest.  Ie. elements past the length of the
     shortest are ignored in the other LSTs.  At least one LST must be
     non-circular.

     `fold' should be preferred over `fold-right' if the order of
     processing doesn't matter, or can be arranged either way, since
     `fold' is a little more efficient.

     The way `fold' builds a result from iterating is quite general, it
     can do more than other iterations like say `map' or `filter'.  The
     following for example removes adjacent duplicate elements from a
     list,

          (define (delete-adjacent-duplicates lst)
            (fold-right (lambda (elem ret)
                          (if (equal? elem (first ret))
                              ret
                              (cons elem ret)))
                        (list (last lst))
                        lst))
          (delete-adjacent-duplicates '(1 2 3 3 4 4 4 5))
          => (1 2 3 4 5)

     Clearly the same sort of thing can be done with a `for-each' and a
     variable in which build the result, but a self-contained PROC can
     be re-used in multiple contexts, where a `for-each' would have to
     be written out each time.

 -- Scheme Procedure: pair-fold proc init lst1 ... lstN
 -- Scheme Procedure: pair-fold-right proc init lst1 ... lstN
     The same as `fold' and `fold-right', but apply PROC to the pairs
     of the lists instead of the list elements.

 -- Scheme Procedure: reduce proc identity lst
 -- Scheme Procedure: reduce-right proc identity lst
     `reduce' is a variant of `fold' (see above), designed for cases
     where the initial value is an "identity", so that PROC can start
     directly from the first element of LST.

     Consider folding with `+' and initial value 0, calls would be for
     instance

          (fold + 0 '(4 5 6))
          =>
          (+ 4 0)
          (+ 5 4)
          (+ 6 9)

     The first call `(+ 4 0)' is unnecessary, adding 0 to 4 doesn't
     change that value.  The first element `4' may as well be the
     initial "previous" value argument to PROC.  This is what `reduce'
     does.

          (reduce + 0 '(4 5 6))
          =>
          (+ 5 4)
          (+ 6 9)

     The IDENTITY parameter is the return when LST is empty, that's the
     only time IDENTITY is used.  If LST has just one element, that's
     the return with no calls to PROC.

     `reduce-right' is a similar variation on `fold-right', working
     from the end (ie. the right) of LST.  Calls in this case become

          (reduce-right + 0 '(4 5 6))
          =>
          (+ 5 6)
          (+ 4 11)

     `reduce' should be preferred over `reduce-right' if the order of
     processing doesn't matter, or can be arranged either way, since
     `reduce' is a little more efficient.

     In the above examples of course `+' takes any number of arguments,
     so it can be used on a list just with `apply'.  An example where
     that's not the case would be SRFI-19 `add-duration' (*note SRFI-19
     Time::) on a list of durations,

          (use-modules (srfi srfi-19))
          (reduce add-duration
                  (make-time time-duration 0 0)
                  (list (make-time time-duration 0 4)
                        (make-time time-duration 0 5)
                        (make-time time-duration 0 6)))
          => #<time duration 15 seconds>