reduce

[eddier]

Lutz,

Code: Select all

(define (gcd_ a b)
  (let (r (% b a))
    (if (= r 0) a (gcd_ r a))))

(define (reduce f L)
  (if (= (length L) 0) nil
      (= (length L) 1) (first L)
      (> (length L) 1) (reduce f (cons (apply f (slice L 0 2)) (slice L 2)))))

(define-macro (gcd)
  (reduce gcd_ (args)))

Could you add a reduce function to apply a binary operator over a list? Or, could you show me a better way of making a function that works on multiple arguments?

Eddie[/code]

[Lutz]

I am not sure if I understand. To apply a binary operator over a list:

(define (op arg1 arg2) ...)

(map op arg1-list arg2-list)


Or what do you mean?

Lutz

(map + '(1 2 3) '(10 20 30)) => (11 22 33)

[nigelbrown]

Map can apply a two or more parameter function to sequential members of two or more lists viz:

> (define (two_ops x y) (+ x y))
(lambda (x y) (+ x y))
> (map two_ops '(1 2 3) '(4 5 6))
(5 7 9)

but it doesn't look like that's what you are after?
Don't know if these help:
Maybe see http://www.delorie.com/gnu/docs/emacs/cl_47.html
that seems to suggest using an underlying looping macro:
...
Function: reduce function seq &key :from-end :start :end :initial-value :key
This function combines the elements of seq using an associative binary operation. Suppose function is * and seq is the list (2 3 4 5). The first two elements of the list are combined with (* 2 3) = 6; this is combined with the next element, (* 6 4) = 24, and that is combined with the final element: (* 24 5) = 120. Note that the * function happens to be self-reducing, so that (* 2 3 4 5) has the same effect as an explicit call to reduce.

If :from-end is true, the reduction is right-associative instead of left-associative:



(reduce '- '(1 2 3 4))
== (- (- (- 1 2) 3) 4) => -8
(reduce '- '(1 2 3 4) :from-end t)
== (- 1 (- 2 (- 3 4))) => -2

If :key is specified, it is a function of one argument which is called on each of the sequence elements in turn.

If :initial-value is specified, it is effectively added to the front (or rear in the case of :from-end) of the sequence. The :key function is not applied to the initial value.

If the sequence, including the initial value, has exactly one element then that element is returned without ever calling function. If the sequence is empty (and there is no initial value), then function is called with no arguments to obtain the return value.

All of these mapping operations can be expressed conveniently in terms of the loop macro. In compiled code, loop will be faster since it generates the loop as in-line code with no function calls.

While
http://t3x.dyndns.org/LISP/CL/reduce.html

suggests:
REDUCE
Purpose:
Reduce a list. Combine the first member of the list with the reduced rest of the list using a given function. Arguments:
A - list to reduce
X - default member (replaces NIL)
F - combining function

Model:

(defun reduce (a x f)
(cond ((null a) x)
(t (f (car a) (reduce (cdr a) x f)))))

Implementation:

(defun reduce (a x f)
(label ((red (lambda (a b)
(cond ((null a) b)
((null b) (red (cdr a) (f (car a) x)))
(t (red (cdr a) (f (car a) b)))))))
(red (reverse a) nil)))

[eddier]

Note that the gcd (greatest common divisor) function above works over a variable number of arguments. Like

(gcd 8 32 12 16) => 4

instead of just two.

A reduce function repeatedly applies a binary function like (gcd_ a b) over a list until the list is reduced to one value. For example:

(reduce f '(arg1 arg2 arg3 ... argn)) =>
(f arg1 (f arg2 (f arg3 ... (f argn-1 argn))) ...)))

Note (apply gcd_ '(arg1 arg2 arg3 ... argn)) doesn't work because (gcd_ a b) only operates on the first two arguments.

Eddie

[eddier]

Yes, Nigel has it.

Looking back at some of my scripts I have done basically this same operation in many places. I';ve just abstracted the operation out and called it "reduce." I noticed the function is called "red" in some Lisp books.

Eddie

[newdep]

Eddier ;-) You are following the Rebol way ;-)

[Lutz]

