Defining "reduce" on a list in scheme

Question

(define (BOR x y)
  (cond
    ((equal? x #t)  #t)
    ((equal? y #t)  #t)
  (else           #f))
)

(define (reduce op list)
  (cond
    ((null? list)
      (cond
        ((BOR (equal? op +) (equal? op -))  0)
        ((BOR (equal? op *) (equal? op /))  1)
        ((equal? op BOR)                    #f)
        ((equal? op BAND)                   #t)
      (else                               #f)))
  (else  (op (car list) (reduce op (cdr list)))))
)

(display (reduce + '(1 2 3 4 5)))
(newline)
(display (reduce - '(100 20 30)))
(newline)

I included "BOR" for visibility. Here is my output:

120
110

It seems my definition is valid, but does not evaluate subtraction and division how I would like. I attempted removing BOR, leaving 6 conditions to check after the check for a null list, without any change in output.

You might notice the behavior is somewhat like this:

(reduce - '(100 20 30 5 40)) is called.
This returns (+ (- (+ (- 100 20) 30) 5) 40).
Which is equivalent to 100 - 20 + 30 - 5 + 40 = 145.

This flip flop behavior only happens when I divide or subtract. All of my other operations perform just fine. This is homework for me, so please no direct answers. Maybe I am missing some key behavior pattern of scheme recursion? Any help would be appreciated.

Answer 1

This is what happens with your last example:

(reduce - '(100 20 30 5 40))
=> (- 100 (- 20 (- 30 (- 5 (- 40 0)))))
=> (- 100 (- 20 (- 30 (- 5 40)))
=> (- 100 (- 20 (- 30 -35)))
=> (- 100 (- 20 65))
=> (- 100 -45)
=> 145

but what you want is probably

> (- 100 20 30 5 40)
5

which is the same as

> (- (- (- (- 100 20) 30) 5) 40)
5

so you need to change your recursion in the else clause.

---

A major problem is that your way of writing reduce leaves a 'dangling' operation which forces you to know in your procedure which final element to apply in order not to interfere with the result: 0 for + and -, 1 for * and /, #f for or and #t for and. This means that your reduce has to accommodate for every possible procedure you give it, and that's not sustainable.

There are easier ways, for example:

(define (reduce op lst)
  (let loop ((res (car lst)) (lst (cdr lst)))
    (if (null? lst)
        res
        (loop (op res (car lst)) (cdr lst)))))

testing:

> (reduce - '(100 20 30 5 40))
5
> (reduce + '(1 2 3 4 5))
15
> (reduce / '(100 5 4))
5

---

I understand you need or and and as a function; this can be expressed more simply:

(define (BOR x y)
  (or x y))

(define (BAND x y)
  (and x y))

---

Hope this helps.

Answer 2

Handling zero and one argument cases

The operations + and * are already defined in Scheme to accept 0 arguments and to return the identity function in those cases. The subtraction and division functions don't have this property, largely because they have a special case for one argument, since it's more convenient to have (/ 2) return 1/2 than to return 2, and more convenient to have (- 2) return -2 than 2.

The forms or and and are not functions, but are also defined with the ability to take any number (including zero) of arguments. or returns true if at least one argument is true, and so returns #f when there are no arguments. and returns false if at least one argument is false, and so returns #t when called with no arguments.

Handling commutativity

Additional and multiplication are commutative and associative, so you can add an identity element to either end of the sequence that you're reducing without a problem. E.g., 0+a+b+c will be the same as a+b+c+0 regardless of how insert parentheses. However, subtraction and division don't have this property. a-b-c is not, in general, the same as c-b-a, and 0-a-b is not the same as a-b-0.

This means that your reduce function needs to state which order the elements will be combined in, and where an identity element (or initial element) should be injected. This is typical of folds in general, not just reduce.

Implement reduce with an initial value

I know you said you didn't want solutions because this is homework, but I think that this code will be different enough from your own that it's not a big problem. Not only that, Stack Overflow answers are supposed to be useful to everyone, not just the original asker. Finally, reduce is a very common function, and it's not hard to find implementations of it.

(define (reduce fn list init)
  (if (null? list) init
      (fn (car list)
          (reduce fn (cdr list) init))))

This is a right-associative fold that inject the init to the right of the last element in the list. That is, for (reduce fn '(a b c) i), you get

(fn a (fn b (fn c i)))

That means that you can do

(reduce + '(...) 0)
(reduce - '(...) 0)
(reduce * '(...) 1)
(reduce / '(...) 1)

For the boolean cases, you need functions like and and or, but those are easy enough:

(define (%or x y)
  (or x y))

(define (%and x y)
  (and x y))

Then you can do

(reduce %or  '(...) #t)
(reduce %and '(...) #f)

Note that a right-associative reduce puts the identity element where you want it in the division and subtraction case, since you end up turning '(a b c d) into

(a - (b - (c - (d - 0))))

(a / (b / (c / (d / 1))))

However, there's a good chance that that's not what you want, because it means you get the "flip-flop" behavior you described. E.g.,

a/(b/c) = (ac)/b ≠ (a/b)/c

For division and subtraction, you probably want a left-associative reduce. Those actually happen to be a bit more efficient in Scheme, since they can be implemented tail-recursively, and so use less stack space.

(define (reduce fn init list)
  (if (null? list) init
      (reduce fn (fn init (car list)) (cdr list))))

This is the way that a left-associative fold feels most natural to me, since initial-value is placed to the left of the list, so we have ((((i • a) • b) • c). The problem, of course, is that for division and subtraction, we really want the "initial" value to be placed at the end. You can write a version that does that, but it's a bit more complicated, because you have to check three cases: (i) list having no elements; (ii) list having one element; and (iii) list having at least two elements:

(define (reduce fn list final)
  (cond
    ((null? list)
     init)
    ((null? (cdr list)) 
     (fn (car list) init))
    (else
     ;; do a normal left-associative reduce over the 
     ;; list, but add the final element at the end.
     (let red ((init (fn (car list) (cadr list)))
               (list (cddr list))
       (if (null? list) (fn init final)
           (red (fn init (car list)) (cdr list))))))))

Answer 3

You've defined your reduce as a right fold; it is usually defined as a left fold in strict (i.e. non-lazy) languages, like Scheme:

(define (reduce op z lst)   
  (cond ((null? lst) z)    ; just pass it in as another argument
    (else (reduce op 
                  (op z (car lst))  ; NB! `z` as first arg
                  (cdr lst)))))

Now (reduce - 100 (list 20 30 5 40)) returns (((100 - 20) - 30) - 5) - 40 = 5.

Notice the parenthesization to the left; that's why it is called a left fold. Also, do notice the order of arguments which I arrange to be applied to the combining operation op. It is the opposite of the usual, but it better fits the - operation used here.

Answer 4

We can write out (reduce - '(100 20 30 5 40)); it becomes

(- 100 (- 20 (- 30 (- 5 (- 40 0)))),

or in infix notation (100 - (20 - (30 - (5 - 40)))), which explains the flip-flopping problem.