Lisp: How to write a Higher Order Function

Question

I have this problem to work on:

The sum higher order procedure can be generalised even further to capture the idea of combining terms with a fixed operator. The mathematical product operator is a specific example of this idea, with multiplication replacing the addition of the summation operator. The procedure accumulate, started below, is intended to capture this idea. The combiner parameter represents the operator that is used to reduce the terms, and the base parameter represents the value that is returned when there are no terms left to be combined. For example, if we have already implemented the accumulate procedure, then we could define the sum procedure as:

(define sum (accumulate + 0))

Complete the definition of accumulate so that it behaves according to this description.

          (define accumulate
             (lambda (combiner base)
                (lambda (term start next stop)
                   (if (> start stop)
                        ...
                        ...))))

I inserted as the last two lines:

   base
   (combiner base (accumulate (combiner start stop) start next stop))

but, I have no idea if this is correct nor how to actually use the sum procedure to call accumulate and hence sum up numbers.

Answer 1

This is a great way to learn how to fish. Much better than being given a fish.

Until then, here's how to approach the problem. Write a function which would do what (accumulate + 0) would do. Don't use the accumulate function; just write a defun which which does what your homework asks. Next, write a function which would do what (accumulate * 1) would do. What are the similarities, what are the differences between the two functions. For the most part, they should be identical except for the occurrence of the + and * operators.

Next, note that the accumulate function is to return a function which will look a lot like the two functions you wrote earlier. Now, using the insight that two functions you wrote are very similar, think how to apply that to the function which (defun accumulate ...) is to return.

Answer 2

Thanks for the reply, I already have the a bookmark to the link you provided. I just needed some guidance as to how to proceed.

The problem is that I keep thinking about * and + as doing just what we all use them for (I can't see them as having to be defined to do that).

Nevertheless, I will follow your suggestions.

Thanks again.

Answer 3

I tried and I think I have it now:

(define accumulate (lambda (combiner base) (lambda (term start next stop) (if (> start stop) base (combiner (term (+ start 1) next stop))))))

Now, my question is how do I use accumulate to, say, sum up a series of numbers.