From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Kevin Ryde Newsgroups: gmane.lisp.guile.devel Subject: doc fold, reduce Date: Sat, 12 Feb 2005 09:03:00 +1100 Message-ID: <87vf8yyctn.fsf@zip.com.au> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1108159669 31257 80.91.229.2 (11 Feb 2005 22:07:49 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Fri, 11 Feb 2005 22:07:49 +0000 (UTC) Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Feb 11 23:07:49 2005 Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1Cziwx-0000Oz-Qa for guile-devel@m.gmane.org; Fri, 11 Feb 2005 23:07:44 +0100 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1CzjBx-0003x7-Gi for guile-devel@m.gmane.org; Fri, 11 Feb 2005 17:23:13 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1CzjAt-0003o8-Vt for guile-devel@gnu.org; Fri, 11 Feb 2005 17:22:08 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1CzjAm-0003lW-E3 for guile-devel@gnu.org; Fri, 11 Feb 2005 17:22:02 -0500 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1CzjAm-0003jE-AC for guile-devel@gnu.org; Fri, 11 Feb 2005 17:22:00 -0500 Original-Received: from [61.8.0.85] (helo=mailout2.pacific.net.au) by monty-python.gnu.org with esmtp (Exim 4.34) id 1CzisV-0003Qz-57 for guile-devel@gnu.org; Fri, 11 Feb 2005 17:03:07 -0500 Original-Received: from mailproxy2.pacific.net.au (mailproxy2.pacific.net.au [61.8.0.87]) by mailout2.pacific.net.au (8.12.3/8.12.3/Debian-7.1) with ESMTP id j1BM34Hn015570 for ; Sat, 12 Feb 2005 09:03:04 +1100 Original-Received: from localhost (ppp2880.dyn.pacific.net.au [61.8.40.128]) by mailproxy2.pacific.net.au (8.12.3/8.12.3/Debian-7.1) with ESMTP id j1BM32Gf000549 for ; Sat, 12 Feb 2005 09:03:03 +1100 Original-Received: from gg by localhost with local (Exim 3.36 #1 (Debian)) id 1CzisO-0000ZT-00; Sat, 12 Feb 2005 09:03:00 +1100 Original-To: guile-devel@gnu.org Mail-Copies-To: never User-Agent: Gnus/5.110003 (No Gnus v0.3) Emacs/21.3 (gnu/linux) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org X-MailScanner-To: guile-devel@m.gmane.org Xref: main.gmane.org gmane.lisp.guile.devel:4772 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.devel:4772 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))) => #