From 857dda93d112fdd5e776f5dce2bbfc8a51704b2a Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Mon, 27 Jan 2014 00:47:43 -0800 Subject: * lib.c (reduce_left, reduce_right): changing the behavior so that the initial value is optional. this creates the possibility that the effective list of operands is empty, in which case the function must support a call with no arguments, just like in the common lisp reduce. * txr.1: rewrote reduce-left and reduce-right documentation. --- ChangeLog | 10 +++++++++ lib.c | 25 +++++++++++++++++++++- txr.1 | 71 ++++++++++++++++++++++++++++++++++++++++++++------------------- 3 files changed, 84 insertions(+), 22 deletions(-) diff --git a/ChangeLog b/ChangeLog index 9a871517..0cfb1a06 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2014-01-27 Kaz Kylheku + + * lib.c (reduce_left, reduce_right): changing the behavior so that + the initial value is optional. this creates the possibility that + the effective list of operands is empty, in which case the function + must support a call with no arguments, just like in the common lisp + reduce. + + * txr.1: rewrote reduce-left and reduce-right documentation. + 2014-01-27 Kaz Kylheku * lib.c (obj_print, obj_pprint): Bugfix: there may be diff --git a/lib.c b/lib.c index ecabd77f..c83dde14 100644 --- a/lib.c +++ b/lib.c @@ -3542,6 +3542,12 @@ val reduce_left(val fun, val list, val init, val key) if (!key) key = identity_f; + if (!init && list) + init = pop(&list); + + if (!init && !list) + return funcall(fun); + for (; list; list = cdr(list)) init = funcall2(fun, init, funcall1(key, car(list))); @@ -3553,8 +3559,25 @@ val reduce_right(val fun, val list, val init, val key) if (!key) key = identity_f; - if (nullp(list)) + if (list) { + if (!init) { + if (!rest(list)) + return funcall1(key, first(list)); + if (!rest(rest(list))) + return funcall2(fun, funcall1(key, first(list)), + funcall1(key, second(list))); + /* fall through: no init, three or more items in list */ + } else { + if (!rest(list)) + return funcall2(fun, funcall1(key, first(list)), init); + /* fall through: init, and two or more items in list */ + } + } else if (init) { return init; + } else { + return funcall(fun); + } + return funcall2(fun, funcall1(key, car(list)), if3(cdr(list), reduce_right(fun, cdr(list), init, key), init)); diff --git a/txr.1 b/txr.1 index 43b08e3f..905e29ad 100644 --- a/txr.1 +++ b/txr.1 @@ -7107,39 +7107,64 @@ yields (1 2 3 4 5). In TXR Lisp, this usage can be simulated using .TP Syntax: - (reduce-left ) - (reduce-right ) + (reduce-left : ) + (reduce-right : ) .TP Description: -The reduce-left and reduce-right functions reduce lists of operands -specified in to a single value by the repeated application of -. +The reduce-left and reduce-right functions reduce lists of operands specified +by and to a single value by the repeated application of +. -First, both functions initialize an internal accumulator with . +An effective list of operands is formed by combining and +. If is specified and not nil, then +the items of are mapped to a new values through . +If an is supplied and not nil, then in the +case of reduce-left, the effective list of operands is formed by prepending + to . In the case of reduce-right, the effective +operand list is produced by appending to . -Under reduce-left, the list is processed left to right. If elements -remain to be processed, the is repeatedly called with two -arguments: the accumulator and the next element from the list. After each call, -the return value of the function replaces the accumulator. When no more items -remain, the accumulator is returned. +The production of the effective list can be expressed like this, +though this is not to be understood as the actual impelmentation: -Under reduce-right, the list is processed right to left. If elements -remain to be processed, the is repeatedly called with two -arguments: the next element from the list and the accumulator. After each call, -the return value of the function replaces the accumulator. When no more items -remain, the accumulator is returned. + ;; reduce-left + (let ((eff-list (append (if init-value (list init-value)) + [mapcar (or key-function identity) list]))) -The specifies how each element from the is converted -to an argument to . The value nil is equivalent to -(fun identity), which means that each list element is taken as the value itself. +In the reduce-right case, the arguments to append are reversed. +If the effective list of operands is empty, then is called +with no arguments at all, and its value is returned. This is the only +case in which is called with no arguments; in all +remaining cases, it is called with two arguments. + +If the effective list contains one item, then that item is returned. + +Otherwise, the effective list contains two or more items, and is decimated as +follows. + +Under reduce-left, the leftmost pair of operands is removed +from the list and passed as arguments to , in the same order +that they appear in the list, and the resulting value initializes an +accumulator. Then, for each remaining item in the list, is +invoked on two arguments: the current accumulator value, and the next element +from the list. After each call, the accumulator is updated with the return +value of . The final value of the accumulator is returned. + +Under reduce-right, the list is processed right to left. The rightmost +pair of elements in the effetive list is removed, and passed as arguments to +, in the same order that they appear in the list. The +resulting value initializes an accumulator. Then, for each remaining item in +the list, is invoked on two arguments: the +next element from the list, in right to left order, and the current +accumulator value. After each call, the accumulator is updated with the return +value of . The final value of the accumulator is returned. .TP Examples: - ;;; list is empty, so 1 is just returned: + ;;; effective list is (1) so 1 is returned (reduce-left (fun +) () 1 nil) -> 1 ;;; computes (- (- (- 0 1) 2) 3) @@ -7149,7 +7174,11 @@ Examples: (reduce-right (fun -) '(1 2 3) 0 nil) -> 2 ;;; computes (* 1 2 3) - (reduce-left (fun *) '((1) (2) (3)) 1 (fun first)) -> 6 + (reduce-left (fun *) '((1) (2) (3)) nil (fun first)) -> 6 + + ;;; computes 1 because the effective list is empty + ;;; and so * is called with no arguments, which yields 1. + (reduce-left (fun *) nil) .SS Function some, all and none -- cgit v1.2.3