Accumulating Curried Function (SML)

Question

I have a set of problems that I've been working through and can't seem to understand what the last one is asking. Here is the first problem, and my solution to it:

a) Often we are interested in computing ∑_i=m..n f(i), the sum of function values f(i) for i = m through n. Define sigma f m n which computes ∑_i=m..n f(i). This is different from defining sigma (f, m, n).

fun sigma f m n = if (m=n) then f(m) else (f(m) + sigma f (m+1) n);

The second problem, and my solution:

b) In the computation of sigma above, the index i goes from current i to next value i+1. We may want to compute the sum of f(i) where i goes from current i to the next, say i+2, not i+1. If we send this information as an argument, we can compute more generalized summation. Define ‘sum f next m n’ to compute such summation, where ‘next’ is a function to compute the next index value from the current index value. To get ‘sigma’ in (a), you send the successor function as ‘next’.

fun sum f next m n = if (m>=n) then f(m) else (f(m) + sum f (next) (next(m)) n);

And the third problem, with my attempt:

c) Generalizing sum in (b), we can compute not only summation but also product and other forms of accumulation. If we want to compute sum in (b), we send addition as an argument; if we want to compute the product of function values, we send multiplication as an argument for the same parameter. We also have to send the identity of the operator. Define ‘accum h v f next m n’ to compute such accumulation, where h is a two-variable function to do accumulation, and v is the base value for accumulation. If we send the multiplication function for h, 1 for v, and the successor function as ‘next’, this ‘accum’ computes ∏_i=m..n f(i). Create examples whose ‘h’ is not addition or multiplication, too.

 fun accum h v f next m n = if (m>=n) then f(m) else (h (f(m)) (accum (h) (v) (f) (next) (next(m)) n));

In problem C, I'm unsure of what i'm suppose to do with my "v" argument. Right now the function will take any interval of numbers m - n and apply any kind of operation to them. For example, I could call my function

accum mult (4?) double next3 1 5;

where double is a doubling function and next3 adds 3 to a given value. Any ideas on how i'm suppoes to utilize the v value?

Answer 1

This set of problems is designed to lead to implementation of accumulation function. It takes

• h - combines previous value and current value to produce next value
• v - starting value for h
• f - function to be applied to values from [m, n) interval before passing them to h function
• next - computes next value in sequence
• m and n - boundaries

Here is how I'd define accum:

fun accum h v f next m n = if m >= n then v else accum h (h (f m) v) f next (next m) n

Examples that were described in C will look like this:

fun sum x y = x + y;
fun mult x y = x * y;
fun id x = x;

accum sum 0 id next 1 10; (* sum [1, 10) staring 0 *)
accum mult 1 id next 1 10; (* prod [1, 10) starting 1 *)

For example, you can calculate sum of numbers from 1 to 10 and plus 5 if you pass 5 as v in first example.

Answer 2

The instructions will make more sense if you consider the possibility of an empty interval.

• The "sum" of a single value n is n. The sum of no values is zero.
• The "product" of a single value n is n. The product of no values is one.
• A list of a single value n is [n] (n::nil). A list of no values is nil.

Currently, you're assuming that m ≤ n, and treating m = n as a special case that returns f m. Another approach is to treat m > n as the special case, returning v. Then, when m = n, your function will automatically return h v (f m), which is the same as (f m) (provided that v was selected properly for this h).

To be honest, though, I think the v-less approach is fine when the function's arguments specify an interval of the form [m,n], since there's no logical reason that such a function would support an empty interval. (I mean, [m,m−1] isn't so much "the empty interval" as it is "obvious error".) The v-ful approach is chiefly useful when the function's arguments specify a list or set of elements in some way that really could conceivably be empty, e.g. as an 'a list.