Python's Reduce Function - Written in Scheme

Question

Evening!

I need to write a reduce function in Scheme that works just as the built-in reduce function in Python. It's easy to write a reduce function in Scheme:

(define (reduce fn lis identity)
  (if (null? lis)
    identity
    (fn (car lis)
        (reduce fn (cdr lis) identity))))

However, this code isn't identical to the Python reduce, which takes only two arguments (the function and a list of items to reduce).

Can anyone help me write a Scheme function that works this way?

(>(reduce * '(2 4 5 5)) => 200, is our professor's example.)

Thanks so much, guys and gals. You are so helpful <3

ETA: To Mr. Levien and Mr. Jester-Young, thank you so very much. You provided the perfect amount of information to help me figure the problem out on my own. *hug

Answer 1

That is easy. The accumulator is initialized with the first element of the list:

(define (py-reduce f ls) (fold f (car ls) (cdr ls)))

(py-reduce * '(2 4 5 5)) => 200

Feel free to use another reduce function than fold from srfi-1 (like reduce, fold-right ...) or use your own. Your list needs one element at least.

Answer 2

Having an identity allows your function to work with a list of size zero or more - when it's an empty list, you get the identity. Without an identity, the function will only work with a list of one or more elements. Some functions naturally have an identity (zero for addition, one for multiplication, etc). Others don't - min and max in particular, especially over big ints.

You should be able to figure out the rest :)

Answer 3

Below is a tail-recursive version. Your professor isn't likely to like it (since it doesn't demonstrate recursion ;-)), but at least it will give you some idea how to go about it.

(define (reduce func lst)
  (let loop ((val (car lst))
             (lst (cdr lst)))
    (if (null? lst) val
        (loop (func val (car lst)) (cdr lst)))))

As hinted in Raph Levien's excellent answer, this version will not work if the incoming list is empty (that'd be what the identity parameter is for). You will, in this case, get an error (since you can't car or cdr an empty list).