Thanks for the clarification I now understand what 'reduce' does. It would be easy to implement. Whould it be useful to have an additional parameter for the number of args, i.e:

(defne (foo x y z) ...)

(reduce foo aList 3)

Or is this something which never occurs?

Lutz

ps: note that in newLISP all arithmetik, logic and bit operators are self reducing.

[eddier]

That would be more generic than what I've seen in books. Most of the Lisp examples I've seen, just constructed a new reduce when they needed to operate on ternary functions, 4nary functions, etc. Could the additional parameter be optional so that

Code: Select all

(reduce f L)  ;; assume f is binary
(reduce f L 3) ;; f is ternary
(reduce f L 4) ;; f is 4nary
...

Note that it would be an error if the third parameter is not a natural number greater than or equal to two.

ps: yes, all built in operators are self reducing, but, the combination of a define-macro and reduce functions would make it easy to create your own.

Eddie

[nigelbrown]

from:
http://cs.hiram.edu/~walkerel/cs152/lesson7.html

"REDUCE applies a function "between" elements of a list
The REDUCE function got its name from the fact that it reduces a list to a single element. It does this by applying the function to the first two elements of the list, then to the result and the third element, etc. So (REDUCE #'+ '(1 2 3 4 5 6)) returns (+ (+ (+ (+ (+ 1 2) 3) 4) 5) 6) or 21. REDUCE is also nice to use with APPEND to jam a bunch of lists together, i.e. (REDUCE #'APPEND '((A B) (C D) (E F G) NIL (H I))) returns (A B C D E F G H I).
Like MAPCAR, REDUCE can be defined recursively in terms of funcall. This example implements a slightly simplified version.


(defun my-reduce (fn lst)
(cond
;;no elements - return nil
((null lst) nil)
;; one element - return it
((null (cdr lst)) (car lst))
;; more than one element - recurse
(t (funcall fn (car lst) (my-reduce fn (cdr lst))))))
"
newLISP'ing this using apply to make funcall functionality gives (I think):
(define (my-reduce funct lst)
(cond
;;no elements - return empty
((not lst) nil)
;; one element - return it
((not (rest lst)) (first lst))
;; more than one element - recurse
(true (apply funct (list (first lst) (my-reduce funct (rest lst)))))))

which is another way of doing Eddier's reduce without slice's
thus:
> (my-reduce 'append '((A B) (C D) (E F G) () (H I)))
(A B C D E F G H I)
>

> (define-macro (gcd) (my-reduce gcd_ (args)))
(lambda-macro () (my-reduce gcd_ (args)))
> (gcd 8 32 12 16)
4
>

[Lutz]

The next 'apply' will have a reduce option, which is the number of arguments of the functions which gets then applied in a 'reducing' fashion:

(apply gcd '(8 32 12 16) 2) => 4

Lutz

[eddier]

After thinking about what Nigel has posted, maybe we need a negative index for right to left associativity and a positive index for left to right associativity.

Example

Code: Select all

(apply gcd '(8 32 12 16) 2) =>
:: gcd '(8 12 16) 
:: gcd '(4 16)
:: 4

(apply gcd '(8 32 12 16) -2) =>
:: gcd '(8 32 4)
:: gcd '(8 4)
:: 4

Some functions are not commutative, mod for example, and their will be a difference when executed from left to right, or right to left.

Also, is their a way to determine if the function that is being applied has two, three, ... arguments. Otherwise, what if the programmer applies a binary operator and has ternary index? Maybe just use a flag to denote left or right associativity.

Eddie

[Lutz]

At the moment there will be no associativity index or flag. This can partly be alleviated by reversing the list, Of course this also changes the order of arguments. But one can take care of this when making the argument list in the first place.

When 3 is specified for a binary op than always 3 arguments get fed to the binary operator, which will than ignore the third one:

(apply biop '(1 2 3 4 5) 3)

; equivalent to

(biop (biop 1 2 3) 4 5)

Lutz

[eddier]

Thanks! Please make note of whether is left or right associative in the manual.

Eddie

[nigelbrown]

If you look at some of the underlying source (I think it was in gcl - gnu common lisp - code) to implement the "If :from-end is true, the reduction is right-associative instead of left-associative:" the list is just reversed before reducing,